DEV Community: Şahin Arslan

A Voyage through Algorithms using Javascript - Radix Sort

Şahin Arslan — Sun, 19 Oct 2025 17:34:36 +0000

What is Radix Sort?

Radix Sort is a clever non-comparison based sorting algorithm that sorts integers by processing individual digits. Think of it like opening a baggage lock with multiple dials. You align the digits one dial at a time. First, you sort all numbers based on the rightmost digit (the ones place), then move to the next digit (tens place), and continue until every dial is aligned. By the end, all the numbers are perfectly ordered without ever directly comparing them.

Unlike comparison-based algorithms like Bubble Sort, Insertion Sort, and Merge Sort, Radix Sort doesn't compare numbers directly. Instead, it leverages Counting Sort as a subroutine to sort numbers digit by digit. The time complexity is O(d × (n + k)), where d is the number of digits, n is the number of elements, and k is the range of digit values (0-9 for decimal numbers).

Radix Sort shines when dealing with integers, especially when they have a fixed number of digits or when the range is large but the number of digits is reasonable. It's not a general-purpose sort like Merge Sort, but when the conditions align, it can outperform even the most optimized comparison-based algorithms.

How Radix Sort Works

Radix Sort operates through a systematic, digit-by-digit approach:

Find the maximum number: Determine how many digits we need to process by finding the largest number in the array.
Start from the least significant digit (LSD): Begin with the rightmost digit (ones place).
Use stable sorting: Sort the entire array based on the current digit using a stable algorithm (typically Counting Sort).
Move to the next digit: Shift one position left (tens, hundreds, thousands, etc.).
Repeat until done: Continue until you've processed all digits of the maximum number.

This approach utilizes the stability requirement in a smart way. When you sort by the ones place first, then the tens place, the stability plays the key role: numbers with the same tens digit remain in the order established by their ones digit. This cascading effect builds up the final sorted result.

Here's a visualization to make the concept clearer:

Implementing Radix Sort in JavaScript

Let's take a look at the implementation of Radix Sort in JavaScript, with detailed comments explaining each part:

function radixSort(arr) {
  if (arr.length === 0) return arr;

  // STEP 1: Find the maximum number to determine how many digits we need to process
  // This tells us how many times we need to run our digit-by-digit sorting
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }

  // STEP 2: Process each digit position, starting from the least significant (rightmost)
  // exp represents which digit we're looking at: 1 for ones, 10 for tens, 100 for hundreds, etc.
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    // Use counting sort to sort based on the current digit
    arr = countingSortByDigit(arr, exp);
  }

  return arr;
}

function countingSortByDigit(arr, exp) {
  // This is counting sort modified to sort by a specific digit position
  const output = new Array(arr.length);
  const count = new Array(10);

  // Initialize count array to zeros manually
  for (let i = 0; i < 10; i++) {
    count[i] = 0;
  }

  // STEP 1: Count occurrences of each digit (0-9) at the current position
  for (let i = 0; i < arr.length; i++) {
    // Extract the digit at position 'exp': (num / exp) % 10
    // Example: For 342 with exp=10, we get (342/10)%10 = 34%10 = 4 (the tens digit)
    const digit = Math.floor(arr[i] / exp) % 10;
    count[digit]++;
  }

  // STEP 2: Transform counts to cumulative positions
  // This tells us where each digit group should END in the output array
  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }

  // STEP 3: Build the output array by placing elements in their sorted positions
  // Process backwards to maintain stability - must have for Radix sort!
  for (let i = arr.length - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    const position = count[digit] - 1;
    output[position] = arr[i];  // Place the entire number
    count[digit]--;
  }

  return output;
}

// Example usage:
const numbers = [170, 45, 75, 90, 802, 24, 2, 66];
console.log("Original:", numbers);
console.log("Sorted:", radixSort(numbers));

/*
Output:
Original: [170, 45, 75, 90, 802, 24, 2, 66]
Sorted: [2, 24, 45, 66, 75, 90, 170, 802]
*/

Key Implementation Details for Radix Sort

1. The Exponential Loop Magic

for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10)

The loop continues while there are still digits to process. When max / exp becomes less than 1, we've processed all digits. For example, with max = 802:

exp = 1: 802 / 1 = 802 (process ones place)
exp = 10: 802 / 10 = 80.2 (process tens place)
exp = 100: 802 / 100 = 8.02 (process hundreds place)
exp = 1000: 802 / 1000 = 0.802 → Stop!

2. The Digit Extraction Trick

const digit = Math.floor(arr[i] / exp) % 10;

This formula extracts any digit from a number:

arr[i] / exp shifts the desired digit to the ones place
Math.floor() removes everything to the right
% 10 isolates just that single digit

Examples:

For 342 with exp = 1: Math.floor(342 / 1) % 10 = 342 % 10 = 2 (ones digit)
For 342 with exp = 10: Math.floor(342 / 10) % 10 = 34 % 10 = 4 (tens digit)
For 342 with exp = 100: Math.floor(342 / 100) % 10 = 3 % 10 = 3 (hundreds digit)

3. Why Stability is Non-Negotiable

Radix Sort absolutely requires a stable sorting algorithm for each digit pass. Here's why:

// Original array: [13, 12]
// After sorting by ones place (3 vs 2): [12, 13] ✓
// After sorting by tens place (1 vs 1): 
//   - With stability: [12, 13] ✓ (preserves ones-place order)
//   - Without stability: [13, 12] ✗ (might swap unnecessarily)

Without stability, the carefully established order from previous digit passes would be destroyed. That's why we use the stable variant of Counting Sort as our subroutine.

4. The Backwards Pass Trick

for (let i = arr.length - 1; i >= 0; i--)

Processing the array backwards when placing elements into the output is what guarantees stability in our Counting Sort implementation. This is critical for Radix Sort to work correctly.

5. Handling Zero Values

The algorithm naturally handles zeros because:

Math.floor(0 / exp) % 10 = 0 for any exp
Zeros get counted in count[0]
They're placed at the beginning of the output (where they belong!)

Radix Sort's Stability Chain Pattern

The magic of Radix Sort comes from its stability chain. Let's follow through an example to see this in action:

// Original: [170, 45, 75, 90, 802, 24, 2, 66]

// After sorting by ONES place (exp = 1):
// [170, 90, 802, 2, 24, 45, 75, 66]
// Buckets: 
// 0 → [170, 90]
// 2 → [802, 2]
// 4 → [24]
// 5 → [45, 75]
// 6 → [66]

// After sorting by TENS place (exp = 10):
// [802, 2, 24, 45, 66, 170, 75, 90]
// Buckets:
// 0 → [802, 2]
// 2 → [24]
// 4 → [45]
// 6 → [66]
// 7 → [170, 75, 90]
// Notice: **170 stays before 75, which stays before 90** — stability preserved!

// After sorting by HUNDREDS place (exp = 100):
// [2, 24, 45, 66, 75, 90, 170, 802]
// Buckets:
// 0 → [2, 24, 45, 66, 75, 90]
// 1 → [170]
// 8 → [802]
// The previous ones and tens order is preserved within each hundred’s bucket!

Time and Space Complexity Analysis

Radix Sort's performance characteristics are:

Time Complexity: O(d × (n + k)) in all cases

d = number of digits in the maximum number
n = number of elements in the array
k = range of digit values (10 for decimal numbers)
We run Counting Sort d times, and each Counting Sort pass takes O(n + k)

In practice, for decimal numbers (k = 10), this simplifies to O(d × n).

Space Complexity: O(n + k)

O(n) for the output array in each Counting Sort pass
O(k) for the count array (10 for decimal digits)
Total: O(n + 10) = O(n) in practice

The d factor is the critical trade-off: Radix Sort's efficiency depends entirely on how many digits you're processing. Let's look at real numbers:

Example 1: Sorting 1,000,000 elements

32-bit integers (max value ~4 billion) have at most 10 digits
Radix Sort: 10 passes through 1 million elements = 10 million operations
Merge Sort: needs roughly 20 million comparisons (n log n where log of 1 million ≈ 20)
Radix Sort wins: fewer total operations

Example 2: Sorting 1,000 elements

Same 32-bit integers with 10 digits
Radix Sort: 10 passes through 1,000 elements = 10,000 operations
Merge Sort: needs roughly 10,000 comparisons (n log n where log of 1,000 ≈ 10)
Close comparison: similar operation counts

Example 3: Sorting 1,000 elements with huge numbers

128-bit integers (max 39 digits)
Radix Sort: 39 passes through 1,000 elements = 39,000 operations
Merge Sort: still roughly 10,000 comparisons
Merge Sort wins: way fewer operations needed

What to look for:

Small d, large dataset: Radix Sort shines (millions of phone numbers, IP addresses)
Large d, small dataset: Comparison sorts are simpler and faster
Rule of thumb: If your maximum value has more than 15-20 digits, reconsider Radix Sort

The larger your dataset, the more Radix Sort's fixed number of passes pays off. The more digits in your numbers, the more those passes cost you.

Is Radix Sort Stable?

Yes, Radix Sort is a stable sorting algorithm, but only when implemented with a stable subroutine like Counting Sort.

The stability of Radix Sort is inherited from its subroutine:

Each digit pass must maintain the relative order of elements with the same digit
This cascades through all digit positions
The final result preserves the original order of equal elements

If you tried using an unstable sort (like a naive Quick Sort) for the digit passes, Radix Sort would break. The algorithm fundamentally depends on stability to build up the correct final order.

Advantages and Disadvantages of Radix Sort

Advantages:

Linear time complexity when d is small: O(d × n) beats O(n log n)
Stable sorting algorithm
Predictable performance - no worst-case degradation
Excellent for fixed-length integer keys
Can be parallelized for each digit position

Disadvantages:

Only works for integers (or data that can be represented as integers)
Performance degrades when d (number of digits) is large
Requires extra space: O(n) for output arrays
More complex to implement than simple comparison sorts
Not cache-friendly due to scattered memory access patterns

When to Choose Radix Sort

Radix Sort excels in specific scenarios but has clear limitations. Here's when to consider it:

Perfect for:

Fixed-length integers: Social security numbers, zip codes, product IDs
Large datasets with small digit counts: Millions of 32-bit integers (d=10)
Uniform integer distributions: Data where numbers have similar digit lengths
Stable sorting requirements: When order preservation matters
Known digit ranges: When you can control or predict the maximum value

Avoid when:

Variable-length data: Strings of very different lengths, arbitrary-precision numbers
Large d values: Sorting 128-bit integers or cryptographic hashes
Non-integer data: Floating-point numbers (without conversion), complex objects
Small datasets: The overhead isn't worth it for 100 elements
Memory constraints: If you can't afford O(n) extra space

The golden rule: Radix Sort is brilliant when d << log n, meaning the number of digits is much smaller than the logarithm of the array size. If you're sorting a million integers (log n ≈ 20) with 6 digits each, Radix Sort wins. If you're sorting a thousand 50-digit numbers, comparison sorts are better.

Radix Sort vs Counting Sort: When to Use Which?

Since Radix Sort uses Counting Sort internally, you might wonder when to use each:

Use Counting Sort when:

Values are in a small, known range (e.g., 0-100)
The range k is not much larger than n
You're sorting primitive integers directly

Use Radix Sort when:

Values have multiple digits/positions to process
The range is large but digit count is small (e.g., 32-bit integers)
You want to avoid the range limitation of Counting Sort

Example:

// Counting Sort is better:
[23, 45, 12, 89, 67, 34]  // Range: 12-89 (78 values)

// Radix Sort is better:
[123456, 789012, 345678, 901234]  // Range: huge, but only 6 digits

Real-World Applications

Radix Sort shines in problems where data naturally has fixed-length integer keys:

Data Processing: Sorting IP addresses, MAC addresses, social security numbers, zip codes, phone numbers

Computer Graphics: Sorting pixels by color channels, z-buffer sorting for 3D rendering

Database Systems: Integer key indexing, parallel sorting in distributed systems

Network Routing: Sorting packets by priority or destination codes

Scientific Computing: Sorting particle positions, grid coordinates in simulations

Handling Negative Numbers

The implementation above works only for non-negative integers. To handle negative numbers, you have two approaches with different trade-offs:

Offset Approach: Best when the range is reasonable

Shifts all numbers to be non-negative by adding the absolute value of the minimum
Simpler logic, single sort pass
Risk: Can cause integer overflow if your numbers are near the maximum integer limit
Choose this when: Your numbers are well within safe integer ranges

Split and Merge: Best for extreme values

Separates negatives and positives, sorts independently, then combines
No overflow risk since we're working with absolute values
Slightly more operations (two separate sorts)
Choose this when: You're dealing with very large numbers or want guaranteed safety

Option 1: Offset Approach

function radixSort(arr) {
  if (arr.length === 0) return arr;

  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }

  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    arr = countingSortByDigit(arr, exp);
  }

  return arr;
}

function countingSortByDigit(arr, exp) {
  const output = new Array(arr.length);
  const count = new Array(10);

  for (let i = 0; i < 10; i++) {
    count[i] = 0;
  }

  for (let i = 0; i < arr.length; i++) {
    const digit = Math.floor(arr[i] / exp) % 10;
    count[digit]++;
  }

  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }

  for (let i = arr.length - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    const position = count[digit] - 1;
    output[position] = arr[i];
    count[digit]--;
  }

  return output;
}

function radixSortWithNegatives(arr) {
  if (arr.length === 0) return arr;

  // Find min to offset all values to non-negative
  let min = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < min) min = arr[i];
  }

  let offset = min < 0 ? -min : 0;

  // Offset all values
  let offsetArr = new Array(arr.length);
  for (let i = 0; i < arr.length; i++) {
    offsetArr[i] = arr[i] + offset;
  }

  // Sort the offset array
  let sorted = radixSort(offsetArr);

  // Remove offset
  let result = new Array(sorted.length);
  for (let i = 0; i < sorted.length; i++) {
    result[i] = sorted[i] - offset;
  }

  return result;
}

// Example usage:
const mixedNumbers = [170, -45, 75, -90, 802, 24, -2, 66];
console.log("Sorted:", radixSortWithNegatives(mixedNumbers));
// Output: [-90, -45, -2, 24, 66, 75, 170, 802]

Option 2: Split and Merge

function radixSort(arr) {
  if (arr.length === 0) return arr;

  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }

  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    arr = countingSortByDigit(arr, exp);
  }

  return arr;
}

function countingSortByDigit(arr, exp) {
  const output = new Array(arr.length);
  const count = new Array(10);

  for (let i = 0; i < 10; i++) {
    count[i] = 0;
  }

  for (let i = 0; i < arr.length; i++) {
    const digit = Math.floor(arr[i] / exp) % 10;
    count[digit]++;
  }

  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }

  for (let i = arr.length - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    const position = count[digit] - 1;
    output[position] = arr[i];
    count[digit]--;
  }

  return output;
}

function radixSortWithNegatives(arr) {
  // Separate negatives and positives
  let negatives = [];
  let positives = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < 0) {
      negatives.push(-arr[i]);  // Store as positive
    } else {
      positives.push(arr[i]);
    }
  }

  // Sort both groups
  negatives = radixSort(negatives);
  positives = radixSort(positives);

  // Reverse negatives and negate them back
  let result = new Array(negatives.length + positives.length);
  let index = 0;

  for (let i = negatives.length - 1; i >= 0; i--) {
    result[index] = -negatives[i];
    index++;
  }

  for (let i = 0; i < positives.length; i++) {
    result[index] = positives[i];
    index++;
  }

  return result;
}

// Example usage:
const mixedNumbers = [170, -45, 75, -90, 802, 24, -2, 66];
console.log("Sorted:", radixSortWithNegatives(mixedNumbers));
// Output: [-90, -45, -2, 24, 66, 75, 170, 802]

Bottom line: For most everyday use cases, go with the split and merge approach. It's more intuitive (you can see it sorting negatives and positives separately), safer (no overflow worries), and the performance difference is negligible. Only choose offset if you're really trying to squeeze out every bit of performance and you're certain your values are safe.

Conclusion

Radix Sort reminds us that sometimes the best way to solve a problem is to break it into smaller, identical subproblems.

Radix Sort isn't a general-purpose solution, but understanding it gives further inspiration about the algorithm design. It shows how leveraging data structure (multiple digits) and algorithmic properties (stability) in a creative way can unlock performance gains that seem impossible at first glance.

When you're sorting integers and the conditions align, do remember about the Radix Sort. It might just be the fastest tool in your algorithmic toolbox for that specific problem.

A Voyage through Algorithms using Javascript - Counting Sort

Şahin Arslan — Sun, 27 Jul 2025 14:55:45 +0000

What is Counting Sort?

Counting Sort is a specialized non-comparison based sorting algorithm that works by counting how many times each number appears in the array, then using those occurrence counts to rebuild the sorted result. Unlike the comparison-based algorithms we've explored like Bubble Sort, Insertion Sort, and Merge Sort, Counting Sort doesn't compare numbers to each other at all. Instead, it leverages the simple concept of counting occurrences to achieve O(n + k) time complexity, where n is the number of elements and k is the range of input values.

The core logic is straightforward: if you know you have three 5's, two 8's, and one 1, you can rebuild the sorted array [1, 5, 5, 5, 8, 8] without ever comparing individual numbers.

Counting Sort is a niche algorithm that shines in specific scenarios: particularly when sorting integers within a known, limited range. It's not a general-purpose sorting solution like comparison-based ones, but when the conditions are right, it can outperform even the most optimized comparison-based sorts. Especially when you're working with integers in a relatively small range.

How Counting Sort Works

Counting Sort operates through four straightforward steps:

Find the range: Determine the smallest and largest numbers in the array so we know what values we're working with.
Create counting buckets: Set up a count array where each index represents a possible value in our range.
Count occurrences: Go through the input array and count how many times each number appears.
Rebuild the sorted array: Use the occurrence counts to construct the final result by adding each number the correct number of times.

The process is simple: instead of asking "is this number bigger than that number?", Counting Sort just asks "how many times does each number appear?" Once you have those counts, rebuilding the sorted array is straightforward.

Here's a visualization to make the concept clearer:

Implementing Counting Sort in JavaScript

Let's take a look at the implementation of Counting Sort in JavaScript, with detailed comments explaining each part:

function countingSort(arr) {
  if (arr.length === 0) return arr;

  // STEP 1: Find the range of numbers we're working with
  // We need to know the smallest and biggest numbers to figure out
  // how many counting buckets we need and how to map values to bucket indices
  let minOffset = arr[0];
  let maxOffset = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < minOffset) minOffset = arr[i];
    if (arr[i] > maxOffset) maxOffset = arr[i];
  }

  // STEP 2: Create our counting buckets
  // We need one bucket for each possible value in our range
  // Example: If the values range from 11 to 15, we need 5 buckets (15 - 11 + 1 = 5)
  const range = maxOffset - minOffset + 1;
  const count = new Array(range);  // Sparse array - undefined slots are okay

  // STEP 3: Count how many times each number appears
  // The trick: map each value to a bucket index by subtracting minOffset
  for (let i = 0; i < arr.length; i++) {
    let value = arr[i];
    // Map value to bucket index: value 11 becomes index 0, value 12 becomes index 1, etc.
    let bucketIndex = value - minOffset;  
    let occurrences = count[bucketIndex] || 0;  // Handle undefined as 0
    count[bucketIndex] = occurrences + 1;  // Increment the count for this bucket
  }

  // STEP 4: Rebuild the sorted array by going through each bucket in order
  // For each bucket that has a count, add that original value to result
  const result = [];
  for (let i = 0; i < count.length; i++) {
    if (count[i]) {  // Skip buckets that are empty (undefined)
      // Convert bucket index back to original value: index 0 becomes value 11, etc.
      let originalValue = i + minOffset;  
      // Add this value to result as many times as we counted it
      while (count[i] > 0) {
        result.push(originalValue);
        count[i]--;  // Decrease count until we've added all occurrences
      }
    }
  }

  return result;
}

Key Implementation Details for Counting Sort

1. The Range Calculation Magic

const range = maxOffset - minOffset + 1;

We need exactly one bucket for each possible value. If our numbers go from 11 to 15, that's 5 different values (11, 12, 13, 14, 15), so we need 5 buckets.

2. The Compression Trick: `value - minOffset`

let bucketIndex = value - minOffset;  // Maps 11→0, 12→1, 13→2, etc.

Array indices must start at 0, but our values might start anywhere. Subtracting minOffset "compresses" any range of values to fit bucket indices starting at 0.

3. Sparse Arrays Are Your Friend

// Creates an array based on range with undefined slots
const count = new Array(range);
// ...
let occurrences = count[bucketIndex] || 0;  // Treats undefined as 0

No need to fill with zeros! We handle undefined values gracefully, which saves time when dealing with sparse data.

4. The Expansion Trick: `i + minOffset`

let originalValue = i + minOffset;  // Maps 0→11, 1→12, 2→13, etc.

When rebuilding, we "expand" bucket indices back to original values by adding minOffset. This is the reverse of our compression step.

5. Handling Negative Numbers

The offset approach works for any range. With values [-5, -3, -1]:

minOffset = -5
Value -5 maps to bucket (-5) - (-5) = 0
Bucket 0 maps back to 0 + (-5) = -5

The beauty is in the symmetry: compress with subtraction, expand with addition.

Is Counting Sort Stable?

Counting sort is a stable algorithm. However though, the simplified implementation above is not technically stable but practically is, here's why:

Stability means that equal elements maintain their relative order from the original array. Above implementation doesn't preserve this because we simply add each integer value multiple times:

while (count[i] > 0) {
  result.push(originalValue);  // Adds the same value multiple times
  count[i]--;
}

Here's the practical part: when sorting primitive integers like [5, 3, 5, 1, 5], all the 5's are literally identical. There's no way to tell which 5 was "first" or "second" because they're exactly the same value.

Stability only matters when sorting objects where equal comparison values have other distinguishing properties:

// A stable sort would always keep Alice before Charlie
// when sorting by grade alone:
let students = [
  {id: 2, name: "Alice", grade: 85, submitted: '09:52'},
  {id: 4, name: "Charlie", grade: 85, submitted: '10:02'},
  // ...
];

For the integer only use cases, the simple variant above is perfectly suitable. I'll be also including a variant that is both stable and accepts an array of objects at the end of this article.

Time and Space Complexity Analysis

Counting Sort's performance characteristics are:

Time Complexity: O(n + k) in all cases

n = number of elements in input array
k = range of input values (maxOffset - minOffset + 1)
We scan the input once (O(n)) + scan the count array once (O(k))

Space Complexity:

Where k is for the count array and n for the output array
Auxiliary space: O(k) - for the count array
Total space: O(n + k) - including the output array

Smaller k factor = better performance: Counting Sort is only efficient when k is not much larger than n. If you're sorting 10 numbers but they range from 1 to 1,000,000, you'd create a million-element count array for just 10 values. That'd be very wasteful!

This is why Counting Sort shines with small, dense ranges but struggles with sparse data like random large integers.

When to Choose Counting Sort

Counting Sort excels in specific scenarios but has clear limitations. Here's when to consider and when to avoid it:

Perfect for:

Small integer ranges: Exam grades (0-100), dice rolls (1-6), RGB values (0-255)
Objects with integer keys: Student records sorted by grade, events by timestamp, inventory by category ID
Dense data: When most values in your range actually appear in the data
Performance-critical sorting: Linear O(n + k) time beats any comparison-based sort
Stable sorting needs: When relative order of equal elements matters

Avoid when:

Sparse data: Sorting small amounts of numbers with large ranges wastes massive memory
Unknown ranges: You need to know min/max values beforehand
Non-integer keys: Floating-point numbers, strings, or objects without suitable integer properties
Memory constraints: The range (k) creates the space bottleneck

The golden rule: Counting Sort is brilliant when range ≈ array size, terrible when range >> array size.

// Inefficient: sorting 10 numbers from 1 to 1,000,000
// Creates a count array of 1 million elements for just 10 values!
const badExample = [5, 999999, 1, 500000, 10];

Counting sort works with any data as long as the sorting key is an integer in a manageable range.

Real-World Applications

Counting Sort shines in problems where the range of values is known and limited:

Digital Systems: Sorting pixel intensities (0-255), character frequencies in text analysis, network packet priorities

Data Processing: Database indexing with categorical values, sorting by age groups or rating scales, organizing inventory by product categories

Algorithm Building Blocks: Used internally by Radix Sort for sorting individual digits, stable sorting subroutine in hybrid algorithms.

Counting Sort Implementation (Object based variant)

function countingSortObjects(arr, key) {
  if (arr.length === 0) return arr;

  // STEP 1: Find range of the target key values
  let minOffset = arr[0][key];
  let maxOffset = arr[0][key];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i][key] < minOffset) minOffset = arr[i][key];
    if (arr[i][key] > maxOffset) maxOffset = arr[i][key];
  }

  // STEP 2: Count frequencies of the key values
  const range = maxOffset - minOffset + 1;
  const count = new Array(range).fill(0);

  for (let i = 0; i < arr.length; i++) {
    count[arr[i][key] - minOffset]++;
  }

  // STEP 3: Transform to cumulative positions
  // This tells us where each key value should END in the final array
  for (let i = 1; i < count.length; i++) {
    count[i] += count[i - 1];
  }

  // STEP 4: Place objects in their final positions (preserving stability)
  const result = new Array(arr.length);

  // Process backwards to maintain original order of objects with same key value
  for (let i = arr.length - 1; i >= 0; i--) {
    let obj = arr[i];
    let keyValue = obj[key];
    let position = count[keyValue - minOffset] - 1;
    result[position] = obj;  // Place the entire object
    count[keyValue - minOffset]--;
  }

  return result;
}

// Example usage:
const students = [
  {id: 1, name: "Bob", grade: 92, submitted: '09:45'}, 
  {id: 2, name: "Alice", grade: 85, submitted: '09:52'},
  {id: 3, name: "Diana", grade: 78, submitted: '09:58'},
  {id: 4, name: "Charlie", grade: 85, submitted: '10:02'},
];

// Sort by grade - Alice stays before Charlie (both grade 85)
const sortedByGrade = countingSortObjects(students, 'grade');
console.log(sortedByGrade);


/*
Output:

[
  { id: 3, name: 'Diana', grade: 78, submitted: '09:58' },
  { id: 2, name: 'Alice', grade: 85, submitted: '09:52' },
  { id: 4, name: 'Charlie', grade: 85, submitted: '10:02' },
  { id: 1, name: 'Bob', grade: 92, submitted: '09:45' }
]

-----

Notice Alice comes before Charlie - that's stability!

*/

Why stability matters here:

Alice and Charlie both have grade 85
A stable sort preserves their original relative order
Alice was first in the input, so she stays first among the 85s in the output

When to use each version:

Simple version: Sorting primitive integers, grades, character codes
Object version: Sorting records, database results, or any structured data where order within equal values matters.

Conclusion

Counting Sort teaches us that sometimes the best algorithm comes from changing the fundamental approach. Instead of asking "which element is bigger?", it asks "how many of each element do I have?"

This shift from comparison to counting unlocks linear time performance that comparison-based sorts mathematically cannot achieve. The trade-off? It only works for specific data types within limited ranges.

When your data fits the mold (integers in a reasonable range), Counting Sort is often the fastest sorting algorithm you can choose.

A Voyage through Algorithms using Javascript - Quick Sort

Şahin Arslan — Sun, 01 Jun 2025 22:08:20 +0000

What is Quick Sort?

Quick Sort is one of the most efficient and widely-used sorting algorithms in computer science. As a "divide and conquer" algorithm, it works by selecting a 'pivot' element and partitioning the array around it. Unlike Merge Sort, which always divides arrays exactly in half, Quick Sort's divisions depend on the chosen pivot.

Quick Sort offers average-case time complexity of O(n log n) with in-place sorting capability, requiring only O(log n) additional memory for the recursion stack. However, its performance can degrade to O(n²) in worst-case scenarios, which makes pivot selection strategy important for optimal performance.

The tone of this article is assumes you are already familiar with Recursion. If that’s not the case or you need a quick refreshment, I’d suggest you to start from the “A Voyage through Algorithms using Javascript - Recursion” article by following the link below, then come back and continue here later:

A Voyage through Algorithms using Javascript - Recursion

How Quick Sort Works

Quick Sort follows a recursive "divide and conquer" approach with a partitioning twist:

Choose: Pick a pivot element from the array (we'll use the last element for simplicity).
Partition: Rearrange the array so smaller elements go before the pivot and larger elements go after it.
Recursively Sort: Apply Quick Sort to the sub-arrays on both sides of the pivot.
Done: Since partitioning puts the pivot in its correct final position, no combining step is needed.

Think of Quick Sort like organizing a bookshelf: you pick a reference book (pivot), move all shorter books to its left and taller books to its right, then repeat this process for each section until everything is perfectly organized. The core mechanic lies within how each partition operation brings elements closer to their final positions.

Let's visualize this process. The number "4" is the starting target pivot in the example below:

Image source: “Quicksort diagram” by Wikipedia user Znupi, released into the public domain.

Implementing Quick Sort in JavaScript

Let's take a look at the implementation of Quick Sort in JavaScript, with detailed comments explaining each part:

function quickSort(arr, start = 0, end = arr.length - 1) {
  // Base case: if the slice has 1 or 0 items, it's already sorted
  if (start >= end) {
    return;
  }

  const pivotValue = arr[end]; // Use the last element as pivot
  let smallerItemsIndex = start; // Marks where smaller values go

  function swap(array, index1, index2) {
    [array[index1], array[index2]] = [array[index2], array[index1]];
  }

  // Move smaller elements to the front
  for (let currentIndex = start; currentIndex < end; currentIndex++) {
    if (arr[currentIndex] < pivotValue) {
      swap(arr, currentIndex, smallerItemsIndex);
      smallerItemsIndex++; // Expand the 'less than pivot' zone
    }
  }

  // Place pivot in final position
  swap(arr, smallerItemsIndex, end);

  // Recursive calls to sort left and right of pivot
  quickSort(arr, start, smallerItemsIndex - 1);    // Left side
  quickSort(arr, smallerItemsIndex + 1, end);      // Right side

  return arr;
}

const nums = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4];
const sorted = quickSort(nums);
console.log('Sorted result:', sorted);
// Output: [1, 2, 4, 5, 6, 44, 63, 87, 99, 283]

Key Implementation Details for Quick Sort

Step 1: Creating a Boundary with In-Place Organization

The algorithm works by creating an invisible boundary in the array using the smallerItemsIndex pointer. We're not creating new subarrays - instead, we're organizing elements in-place within the same array. This pointer tracks where the "smaller than pivot" zone ends and acts as a moving boundary that expands as we find more small elements.

At the start, the "boundary" starts at the index zero. And our pivot is the last index value:

// B: Boundary, P: Pivot
[8, 3, 5, 2, 4]
 ^           ^
 B           P

Step 2: Swapping to Maintain the Boundary

As we scan through the array, whenever we find an element smaller than our pivot, we swap it with the element at our boundary position and move the boundary forward. This swap operation keeps all smaller elements on the left side of our invisible boundary line. In this example, we use the Lomuto partitioning method rather than the Hoare partition scheme because it's simpler for understanding Quick sort since it always uses the last element as the pivot.

In real-world applications, pivot selection can greatly affect performance. Choosing a poor pivot (like always picking the first or last element on a nearly sorted list) can lead to much slower runtimes.

Example of boundary movement:

Pick pivot: 4
Boundary starts at index 0
Iteration begins at index 0

Scan:

8 > 4 → skip

// B: Boundary, P: Pivot, I: Iterator
[8, 3, 5, 2, 4]
 ^           ^
 B           P
 I

3 < 4 → swap with index 0 (8) → [3, 8, 5, 2, 4], move boundary → 1

// B: Boundary, P: Pivot, I: Iterator
[3, 8, 5, 2, 4]
    ^        ^
    B        P
    I

5 > 4 → skip

// B: Boundary, P: Pivot, I: Iterator
[3, 8, 5, 2, 4]
    ^  ^     ^
    B  I     P

2 < 4 → swap with index 1 → [3, 2, 5, 8, 4], move boundary → 2

// B: Boundary, P: Pivot, I: Iterator
[3, 2, 5, 8, 4]
       ^  ^  ^
       B  I  P

Now finally, swap the pivot 4 into the boundary index → [3, 2, 4, 8, 5]

// B: Boundary, P: Pivot, I: Iterator
[3, 2, 4, 8, 5]
       ^     ^
     P & B   I

Pivot 4 is now where it belongs.

Step 3: Pivot Is Placed, Time for Recursion

As we've seen, the pivot is now in its correct position (swapped into the boundary spot). Now comes the recursive step:

Everything to the left is smaller
Everything to the right is larger
The pivot is exactly where it belongs and locked in.

At this point, we don’t touch the pivot anymore. Instead, we make two recursive calls:

One for the left side of the pivot
One for the right side

We only send the parts excluding the pivot, because it’s already in the correct position.

After placing 4, our array looks like this:

[3, 2, 4, 8, 5]
       ^
     Pivot

Now we call Quick Sort again on:
Left side: [3, 2]
Right side: [8, 5]

Each of these subarrays will go through the same process:

Pick a pivot
Partition the section
Lock the pivot
Recurse again

Eventually, every element gets locked into place, one pivot at a time. When all recursive calls finish, the array is fully sorted - and we didn’t need any extra arrays to do it.

Step 4: When Does the Recursion Stop?

Like any recursive function, Quick Sort needs a condition to stop calling itself. That’s called the base case.

We stop recursing when the slice of the array we’re working on has zero or one element - because that’s already sorted by definition.

In code, it usually looks something like this:

if (start >= end) return;

This means:

If there’s nothing to sort (start === end)
Or if the subarray is empty (start > end)

We just return without doing anything. That’s how the recursion eventually stops: when all the tiny pieces have been handled.

Is Quick Sort Stable?

No, Quick Sort is not a stable sorting algorithm. Stability in sorting algorithms means that the relative order of equal elements is preserved after sorting. Quick Sort can change the relative positions of equal elements during the partitioning process.

Consider this example: if you have an array [3a, 1, 3b, 2] where 3a and 3b have the same value but different origins, Quick Sort might produce [1, 2, 3b, 3a], changing their original relative order.

Quick Sort is unstable because during partitioning, elements are moved based on their comparison with the pivot, not their original positions. Elements can be swapped across long distances in the array, potentially crossing over equal elements, and the algorithm prioritizes efficiency over maintaining the relative order of equal elements.

When stability matters - like sorting complex objects where secondary sort orders must be preserved, database operations where record order significance exists, or multi-level sorting scenarios - you might want to consider using Merge Sort, which maintains stability while offering O(n log n) performance.

Time and Space Complexity Analysis

Quick Sort's performance characteristics vary significantly based on pivot selection and input data:

Time Complexity:
- Best Case: O(n log n) - when the pivot consistently divides the array into roughly equal halves
- Average Case: O(n log n) - for randomly distributed data
- Worst Case: O(n²) - when the pivot is always the smallest or largest element (like with already sorted arrays)
Space Complexity: O(log n) - for the recursion stack in the average case, but can degrade to O(n) in the worst case

The key insight is that Quick Sort's performance heavily depends on how well the pivot divides the array. Good pivot selection leads to balanced partitions and optimal performance, while poor pivot selection can cause the algorithm to degrade significantly.

Advantages and Disadvantages of Quick Sort

Advantages:

Excellent average-case performance of O(n log n)
In-place sorting with minimal memory overhead
Cache-efficient due to good locality of reference
Widely implemented in standard libraries
Generally faster than Merge Sort for in-memory sorting
Easily parallelizable

Disadvantages:

Unstable sorting algorithm (doesn't preserve relative order of equal elements)
Worst-case time complexity of O(n²)
Performance varies significantly with input data and pivot selection
Not suitable for scenarios requiring guaranteed O(n log n) performance
Can cause stack overflow on very large inputs due to deep recursion

When to Use Quick Sort

General-purpose sorting: When you need efficient sorting for most datasets
Memory-constrained environments: Where in-place sorting is valuable
Performance-critical applications: Where average-case performance matters more than worst-case guarantees
Large datasets: Where cache-friendly behavior provides benefits
When stability isn't required: Perfect for scenarios where maintaining relative order of equal elements doesn't matter

When NOT to Use Quick Sort

When you need guaranteed O(n log n) performance (use Merge Sort instead)
When sorting stability is required
For small arrays (simple algorithms like Insertion Sort might be more efficient)
In adversarial environments where worst-case performance could be exploited

Practical Applications and Use Cases

Many programming languages use optimized versions of Quick Sort in their built-in sorting functions. Database systems employ it for sorting intermediate results during query execution, and operating systems use it for file system operations like directory listings. In graphics programming, it's commonly used for sorting objects by depth for rendering operations. Data analytics platforms leverage Quick Sort for processing large datasets where average-case performance is more important than worst-case guarantees, and gaming applications use it for sorting game objects, leaderboards, and real-time data where performance is critical.

Conclusion

Quick Sort is a classic example of the “divide and conquer” strategy in action. It stands out for its efficiency and in-place sorting, especially when memory is limited and average-case performance matters.

That said, it’s not always the safest pick. Its worst-case performance and lack of stability can be dealbreakers in certain cases. But if you understand how it works, particularly how partitioning and pivot placement drive the recursion - you’ll not only be able to implement it confidently, but also gain a deeper understanding of algorithm design in general.

A Voyage through Algorithms using Javascript - Merge Sort

Şahin Arslan — Thu, 06 Mar 2025 23:32:21 +0000

What is Merge Sort?

Merge Sort is a classic "divide and conquer" algorithm in computer science that breaks down a problem into smaller, more manageable parts. Unlike Bubble Sort and Insertion Sort, which slow down as the input size grows, Merge Sort maintains O(n log n) time complexity and handles larger datasets efficiently.

One of its key advantages is that it’s a stable sorting algorithm, meaning equal elements keep their original order. This can be useful in scenarios where stability matters, such as when sorting database records or ordered datasets.

A Voyage through Algorithms using Javascript - Recursion

How Merge Sort Works

Merge Sort follows a clean, recursive approach:

Divide: Split the array into two halves, creating smaller and smaller subarrays.
Conquer: Recursively sort each subarray.
Combine: Merge the sorted subarrays back together to form a single sorted array.

Think of it this way: we shatter an array to pieces until each element becomes precisely a mini-array containing just that element, then with recursion we build it up again with a touch of comparison. The beauty of Merge Sort lies in its elegant process - first breaking down the problem completely, then building up the solution by merging sorted pieces back together.

Here's a visualization to make this clearer:

Modified (speed up) from Swfung8, licensed under CC BY-SA 3.0.

Implementing Merge Sort in JavaScript

Let's examine the implementation of Merge Sort in JavaScript, with detailed comments explaining each part:

const nums = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4];

function mergeSort(array) {
  /*
    Recursion exit condition: when there is only one item in the list, return the array.
    This is our base case - a single element array is already sorted.
    Each element in the array eventually ends up as a single element array: [99], [44], etc.
  */
  if (array.length === 1) {
    return array;
  }

  let left = [];
  let right = [];

  // Math.floor is used for a balanced split, making left <= right when odd-length.
  // This keeps recursion depth even, preventing unnecessary imbalance.
  let mid = Math.floor(array.length / 2);

  // Split array into left and right portions:
  for (let i = 0; i < mid; i++) {
    left.push(array[i]);
  }
  for (let i = mid; i < array.length; i++) {
    right.push(array[i]);
  }

  // Recursively sort both halves, then merge them
  // The || [] ensures we always pass an array even in edge cases
  // This prevents "Cannot read properties of undefined" errors
  return merge(mergeSort(left) || [], mergeSort(right) || []);
}

function merge(left, right) {
  // This function merges two arrays while keeping elements in order
  const mergedArr = [];

  // Use index pointers instead of shift() to maintain O(n) efficiency
  // shift() would cause O(n²) behavior due to array reindexing
  let i = 0; // index for left array
  let j = 0; // index for right array

  // Compare elements from both arrays and add the smaller one to result
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      mergedArr.push(left[i]);
      i++;
    } else {
      mergedArr.push(right[j]);
      j++;
    }
  }

  // Add any remaining elements from the left array
  // This triggers only when right array is exhausted but left still has elements
  while (i < left.length) {
    mergedArr.push(left[i]);
    i++;
  }

  // Add any remaining elements from the right array
  // This triggers only when left array is exhausted but right still has elements
  while (j < right.length) {
    mergedArr.push(right[j]);
    j++;
  }

  return mergedArr;
}

const answer = mergeSort(nums);
console.log("answer:", answer);
// Output: [1, 2, 4, 5, 6, 44, 63, 87, 99, 283]

As we can see from the implementation above, Merge Sort consists of two key functions:

The mergeSort function, which recursively splits the array into smaller parts until each subarray contains a single element.
The merge function, which compares elements from two sorted subarrays and merges them back into a single sorted array.

This separation of concerns makes the algorithm both elegant and powerful. At first, it can be overwhelming to follow what is happening and why it is happening. But there's more to Merge Sort than meets the eye. Let's look into some key implementation details that can help us to have a better mental model for understanding it's inner mechanics.

Key Implementation details for Merge Sort

Many explanations cover the basic mechanics of merge sort, but there are several technical aspects worth examining more closely for a complete understanding.

The Math.floor() Decision Point When Splitting Arrays

One detail that is often glossed over is the choice between Math.floor(), Math.ceil(), or regular integer division when splitting arrays. This decision significantly impacts algorithm behavior.

Using Math.floor() means that when the array length is odd, the left side gets one fewer element than the right. For example, with an array of length 5:

Math.floor(5/2) = 2, so left gets indices [0, 1] and right gets [2, 3, 4]

This creates a balanced recursion tree, which drives optimal performance. If we used Math.ceil(), we'd get an unbalanced split, potentially causing deeper recursion on one side and degrading performance.

Common Edge Cases

One error that can appear during studying Merge Sort might look like this:

TypeError: Cannot read properties of undefined (reading 'length')

This occurs because in certain edge cases, mergeSort(left) or mergeSort(right) might return undefined. A simple solution adds a failsafe:

return merge(mergeSort(left) || [], mergeSort(right) || []);

The || [] guarantees an array always reaches the merge function and eliminates the undefined length check errors.

Avoiding the O(n²) Performance Trap

When working with large amounts of data, certain built-in methods can introduce hidden performance costs. One common pitfall is using shift() to extract elements:

while (left.length && right.length) {
  mergedArr.push(left[0] < right[0] ? left.shift() : right.shift());
}

This approach has a serious flaw: shift() runs at O(n) complexity because it reindexes the entire array after each operation. When performed repeatedly throughout the sorting process, this creates O(n²) behavior, reducing Merge Sort's efficiency.

While using methods like slice() is convenient to simplify array splitting, they come with their own time and space complexity. Being mindful of how built-in functions operate can help avoid unnecessary overhead.

A more efficient approach for merging uses index pointers (i and j) to maintain O(n) complexity:

let i = 0
let j = 0;
while (i < left.length && j < right.length) {
  if (left[i] < right[j]) {
    mergedArr.push(left[i]);
    i++;
  } else {
    mergedArr.push(right[j]);
    j++;
  }
}

Time and Space Complexity Analysis

Merge Sort's performance characteristics are as follows:

Time Complexity:
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n log n)

This consistent performance across all scenarios makes Merge Sort highly reliable, unlike unstable sorting algorithms which can degrade in certain cases.

Space Complexity: O(n)

Merge Sort requires additional memory proportional to the input size. This is due to the creation of new arrays during the merge process.

Advantages and Disadvantages of Merge Sort

Advantages:

Predictable O(n log n) performance regardless of input data
Stable sorting (maintains relative order of equal elements)
Well-suited for linked lists and external sorting

Disadvantages:

O(n) extra space requirement
Slightly slower than Quicksort for in-memory sorting of arrays
Overkill for small arrays (where simpler algorithms might perform better)

When to Use Merge Sort

When you need stable sorting
When dealing with linked lists (Merge Sort is particularly efficient for linked lists)
When worst-case performance matters (unlike Quicksort, which can degrade to O(n²))
For external sorting, where data doesn't fit in memory

Practical Applications and Use Cases

Database systems: When sorting large datasets that don't fit in memory
External sorting: Used in systems that need to sort data stored on disk
Stable sorting requirements: When order of equal elements matters
Parallel computing: Merge Sort is easily parallelizable

Conclusion

Merge Sort is one of the most well-known examples of the "divide and conquer" approach, which powers many efficient algorithms. Even though it requires more memory than some sorting algorithms, its consistent performance and stability make it a solid choice for many applications.

Merge Sort might not be the go-to choice for every sorting need (especially with small arrays or when memory is constrained), understanding it deepens your algorithmic thinking and prepares you for dealing with more complex computational problems.

A Voyage through Algorithms using Javascript - Insertion Sort

Şahin Arslan — Sat, 12 Oct 2024 15:47:04 +0000

What is Insertion Sort?

Insertion Sort is another fundamental sorting algorithm in computer science. It builds the final sorted array one item at a time. It's much like sorting a hand of playing cards - you pick up cards one by one and insert each into its proper position among the cards you've already sorted.

How Insertion Sort Works

Insertion Sort iterates through the array, growing the sorted portion with each iteration. For each element, it compares it with the already sorted elements, moving them up until it finds the correct position to insert the current element.

Here's a step-by-step breakdown:

Start with the second element (index 1) as the "current" element.
Compare the current element with the one before it.
If the current element is smaller, compare it with the elements before. Move the greater elements up to make space for the swapped element.
Repeat steps 2-3 until the whole array is sorted.

Visualization of Insertion Sort:

Recorded gif from https://visualgo.net/en/sorting

Implementing Insertion Sort in JavaScript

Let's take a look at the implementation of Insertion Sort in JavaScript, with detailed comments explaining each part:

function insertionSort(arr) {
  // Start from the second element (index 1)
  // We assume the first element is already sorted
  for (let i = 1; i < arr.length; i++) {
    // Store the current element we're trying to insert into the sorted portion
    let currentElement = arr[i];
    // Define the starting index of lookup (this is the last index of sorted portion of array)
    let j = j - 1;
    // Move elements of arr[0..i-1] that are greater than currentElement
    // to one position ahead of their current position
    while (j >= 0 && arr[j] > currentElement) {
      // Shift element to the right
      arr[j + 1] = arr[j];
      j--;
    }
    // We've found the correct position for currentElement (at j + 1), insert it:
    arr[j + 1] = currentElement;
  }

  // The array is now sorted in-place:
  return arr;
}

Key Points:

Two-Directional Process: Insertion Sort operates through a forward-moving outer loop and a backward-looking inner loop, creating a back-and-forth movement that forms the core of the algorithm.
Forward Scan (Outer Loop):

   for (let i = 1; i < arr.length; i++)

Moves forward through the array, selecting one unsorted element (currentElement = arr[i]) at a time.

Backward Insert (Inner Loop):

   while (j >= 0 && arr[j] > currentElement)

Looks backward into the sorted portion, shifting larger elements right (arr[j + 1] = arr[j]) to make room for the current element.

Element Insertion:

   arr[j + 1] = currentElement;

Inserts the current element into its correct position, growing the sorted portion.

In-Place and Stable Sorting: Modifies the original array directly, maintaining the relative order of equal elements.

Insertion Sort builds the final sorted array one item at a time, mimicking how you'd sort a hand of cards. It repeatedly selects a card (element) from the unsorted portion and inserts it into its correct position among the sorted cards, shifting larger cards as needed. This intuitive process makes Insertion Sort efficient for small or nearly-sorted datasets.

Is Insertion Sort Stable?

Yes, Insertion Sort is a stable sorting algorithm. Stability in sorting algorithms means that the relative order of equal elements is preserved after sorting. Insertion Sort achieves this naturally due to its method of operation:

Preserving Order: When inserting an element into the sorted portion, Insertion Sort only shifts elements that are strictly greater than the current element. This means that if there are multiple elements with the same value, their relative order will be maintained.
No Unnecessary Swaps: Unlike some other sorting algorithms that might swap equal elements, Insertion Sort only moves an element when necessary. This characteristic ensures that equal elements remain in their original relative positions.
Left-to-Right Processing: By processing the array from left to right and inserting each element into its correct position among the already-sorted elements, Insertion Sort naturally maintains the original order of equal elements.

The stability of Insertion Sort can be particularly useful when sorting complex data structures where maintaining the original order of equal elements is important. For example, when sorting a list of students first by grade and then by name, a stable sort would ensure that students with the same grade remain in alphabetical order by name.

This stability is an inherent property of the basic Insertion Sort algorithm and doesn't require any additional modifications or overhead to achieve, making it a naturally stable sorting method.

Time and Space Complexity Analysis

Insertion Sort's performance characteristics are as follows:

Time Complexity:
- Best Case: O(n) - when the array is already sorted
- Average Case: O(n^2)
- Worst Case: O(n^2) - when the array is reverse sorted
Space Complexity: O(1) - Insertion Sort is an in-place sorting algorithm

Unlike Selection Sort, Insertion Sort can perform well on nearly sorted arrays, achieving close to linear time complexity in such cases.

Advantages and Disadvantages of Insertion Sort

Advantages:

Simple to implement and understand
Efficient for small to medium-sized datasets
Adaptive - performs well on nearly sorted arrays
Stable - maintains relative order of equal elements
In-place sorting (O(1) space)
Suitable for online sorting scenarios

Disadvantages:

Inefficient for large datasets (O(n^2) in average and worst cases)
Performance degrades quickly as input size increases

When to Use Insertion Sort

Small to medium-sized datasets (generally up to a few hundred elements)
Nearly sorted data
Online sorting scenarios where elements are received and sorted incrementally
As a subroutine in more complex algorithms (e.g., Quicksort for small partitions)

Practical Applications and Use Cases

Standard library implementations: Often used for small arrays or as part of hybrid sorting algorithms
Database operations: Sorting small sets of records
Embedded systems: Suitable for systems with limited resources due to its simplicity and low memory overhead
Real-time data processing: Maintaining sorted order as data is received

Conclusion

Insertion Sort, despite its limitations for large datasets, offers valuable advantages in specific scenarios. Its intuitive nature, resembling how we might sort cards by hand, makes it an excellent educational tool for understanding sorting algorithms.

Key takeaways:

Best-case time complexity of O(n) for nearly sorted data
Stable, in-place, and adaptive sorting algorithm
Efficient for small datasets and online sorting
Often incorporated into hybrid sorting strategies

While not suitable for large-scale sorting tasks, Insertion Sort's principles are often applied in more sophisticated methods. Its simplicity and efficiency in certain scenarios make it a valuable addition to a programmer's algorithmic toolkit.

The choice of sorting algorithm ultimately depends on your specific use case, data characteristics, and system constraints. Understanding Insertion Sort provides insights into algorithm design trade-offs and lays a foundation for exploring more advanced sorting techniques.

A Voyage through Algorithms using Javascript - Selection Sort

Şahin Arslan — Sun, 08 Sep 2024 19:45:32 +0000

What is Selection Sort?

Selection Sort is one of the elementary sorting algorithms in computer science. It divides the input list into two parts: a sorted portion at the left end and an unsorted portion at the right end. The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion and moves it to the sorted portion.

How Selection Sort Works

Selection Sort works by iterating through the array, finding the minimum element in the unsorted portion, and swapping it with the first element of the unsorted portion. This process is repeated until the entire array is sorted.

Here's a step-by-step breakdown:

Start with the first element as the "current" element.
Search through the rest of the array to find the smallest element.
If a smaller element is found, swap it with the "current" element.
Move to the next element and repeat steps 2-3 until you reach the end of the array.
The array is sorted when you've gone through all elements.

Visualization of Selection Sort:

Recorded gif from https://visualgo.net/en/sorting

Implementing Selection Sort in JavaScript

Let's take a look at the implementation of Selection Sort in JavaScript, with detailed comments explaining each part:

function selectionSort(arr) {
  // Cache the array length to avoid recalculating it in every loop iteration
  // This is a small optimization that can be beneficial for larger arrays
  const arrayLength = arr.length;
  let indexOfMinimum;

  // Outer loop: iterates through the array, establishing the boundary between sorted and unsorted portions
  // We only need to go up to the second-to-last element because the last element will already be in place
  for (let currentIndex = 0; currentIndex < arrayLength - 1; currentIndex++) {
    // Assume the current index holds the minimum value
    indexOfMinimum = currentIndex;

    // Inner loop: searches for the minimum element in the unsorted portion of the array
    // Start from the element next to currentIndex, as elements before currentIndex are already sorted
    for (let searchIndex = currentIndex + 1; searchIndex < arrayLength; searchIndex++) {
      // If we find a smaller element, update indexOfMinimum
      if (arr[searchIndex] < arr[indexOfMinimum]) {
        indexOfMinimum = searchIndex;
      }
    }

    // After inner loop, indexOfMinimum holds the index of the smallest element in the unsorted portion

    // Swap the found minimum element with the first element of the unsorted portion
    // Only swap if we found a smaller element (indexOfMinimum changed)
    if (indexOfMinimum !== currentIndex) {
      // Use destructuring assignment for a clean swap operation
      // This is a shorthand way to swap two array elements without a temporary variable
      [arr[currentIndex], arr[indexOfMinimum]] = [arr[indexOfMinimum], arr[currentIndex]];
    }
  }

  // The array is now sorted in-place
  return arr;
}

Key Points:

Outer Loop and Passes: The outer loop for (let currentIndex = 0; currentIndex < arrayLength - 1; currentIndex++) manages the "passes" through the array. Each iteration of this loop represents one complete pass, where we find the smallest element in the unsorted portion and place it in its correct position.
Inner Loop: Within each pass, the inner loop for (let searchIndex = currentIndex + 1; searchIndex < arrayLength; searchIndex++) searches for the minimum element in the unsorted portion of the array.
Swap After Inner Loop: Importantly, the swap operation occurs after the inner loop completes. This means we only perform one swap per pass, moving the found minimum element to its correct position.
Pass Completion: A pass is considered complete when the inner loop finishes and the swap (if necessary) is performed. The algorithm then moves to the next pass by incrementing currentIndex in the outer loop.
Optimization: We only swap if a new minimum is found (if (indexOfMinimum !== currentIndex)), avoiding unnecessary operations.

Most important point to understand Selection Sort is figuring out how it manages its passes:

Each pass (outer loop iteration) finds the smallest element in the unsorted portion.
The inner loop handles the comparison part of each pass.
The swap after the inner loop finalizes each pass by placing the found minimum in its correct position.
The process repeats, with the sorted portion growing by one element after each pass.

In other words, we don't need to manually track when each pass ends - the nested loop structure naturally handles this for us.

Making Selection Sort Stable

While our basic implementation of Selection Sort works well, it has one potential drawback: it's not stable. But what does this mean, and why might it matter?

Understanding Stability in Sorting

A stable sorting algorithm preserves the relative order of equal elements. This becomes important when sorting complex data or when you need to maintain the original order of equivalent items.

For example, consider this array: [4A, 3, 2, 4B, 1] (where 4A and 4B represent different elements with the same value 4).

Our current Selection Sort might produce: [1, 2, 3, 4B, 4A]

Notice how 4B and 4A swapped positions. In some scenarios, this could be problematic.

Implementing Stable Selection Sort

We can modify our algorithm to make it stable. Instead of swapping elements, we'll shift elements and insert the minimum value in its correct position. Here's how:

function stableSelectionSort(arr) {
  // Cache the array length to avoid recalculating it in every loop iteration
  const arrayLength = arr.length;

  // Outer loop: iterates through the array, establishing the boundary between sorted and unsorted portions
  // We only need to go up to the second-to-last element because the last element will already be in place
  for (let currentIndex = 0; currentIndex < arrayLength - 1; currentIndex++) {
    // Assume the current index holds the minimum value
    let indexOfMinimum = currentIndex;

    // Inner loop: searches for the minimum element in the unsorted portion of the array
    // Start from the element next to currentIndex, as elements before currentIndex are already sorted
    for (let searchIndex = currentIndex + 1; searchIndex < arrayLength; searchIndex++) {
      // If we find a smaller element, update indexOfMinimum
      if (arr[searchIndex] < arr[indexOfMinimum]) {
        indexOfMinimum = searchIndex;
      }
    }

    // After inner loop, indexOfMinimum holds the index of the smallest element in the unsorted portion

    // If the minimum element is not already in its correct position
    if (indexOfMinimum !== currentIndex) {
      // Store the minimum value
      const minimumValue = arr[indexOfMinimum];

      // Shift all elements between currentIndex and indexOfMinimum one position to the right
      // This maintains the relative order of equal elements, ensuring stability
      for (let shiftIndex = indexOfMinimum; shiftIndex > currentIndex; shiftIndex--) {
        arr[shiftIndex] = arr[shiftIndex - 1];
      }

      // Place the minimum value in its correct position
      arr[currentIndex] = minimumValue;
    }
  }

  // The array is now sorted in-place and in a stable manner
  return arr;
}

Key Points for Stable Selection Sort:

Outer Loop and Passes: Similar to the classic version, the outer loop
for (let currentIndex = 0; currentIndex < arrayLength - 1; currentIndex++)
manages the passes through the array. Each pass finds the smallest element
in the unsorted portion and places it in its correct position.
Inner Loop: The inner loop
for (let searchIndex = currentIndex + 1; searchIndex < arrayLength; searchIndex++)
searches for the minimum element in the unsorted portion of the array,
just like in the classic version.
Shifting Instead of Swapping: The key difference from the classic version
is that after finding the minimum element, we don't swap it directly. Instead,
we shift all elements between the current position and the minimum element's
position one step to the right. This preserves the relative order of equal elements.
Insertion After Shifting: After shifting, we insert the minimum element
into its correct position. This approach ensures stability by maintaining
the original order of equal elements.
Additional Loop for Shifting: The stable version introduces an additional
loop for the shifting operation:
for (let shiftIndex = indexOfMinimum; shiftIndex > currentIndex; shiftIndex--).
This loop moves elements to create space for the minimum element.
Preserving Stability: By shifting elements instead of swapping, we ensure
that elements with equal values maintain their relative positions, making
the sort stable.
Trade-off: The stable version potentially performs more write operations
due to the shifting process, which can impact performance for larger datasets.

Most important point to understand Stable Selection Sort:

The algorithm still selects the minimum element in each pass, but instead of swapping, it performs a series of shifts to insert the minimum element in its correct position.
This shifting process is what guarantees stability, ensuring that equal elements maintain their relative order from the input array.
The trade-off for stability is potentially more write operations, which can affect performance on larger datasets compared to the classic version.

In essence, stable selection sort maintains the overall structure of classic
selection sort but modifies the element placement strategy to ensure stability
at the cost of some additional operations.

Time and Space Complexity Analysis

Selection Sort's performance characteristics are as follows:

Time Complexity:
- Best Case: O(n^2)
- Average Case: O(n^2)
- Worst Case: O(n^2)
Space Complexity: O(1) - Selection Sort is an in-place sorting algorithm, requiring only a constant amount of additional memory.

Unlike Bubble Sort, Selection Sort's time complexity remains quadratic even in the best case scenario. This is because it always scans the entire unsorted portion of the array to find the minimum element, regardless of whether the array is already sorted or not.

Advantages and Disadvantages of Selection Sort

Advantages:

Simple to understand and implement
In-place sorting (O(1) space)
Performs well on small lists
Minimizes the number of swaps (at most n swaps where n is the number of elements)

Disadvantages:

Inefficient for large datasets (O(n^2))
Not adaptive (doesn't take advantage of existing order in the array)
Not stable in its basic form (may change the relative order of equal elements)

When to Use Selection Sort

Educational purposes: Its simplicity makes it excellent for teaching basic algorithm concepts.
Small datasets: For very small arrays, the performance difference compared to complex algorithms may be negligible.
Memory-constrained environments: Its in-place nature can be advantageous in extremely memory-constrained scenarios.
When minimizing writes is important: Selection Sort performs the minimum number of swaps possible (at most n).

Practical Applications and Use Cases

While Selection Sort, like Bubble Sort, isn't typically used in production environments for large-scale applications, it can still find use in certain scenarios:

Educational tools: It's often used to introduce sorting algorithms and algorithm analysis in computer science education.
Embedded systems: In systems with very limited memory, its in-place sorting can be advantageous.
Small datasets: For sorting small lists (e.g., less than 50 elements), its simplicity might outweigh the performance benefits of more complex algorithms.
Minimizing writes: In scenarios where writing to memory is significantly more expensive than reading, Selection Sort's minimal number of swaps can be beneficial.

Conclusion

Selection Sort, despite its inefficiencies with large datasets, offers valuable insights into the world of sorting algorithms and algorithm analysis. Its straightforward approach makes it an excellent teaching tool for beginners in computer science.

Key takeaways are:

It's simple to understand and implement.
It has a consistent time complexity of O(n^2), making it inefficient for large datasets.
It's an in-place sorting algorithm, but not stable in its basic form (may change the relative order of equal elements).
It performs well when minimizing the number of swaps is important.
It's primarily used for educational purposes and in scenarios with very small datasets or limited memory.

While you're unlikely to use Selection Sort in production code for large-scale applications, understanding its mechanics and trade-offs is helpful for developing a comprehensive grasp of sorting algorithms. As we continue our voyage through algorithms, we'll encounter more sophisticated sorting methods that build upon these fundamental concepts.

The best algorithm for a given task depends on the specific requirements, constraints, and characteristics of your data. Even though Selection Sort is not a typical algorithm you'd use for most cases, it still has its place as a stepping stone to give you a better perspective for more advanced concepts.

A Voyage through Algorithms using Javascript - Bubble Sort

Şahin Arslan — Sun, 28 Jul 2024 15:53:34 +0000

What is Bubble Sort?

Bubble Sort is one of the simplest sorting algorithms in computer science. Named for the way smaller elements "bubble" to the top of the list with each iteration, it's an excellent tool for teaching the basics of sorting algorithms. While not the most efficient for large datasets, its simplicity makes it a great starting point for understanding how sorting algorithms work.

How Bubble Sort Works

Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they're in the wrong order. This process is repeated until no more swaps are needed, indicating that the list is sorted.

Here's a step-by-step breakdown:

Start with the first element in the array.
Compare it with the next element.
If the first element is greater than the second, swap them.
Move to the next element and repeat steps 2-3 until you reach the end of the array.
If any swaps were made, repeat the process from the beginning.
If no swaps were made in a full pass, the array is sorted.

Let's visualize this process:

Recorded gif from https://visualgo.net/en/sorting

Implementing Bubble Sort in JavaScript

Let's examine three implementations of Bubble Sort in JavaScript, each with increasing levels of optimization.

Basic Implementation (v1)

function bubbleSort(list) {
  // Outer loop: iterate through the entire list
  for (let i = 0; i < list.length - 1; i++) {
    // Inner loop: compare adjacent elements
    for (let j = 0; j < list.length - 1; j++) {
      // If the current element is greater than the next one
      if (list[j] > list[j + 1]) {
        // Swap the elements using destructuring assignment
        [list[j], list[j + 1]] = [list[j + 1], list[j]];
      }
    }
  }
  // Return the sorted list
  return list;
}

This basic implementation uses nested loops to compare and swap adjacent elements. The outer loop ensures we make enough passes through the array, while the inner loop performs the comparisons and swaps.

Optimized Implementation (v2)

function bubbleSort(list) {
  // Outer loop: iterate through the entire list
  for (let i = 0; i < list.length - 1; i++) {
    // Flag to check if any swaps occurred in this pass
    let swapped = false;
    // Inner loop: compare adjacent elements
    for (let j = 0; j < list.length - 1; j++) {
      // If the current element is greater than the next one
      if (list[j] > list[j + 1]) {
        // Swap the elements using destructuring assignment
        [list[j], list[j + 1]] = [list[j + 1], list[j]];
        // Set the swapped flag to true
        swapped = true;
      }
    }    
    // If no swaps occurred in this pass, the list is sorted
    if (!swapped) {
      break; // Exit the outer loop early
    }
  }
  // Return the sorted list
  return list;
}

This version introduces a swapped flag to check if any swaps were made in a pass. If no swaps occur, the list is already sorted, and we can break out of the loop early.

Most Optimized Implementation (v3)

function bubbleSort(list) {
  // Outer loop: iterate through the entire list
  for (let i = 0; i < list.length - 1; i++) {
    // Flag to check if any swaps occurred in this pass
    let swapped = false;
    // Inner loop: compare adjacent elements
    // Note: We reduce the upper bound by i in each pass
    for (let j = 0; j < list.length - 1 - i; j++) {
      // If the current element is greater than the next one
      if (list[j] > list[j + 1]) {
        // Swap the elements using destructuring assignment
        [list[j], list[j + 1]] = [list[j + 1], list[j]];
        // Set the swapped flag to true
        swapped = true;
      }
    }    
    // If no swaps occurred in this pass, the list is sorted
    if (!swapped) {
      break; // Exit the outer loop early
    }
  }
  // Return the sorted list
  return list;
}

This final optimization reduces the range of the inner loop by i in each pass. This is because after each pass, the largest unsorted element "bubbles up" to its correct position at the end of the array.

Time and Space Complexity Analysis

Bubble Sort's performance characteristics are as follows:

Time Complexity:
- Best Case: O(n) - when the array is already sorted
- Average Case: O(n^2)
- Worst Case: O(n^2) - when the array is in reverse order
Space Complexity: O(1) - Bubble Sort is an in-place sorting algorithm, requiring only a constant amount of additional memory.

Compared to more advanced algorithms like Quick Sort (average O(n log n)) or Merge Sort (O(n log n)), Bubble Sort's quadratic time complexity makes it inefficient for large datasets.

Advantages and Disadvantages of Bubble Sort

Advantages:

Simple to understand and implement
In-place sorting (O(1) space)
Stable sorting algorithm
Can detect already sorted lists

Disadvantages:

Inefficient for large datasets (O(n^2))
Poor performance on nearly sorted data
Excessive swapping operations

When to Use Bubble Sort

Educational purposes: Its simplicity makes it excellent for teaching basic algorithm concepts.
Small datasets: For very small arrays, the performance difference compared to complex algorithms may be negligible.
Nearly sorted data: With the optimized version, it can be reasonably efficient on almost sorted lists.
Limited memory environments: Its in-place nature can be advantageous in extremely memory-constrained scenarios.

Cocktail Sort: An Improved Variation

Cocktail Sort, also known as Cocktail Shake Sort or Bidirectional Bubble Sort, is an improved version of Bubble Sort. It traverses the list in both directions, helping to move elements to their correct positions more efficiently.

How Cocktail Sort Works

Start with the first element and move towards the end, swapping adjacent elements if they're in the wrong order.
When you reach the end, start from the second-to-last element and move towards the beginning, again swapping elements as needed.
Repeat this process, narrowing the range of elements to check with each pass, until no swaps are needed.

Cocktail Sort is particularly useful in cases where the array has elements that are initially large at the beginning and small at the end, as it can reduce the total number of passes needed compared to traditional Bubble Sort.

Here's a visualization of Cocktail Sort:

Visual from Wikipedia: https://en.wikipedia.org/wiki/Cocktail_shaker_sort

Cocktail Sort implementation in Javascript

function cocktailSort(list) {
  let swapped;

  // The do...while loop ensures the sorting continues until no swaps are needed
  do {
    // Reset the swapped flag at the beginning of each complete iteration
    swapped = false;

    // First pass: left to right (like standard bubble sort)
    for (let i = 0; i < list.length - 1; i++) {
      // If the current element is greater than the next, swap them
      if (list[i] > list[i + 1]) {
        [list[i], list[i + 1]] = [list[i + 1], list[i]];
        // Mark that a swap occurred
        swapped = true;
      }
    }

    // If no swaps occurred in the first pass, the array is sorted
    if (!swapped) {
      break; // Exit the do...while loop early
    }

    // Reset the swapped flag for the second pass
    swapped = false;

    // Second pass: right to left (this is what makes it "cocktail" sort)
    for (let i = list.length - 2; i >= 0; i--) {
      // If the current element is greater than the next, swap them
      if (list[i] > list[i + 1]) {
        [list[i], list[i + 1]] = [list[i + 1], list[i]];
        // Mark that a swap occurred
        swapped = true;
      }
    }

    // The loop will continue if any swaps occurred in either pass
  } while (swapped);

  // Return the sorted list
  return list;
}

This implementation alternates between forward and backward passes through the list, potentially reducing the number of iterations needed to sort the array.

Practical Applications and Use Cases

While Bubble Sort isn't typically used in production environments for large-scale applications, it can still find use in certain scenarios:

Educational tools: It's often used to introduce sorting algorithms and algorithm analysis in computer science education.
Embedded systems: In systems with very limited memory, its in-place sorting can be advantageous.
Small datasets: For sorting small lists (e.g., less than 50 elements), its simplicity might outweigh the performance benefits of more complex algorithms.
Nearly sorted data: If data is known to be almost sorted, an optimized Bubble Sort can be reasonably efficient.
Sorting stability requirement: When a stable sort is needed and simplicity is preferred over efficiency, Bubble Sort can be a straightforward choice.

Conclusion

Bubble Sort, despite its inefficiencies with large datasets, offers valuable insights into the world of sorting algorithms and algorithm analysis. Its straightforward approach makes it an excellent teaching tool for beginners in computer science.

Key takeaways are:

It's simple to understand and implement.
It has a time complexity of O(n^2), making it inefficient for large datasets.
It's an in-place and stable sorting algorithm.
Optimizations can improve its performance, especially for nearly sorted data.
It's primarily used for educational purposes and in scenarios with very small datasets or limited memory.

While you're unlikely to use Bubble Sort in production code for large-scale applications, the principles behind it are fundamental to many algorithms. The process of optimizing Bubble Sort teaches valuable lessons about algorithm improvement, serving as a stepping stone to more advanced computational problem-solving.

When it comes to algorithms, there's rarely a one-size-fits-all solution. The best algorithm for a given task depends on the specific requirements, constraints, and characteristics of your data. Bubble Sort, with all its limitations, still has its place in this diverse algorithmic ecosystem.

A Voyage through Algorithms using Javascript - Recursion

Şahin Arslan — Sun, 09 Jun 2024 21:02:21 +0000

What is Recursion?

Recursion is a powerful and elegant technique that forms the backbone of many algorithms. It allows a function to call itself repeatedly until a specific condition is met, enabling the solution of complex problems by breaking them down into simpler subproblems.

Anatomy of a Recursive function

Every recursive function consists of two essential parts: the base condition and the recursive call.

Base Condition: The base condition is the foundation of a recursive function. It defines the scenario where the function can provide a direct solution without the need for further recursive calls, acting as a termination point to prevent infinite loops. The base condition represents the simplest form of the problem that can be solved immediately.

Recursive Call: The recursive call is where the function invokes itself with a modified version of the original problem. The function approaches the base condition by gradually reducing the problem into smaller, more manageable subproblems. The results of these recursive calls are then combined or processed to yield the final solution.

The cooperation between the base condition and the recursive call is what makes recursion a powerful tool. The base condition ensures that the recursion terminates, while the recursive call allows the function to tackle complex problems by breaking them down into simpler ones.

Here's the general structure of a recursive function:

function recursiveFunction(parameters) {
  if (baseCondition) {
    // Base case: Return a direct solution
    return baseResult;
  } else {
    // Recursive case: Modify parameters for the next recursive call
    const modifiedParameters = ...;
    // Invoke the recursive function with modified parameters
    const recursiveResult = recursiveFunction(modifiedParameters);
    // Process or combine the recursive result
    const finalResult = ...;
    return finalResult;
  }
}

Types of Recursion

Recursion can be classified into different types based on how the recursive calls are made. Let's explore each type with examples, use cases, pros, and cons.

Direct Recursion

In direct recursion, a function calls itself directly within its own body.

Example:

function factorial(n) {
  if (n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

console.log(factorial(5)); // Output: 120

Use cases:

Calculating factorials
Traversing tree-like data structures (e.g., binary trees, file systems)
Implementing recursive algorithms (e.g., Tower of Hanoi, Fibonacci sequence)

Pros:

Simple and intuitive to understand and implement
Suitable for problems with a clear recursive structure

Cons:

Can lead to stack overflow if the recursion depth is too large
May be less efficient compared to iterative solutions for certain problems

Indirect Recursion

Indirect recursion occurs when a function calls another function, which in turn calls the original function directly or indirectly.

Example:

function isEven(n) {
  if (n === 0) {
    return true;
  }
  return isOdd(n - 1);
}

function isOdd(n) {
  if (n === 0) {
    return false;
  }
  return isEven(n - 1);
}

console.log(isEven(4)); // Output: true
console.log(isOdd(5));  // Output: true

Use cases:

Implementing mutually recursive functions (e.g., even/odd, is_palindrome)
Solving problems that can be divided into interrelated subproblems

Pros:

Allows for modular and organized code structure due to each function having a specific role.
Can make the logic more readable and maintainable due to each function handling a distinct part of the problem.

Cons:

Even the modularity and separation of concerns makes it readable at a glance, it can be still harder to understand since it involves multiple functions calling each other. This can make the flow of execution less straightforward compared to direct recursion, where you only deal with a single function calling itself.
It can result in deeper recursion depths since multiple functions are involved in the recursive process. This increases the risk of stack overflow if the recursion goes too deep, as each function call adds a new frame to the call stack.

Tail Recursion

A recursive function is considered tail recursive if the recursive call is the last thing executed by the function. There is no need to keep a record of the previous state – in other words, there's no additional computation after the recursive call returns.

Example:

function sumNumbers(n, accumulator = 0) {
  if (n === 0) {
    return accumulator;
  }
  return sumNumbers(n - 1, accumulator + n);
}

console.log(sumNumbers(5)); // Output: 15

Use cases:

Optimizing recursive algorithms by simplifying the recursive structure to reduce the amount of recursive calls
- Example: A tail-recursive version of the naive implementation of Fibonacci sequence (more details on Optimizing Recursive functions section).
- Tail call optimization (TCO) can also further enhance performance by optimizing these calls at the engine level. In terms of Javascript, TCO is only supported by the Safari engine.
Avoiding stack overflow in languages (or engines) that support tail call optimization

Pros:

Can be optimized by the compiler or interpreter for better performance
Reduces the risk of stack overflow in supported languages / engines

Cons:

Not all programming languages support tail call optimization in the engine level
May require additional parameters or helper functions to maintain the state

Non-Tail Recursion

A recursive function is considered non-tail recursive if the recursive call is not the last thing executed by the function. After returning from the recursive call, there is something left to evaluate (notice the console log after the reversePrint function below).

Example:

function reversePrint(n) {
  if (n === 0) {
    return;
  }
  reversePrint(n - 1);
  console.log(n);
}

reversePrint(5);
// Output:
// 1
// 2
// 3
// 4
// 5

Use cases:

Generating permutations or combinations
Traversing and processing data structures in a post-order manner

Pros:

Allows for post-processing or evaluation after the recursive call
Suitable for problems that require backtracking or post-order traversal

Cons:

Can lead to stack overflow if the recursion depth is too large
May be less efficient compared to tail recursive or iterative solutions

Infinite Recursion and Stack Overflow Errors

It is critical that the recursive calls eventually reach the base condition. Without a well-defined base condition, the function may continue calling itself indefinitely, leading to infinite recursion and a stack overflow error.

Consider the following example of a recursive function without a base condition:

function recursiveGreeting(name) {
  console.log(`Hi ${name}.`);
  recursiveGreeting(name);
}

recursiveGreeting("Mark");

In this case, the recursiveGreeting function lacks a base condition. When invoked with the argument "Mark", it will print "Hi Mark." and then call itself with the same argument. This process will repeat indefinitely, causing an infinite loop. The function will keep printing "Hi Mark." until the call stack reaches its limit, resulting in a stack overflow error:

However, stack overflow errors can also occur in functions with a base condition if the input data is too large. For example, calculating the factorial of a very large number using a simple recursive function without optimization can also lead to a stack overflow due to the excessive depth of recursive calls.

Which brings us to the next topic: to effectively work with recursive functions, it's not only essential to understand the anatomy of recursion but also to comprehend how the call stack operates. The call stack is an "unseen" key element that must be considered when working with recursive problems.

Understanding the Call Stack

The call stack is a fundamental data structure used by Javascript Engine (similarly in many other programming languages) to manage function execution, evaluations, and the program's execution flow "under the hood".

When a script calls a function, Javascript creates a new execution context for that function and pushes it onto the call stack. This execution context includes information such as the function's parameters, local variables, and the location to return to when the function completes. If the function makes further function calls or evaluations, additional execution contexts are pushed onto the stack.

The call stack operates on the principle of "last in, first out" (LIFO), meaning that the last execution context pushed onto the stack is the first one to be popped off when it completes. Javascript continuously executes the code in the execution context at the top of the stack. When a function completes, its execution context is popped off the stack, and the program resumes execution from the previous execution context.

Let's consider a simple example to illustrate how the call stack behaves with non-nested function calls:

Recorded gif from JS Visualizer 9000 tool: https://www.jsv9000.app/

Code:

function one() {
  return 'one';
}

function two() {
  return 'two';
}

function three() {
  return 'three';
}

one();
two();
three();

Here's what happens with the call stack:

one() is called:

one is pushed onto the call stack.
one executes and returns the string 'one'.
one is popped off the call stack.
1. two() is called:
two is pushed onto the call stack.
two executes and returns the string 'two'.
two is popped off the call stack.
1. three() is called:
three is pushed onto the call stack.
three executes and returns the string 'three'.
three is popped off the call stack.

In this scenario, each function call is independent and completes before the next function is called. The call stack never holds more than one function at a time, as each function "comes and goes" in a sequential manner.

Now, let's examine how the call stack handles nested function calls:

Recorded gif from JS Visualizer 9000 tool: https://www.jsv9000.app/

Code:

function one() {
  return two();
}

function two() {
  return three();
}

function three() {
  return 'done!';
}

one();

Here's what happens with the call stack when we're dealing with nested calls:

one() is called:

one is pushed onto the call stack.
one calls two().
1. two() is called by one():
two is pushed onto the call stack on top of one.
two calls three().
1. three() is called by two():
three is pushed onto the call stack on top of two.
three executes and returns the string 'done!'.
three is popped off the call stack.
1. The return value from three() is used by two():
two continues execution, receives the string 'done!', and returns it.
two is popped off the call stack.
1. The return value from two() is used by one():
one continues execution, receives the string 'done!', and returns it.
one is popped off the call stack.

In this case, the call stack holds multiple functions simultaneously due to the nested calls to manage more complex execution flows.

The Call Stack and Recursion:

Recursion relies heavily on the call stack to manage the multiple instances of the recursive function. Each recursive call creates a new frame on the call stack with its own execution context (variables and parameters).

Consider a simple example of a recursive function that counts down from a number:

Recorded gif from JS Visualizer 9000 tool: https://www.jsv9000.app/

Code:

function recursiveCountdown(n) {
  if (n === 0) {
    return;
  }

  return recursiveCountdown(n - 1);
}

recursiveCountdown(4);

Here's what happens in the call stack when we're dealing with this recursive function:

recursiveCountdown(4) is called and pushed onto the stack.
Since n is not 0, it calls recursiveCountdown(3) and pushes it onto the stack.
This process continues, pushing recursiveCountdown(2), recursiveCountdown(1), and recursiveCountdown(0) onto the stack.
When recursiveCountdown(0) is called, the base case is met, and it returns undefined and pops recursiveCountdown(0) off the stack.
The return value (undefined) is passed up to recursiveCountdown(1), which then returns and pops off the stack.
This process continues until recursiveCountdown(4) receives the return value from recursiveCountdown(3) and completes, ultimately clearing the stack.

As you see, even a small operation can fill up the call stack pretty quickly. Therefore it's critical to be cautious of the call stack's size when working with recursion. If the recursion depth becomes too large or if there is no base case to terminate the recursion, the call stack can overflow. This happens when the maximum stack size is exceeded, and the program runs out of memory to store additional execution contexts.

Optimizing Recursive functions

Recursive functions can be powerful and expressive, but they can also suffer from performance issues if not optimized properly. One common problem that arises with recursive functions is redundant calculations, where the same subproblems are solved multiple times. This can lead to exponential time complexity and inefficient use of resources.

Whenever we discuss optimizing an algorithm, we are essentially focusing on improving its time and space complexity. This section assumes that you are at least somewhat familiar with Big O notation. If you need a quick refresher, I recommend starting with the article below and then returning here to continue:

Comprehensive Big O Notation Guide in Plain English, using Javascript

Case study: Fibonacci Sequence Problem

To illustrate this, let's take a look at the famous Fibonacci sequence problem and explore how we can optimize its recursive solution. The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. The sequence starts with 0 and 1, and goes on infinitely:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Naive Recursive Implementation

A straightforward recursive implementation of the Fibonacci sequence can be written as follows:

function fibonacci(n) {
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

In this implementation, the base condition is when n is less than or equal to 1, in which case we simply return n. For any value of n greater than 1, we recursively call the fibonacci function with n - 1 and n - 2 and add their results to obtain the Fibonacci number at position n.

While this implementation is concise and easy to understand, it suffers from a major performance issue. Let's analyze the time complexity of this approach.

Time Complexity: O(2^n)

The time complexity of the naive recursive Fibonacci implementation can be represented by the recurrence relation:

T(n) = T(n-1) + T(n-2) + O(1)

This means that to calculate the Fibonacci number at position n, we need to calculate the Fibonacci numbers at positions n-1 and n-2, and then perform a constant-time operation (addition).

The recursive calls form a binary tree-like structure, where each node represents a function call. The height of this tree is n, and the number of nodes in the tree grows exponentially with n. In fact, the time complexity of this naive recursive approach is exponential, approximately O(2^n). In simpler words, each function is calling 2 functions, those 2 functions are calling 4 functions, and so on...

To understand why, let's look at a small example. Consider the calculation of the 5th Fibonacci number:

fibonacci(5)
  -> fibonacci(4) + fibonacci(3)
    -> (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
      -> ((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) +
         ((fibonacci(1) + fibonacci(0)) + fibonacci(1))
        -> (((fibonacci(1) + fibonacci(0)) + fibonacci(1)) + (1 + 0)) +
           ((1 + 0) + 1)

As we can see, the number of function calls grows exponentially with each increasing value of n. Each function call leads to two more function calls, resulting in a binary tree structure. The number of nodes in this tree is approximately 2^n, leading to an exponential time complexity.

Space Complexity: O(n)

The space complexity of the naive recursive Fibonacci implementation is O(n). This is because the maximum depth of the recursive call stack is proportional to the input value n. Each recursive call adds a new frame to the call stack, consuming additional memory.

In the worst case, when n is large, the recursive calls will reach a depth of n before starting to return. This means that the call stack will contain n frames, each storing the local variables and function call information.

It's important to note that the space complexity is not exponential like the time complexity. While the time complexity grows exponentially with n, the space complexity grows linearly with n due to the linear growth of the call stack.

To summarize:

The time complexity of the naive recursive Fibonacci implementation is O(2^n), which is exponential.
The space complexity is O(n) due to the linear growth of the call stack with respect to the input value n.

Now let's explore different optimization techniques to improve the performance of the recursive Fibonacci function:

1 - Memoization

Memoization is a technique where we store the results of expensive function calls and return the cached result when the same inputs occur again. This optimization can significantly improve the performance of recursive functions by eliminating redundant calculations.

Here's an example of applying memoization to the Fibonacci function:

function fibonacciMemo(n, memo = {}) {
  if (n in memo) {
    return memo[n];
  }
  if (n <= 1) {
    return n;
  }
  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  return memo[n];
}

In this optimized version, we introduce an object memo to store the previously calculated Fibonacci numbers. Before making a recursive call, we check if the result for the current input n is already available in the memo object. If it is, we return the memoized result directly. Otherwise, we proceed with the recursive calls and store the result in the memo object before returning it.

Time Complexity: O(n)

With memoization, each Fibonacci number is calculated only once. The recursive calls are made only for numbers that have not been previously calculated and memoized. This reduces the time complexity from exponential to linear, as there are only n unique subproblems to solve.

Space Complexity: O(n)

The space complexity of the memoized solution is O(n) because the memo object stores the results of each subproblem. In the worst case, the memo object will contain all the Fibonacci numbers from 0 to n.

Use cases:

When the recursive function performs redundant calculations
When the recursive function has overlapping subproblems

Pros:

Eliminates redundant calculations
Significantly improves the time complexity (from exponential to linear)

Cons:

Requires extra space to store the memoized results
May not be suitable for all recursive problems

2 - Tail Call Optimization

Tail call optimization is a technique used by some programming languages / engines to optimize recursive functions. It allows the compiler or interpreter to reuse the same callstack frame for recursive calls, thereby avoiding the overhead of creating new stack frames.

To take advantage of tail call optimization, we need to rewrite the recursive function in a way that the recursive call is the last operation performed. Here's an example of the Fibonacci function optimized for tail calls:

function fibonacciTailCall(n, a = 0, b = 1) {
  if (n === 0) {
    return a;
  }
  if (n === 1) {
    return b;
  }
  return fibonacciTailCall(n - 1, b, a + b);
}

In this version, we introduce two additional parameters a and b to keep track of the previous two Fibonacci numbers. The recursive call is made with n - 1, and the values of a and b are updated accordingly. The base conditions handle the cases when n is 0 or 1.

Time Complexity: O(n)

The tail-recursive solution has a time complexity of O(n) because it makes n recursive calls, each taking constant time. This time complexity remains the same regardless of whether tail call optimization is supported or not.

Space Complexity: O(n) or O(1)

The space complexity of the tail-recursive solution depends on whether the Javascript engine supports tail call optimization or not.

If tail call optimization is supported, the space complexity is reduced to O(1) because the recursive calls are optimized to reuse the same stack frame. This eliminates the need for additional memory to store the call stack.
If tail call optimization is not supported, the space complexity remains O(n) because each recursive call will consume an additional stack frame, similar to the naive recursive approach.

It's worth noting that tail call optimization is not consistently available across all Javascript engines. As of today, TCO is only supported by Safari (in strict mode). This means that the actual space complexity of the tail-recursive solution may vary depending on the execution environment.

Use cases:

When the recursive function can be transformed into a tail-recursive form
When the programming language or specific implementation supports tail call optimization

Pros:

Avoids stack overflow errors for deep recursions (if tail call optimization is supported)
Optimizes memory usage by reusing stack frames (if tail call optimization is supported)

Cons:

Not all Javascript engines support tail call optimization consistently
May require additional parameters and manipulation of the recursive function

To keep the consistent behavior across different Javascript environments, it's generally recommended to rely on other optimization techniques that have more predictable performance characteristics.

3 - Trampolining

Trampolining is a technique used to overcome the limitations of stack overflow in recursive functions. It involves separating the recursive function into a trampoline function that handles the recursive calls iteratively. This technique is particularly useful in Javascript, as it provides a way to manage deep recursion across different engines to prevent the call stack to exceed its limit.

Here's an example of applying trampolining to the Fibonacci function:

function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);
    while (typeof result === 'function') {
      result = result();
    }
    return result;
  };
}

function fibonacciTrampoline(n, a = 0, b = 1) {
  if (n === 0) {
    return a;
  }
  if (n === 1) {
    return b;
  }
  return () => fibonacciTrampoline(n - 1, b, a + b);
}

const trampolinedFibonacci = trampoline(fibonacciTrampoline);
trampolinedFibonacci(5); // Output: 5

In this variant, the trampoline function is defined separately. It takes a recursive function fn as an argument and returns a new function that handles the recursive calls iteratively. The fibonacciTrampoline function remains the same as before, returning a function that encapsulates the next recursive step.

The trampoline function repeatedly calls the returned function until a non-function value is returned, which represents the final result. Finally, we create a trampolinedFibonacci function by passing fibonacciTrampoline to the trampoline function.

Time Complexity: O(n)

The trampolined solution has a time complexity of O(n) because it performs n iterations in the trampoline function. Each iteration invokes the returned function, which represents the next step of the recursion.

Space Complexity: O(n)

The space complexity of the trampolined solution is O(n) because the closure returned by fibonacciTrampoline captures the current state of the computation. In the worst case, there will be n closures created, each capturing the values of n, a, and b.

Use cases:

When the recursive function has a deep recursion depth
When the programming language / engine does not support tail call optimization

Pros:

Avoids stack overflow errors by breaking down the recursion into smaller steps
Allows for deep recursions without exceeding the call stack limit

Cons:

Requires additional code to handle the trampolining logic
May have slightly slower performance compared to direct recursion

Take a look at the visual comparison below to see how trampolining effectively manages the call stack compared to the naive recursive approach:

Call stack visualization using the naive approach:

Recorded gif from JS Visualizer 9000 tool: https://www.jsv9000.app/

Call stack visualization using the trampoline optimization:

Recorded gif from JS Visualizer 9000 tool: https://www.jsv9000.app/

4 - Opting for an Iterative Approach

While recursive solutions can be elegant and expressive, sometimes an iterative approach can be more efficient in terms of time and space complexity. However, it's important to note that iterative variants of recursive functions can often be more complex and harder to understand compared to their recursive counterparts. Let's consider an iterative variant of the Fibonacci problem:

function fibonacciIterative(n) {
  if (n <= 1) {
    return n;
  }
  let a = 0;
  let b = 1;
  for (let i = 2; i <= n; i++) {
    const temp = b;
    b = a + b;
    a = temp;
  }
  return b;
}

In this iterative solution, we start with the base cases for n <= 1. Then, we initialize two variables a and b to keep track of the previous two Fibonacci numbers. We iterate from 2 to n, updating the values of a and b in each iteration. Finally, we return the value of b, which represents the Fibonacci number at position n.

Time Complexity: O(n)

The iterative solution has a time complexity of O(n) because it iterates from 2 to n, performing constant-time operations in each iteration. The number of iterations is directly proportional to the input value n.

Space Complexity: O(1)

The space complexity of the iterative solution is O(1) because it only uses a constant amount of additional memory to store the variables a, b, and temp. The space required does not depend on the input value n.

Use cases:

When the recursive solution exceeds the maximum call stack size
When the problem requires a large number of iterations

Pros:

Often more efficient in terms of time and space complexity
Avoids the overhead of function calls and stack management

Cons:

Can be more complex and harder to understand compared to recursive solutions
Requires explicit state management (e.g., variables to track previous values)
May lack the elegance and expressiveness of recursive solutions

Optimization summary

Just by looking at the time and space complexity of each optimization technique, we can see how they improve upon the naive recursive approach:

Memoization reduces the time complexity from O(2^n) exponential to O(n) linear, but space complexity stays at O(n) linear to store the memoized results.
Tail call optimization maintains the O(n) linear time complexity, if the language / engine supports TPO it reduces the space complexity to O(1) constant by reusing stack frames, else space complexity stays at O(n) linear.
Trampolining also maintains the O(n) linear time complexity but has a space complexity of O(n) linear due to the creation of closures.
The iterative approach achieves optimization on both ends - O(n) linear time complexity and O(1) constant space complexity, making it the most efficient in terms of both time and space. But at this point, we no longer have a recursive function.

While the iterative solution is the most efficient among them, it comes at the cost of reduced readability and increased complexity.

Recursive solutions, on the other hand, often have a more natural and intuitive structure that aligns with the problem's definition. They can be easier to understand and reason about, especially for problems that have a clear recursive nature.

When deciding between a recursive or iterative approach, it's also important to consider not only the efficiency aspects but also the readability and maintainability of the code. In some cases, a recursive solution may be preferable due to its simplicity and expressiveness, even if it has slightly higher time or space complexity compared to an iterative approach.

The choice between recursion and iteration depends on the specific problem, the constraints of the system, and the balance between efficiency and code clarity. It's all about comparing the trade-offs and choose the approach that best fits the given scenario while prioritizing code readability and maintainability.

I hope this article helped you to understand what a recursion is, how to work with it and how to optimize recursive functions depending on your use case. Thanks for reading!

Deep Dive into Data structures using Javascript - Graph

Şahin Arslan — Tue, 23 Apr 2024 19:40:54 +0000

Graphs are powerful data structures that excel at representing relationships and connections between objects. In the real world, graphs can model diverse scenarios such as social networks, transportation systems, computer networks, and even recommendations on e-commerce sites.

These non-linear and non-hierarchical structures consist of vertices (or nodes) and edges that create the links between them. Vertices can represent entities like individuals, locations, or objects, and the edges map the relationships or interactions between them.

While graphs share the non-linear quality with trees, they are distinct in their lack of hierarchical structure; in other words, graphs do not revolve around a central root node. This similarity is not superficial, as trees are actually a special category of graphs (Directed Acyclic Graphs). We will take a look at different type of graphs in more detail in the further sections.

The tone of this article is assuming you are at least familiar with the Tree data structure. If you need a quick refresher, I’d suggest you to start from “Introduction to Trees” article below, then come back and continue here later:

Deep Dive into Data structures using Javascript - Introduction to Trees

This article is intended to be a comprehensive introduction guide for Graphs, as a result it is quite lengthy. If you're looking for a specific section, feel free to use the table of contents below to directly navigate to the part you are interested.

Anatomy of a Graph
- Graph Types
  - Directed and Undirected
  - Weighted and Unweighted
  - Cyclic and Acyclic
  - Connected, Disconnected and Complete
- Graph Representations
  - Adjacency List
  - Adjacency Matrix
Graph Traversals
- Breadth First Traversal
- Depth First Traversal
- When to use Breadth-First vs Depth-First in Graphs
When to use a Graph
Graph Implementation in Javascript
- Adjacency List based Graph implementation
- Adjacency Matrix based Graph implementation

Anatomy of a Graph

Graphs has a complex and advanced anatomy that can be intimidating especially for those new to the subject. Before diving deeper into the types and inner workings of Graphs, let's start with getting familiar with the common terminologies:

Graph Terminologies:

Vertices (Nodes): These are the fundamental units of a graph, representing the entities or objects being modeled.
Edges (Links): Edges are the connections between vertices, representing the relationships or associations between entities.
Adjacent (Neighbor): In a graph, two vertices (nodes) are considered adjacent if they are directly connected by an edge, indicating an immediate relationship or link between them.
Degree: The degree of a vertex is the number of edges connected to it. In a directed graph, vertices have an in-degree (number of incoming edges) and an out-degree (number of outgoing edges).
Path: A path is a sequence of vertices connected by edges, allowing you to traverse from one vertex to another.
Self-loop: A self-loop is an edge that connects a vertex to itself. This represents a scenario where an entity is associated with or relates back to itself within the graph's context.
Cycle: A cycle is a path that starts and ends at the same vertex, forming a closed loop.

Types of Graph data structure

Graph is a broad term that includes variety of implementations that are designed to solve specific problems. "Type of graph" refers to the distinctive characteristics and configurations that define how the graph operates and what it can represent. A graph type can be on its own, or based on your use case it could also be a composition of types, such as a Directed Acyclic Graph (DAG) or an Undirected Weighted Graph, etc.

We'll be looking at most commonly used type of Graphs in this section one at a time. Once again it's important to understand that these types are not mutually exclusive; they can be combined to create more specialized graph structures tailored to specific requirements. For example, a graph can be both directed and weighted, or acyclic and unweighted, depending on the problem at hand.

Directed and Undirected Graphs

Directed Graph

In a directed graph, the relationships between vertices (nodes) are directional, meaning they flow in a specific direction. This is useful for representing scenarios where the connection or relationship is not mutual or reciprocal. For instance, in social networks like Twitter or Instagram, when you follow someone, it does not automatically mean they follow you back. Each follow represents a single one-way relationship. Even if two users follow each other, there are two separate one-way relationships, one in each direction.

Undirected Graph

In contrast to directed graph, undirected graphs represent relationships that are bidirectional or mutual. When you establish a connection between two vertices, it automatically implies a two-way relationship, meaning both vertices are connected to each other. This is useful for modeling scenarios like friendships on social networks like Facebook or LinkedIn, where adding someone as a friend or connection creates a mutual relationship.

Weighted and Unweighted Graphs

Weighted Graph

In a weighted graph, each edge (connection between vertices) has an associated numerical value, called a weight. These weights can represent measurements or costs related to the relationship, such as the distance between two cities in a road network or the duration of a flight between two airports. The weights play a crucial role in various graph algorithms, as they affect the traversal and decision-making processes based on factors like the length of a path or the total cost involved.

An edge in a weighted graph typically has a numerical weight assigned to represent the cost, capacity, or strength of the connection. If no specific weight is assigned, a default value, often 1 or 0, may be used depending on the application's requirements or the context of the graph.

Unweighted Graph

Unweighted graphs on the other hand, do not have any numerical values associated with their edges. All connections are treated equally, without any additional measurements or costs. This type of graph is useful for modeling scenarios where the primary concern is the existence of relationships or connections between vertices, rather than any quantitative aspects of those connections. Social networks, where the focus is on the relationships themselves (e.g., friendships or acquaintances), are a common example of unweighted graphs.

Cyclic and Acyclic Graphs

Cyclic Graph

A cyclic graph is one that contains at least one cycle, which is a path that starts and ends at the same vertex, without revisiting any other vertices more than once. Cycles are essential in certain applications, such as local traffic routes, where you can start from a point, travel through multiple locations, and eventually return to the starting point without retracing the same path. Another example is circular train lines, where trains operate in a continuous loop, facilitating uninterrupted transit.

Acyclic Graph

In contrast, an acyclic graph is one that does not contain any cycles. This means that once you start traversing from a vertex, you cannot return to the same vertex without revisiting another vertex more than once. Acyclic graphs are commonly used to represent hierarchical structures or dependencies, where there is a clear flow or direction without any loops or cycles. A good example is the version history in Git, where each commit or save point represents a step in the process, and you cannot go back to a previous step directly; you can only move forward by adding new commits or merging branches.

Connected, Disconnected and Complete Graphs

Connected Graph

A connected graph is one where every vertex is reachable from every other vertex through a sequence of edges. In other words, there exists at least one path between any two vertices in the graph. This property is similar to a road map, where you can always find a way to travel from one city to another, either directly or through a series of connected roads.

Disconnected Graph

In contrast, a disconnected graph consists of two or more separate components or subgraphs that are not connected to each other. This means that there are vertices or groups of vertices that have no paths connecting them to other vertices or groups. The analogy of remote islands is fitting, where some islands may have bridges connecting them, while others remain isolated, requiring different modes of transportation to reach them.

Complete Graph

A complete graph is a special type of graph where every vertex is directly connected to every other vertex. This means that for any pair of vertices, there exists an edge connecting them. The analogy of a dinner party where every guest is acquainted with every other guest illustrates this concept well. In a complete graph, there are no introductions needed, as every vertex has a direct connection to all other vertices, representing a fully interlinked system.

Graph Representations

Graphs can be represented in various ways, and the choice of representation can have a significant impact on the efficiency of graph operations and the memory usage. Two of the most common ways to represent graphs are adjacency lists and adjacency matrices.

Adjacency List

Adjacency list consists of unordered Arrays or Linked lists. Each vertex (node) is associated with a list of all connected vertices (nodes).

This representation is efficient for sparse graphs (graphs with relatively few edges compared to the maximum possible edges) because it only stores the existing edges. It is well-suited for operations that involve iterating over the neighbors of a vertex, such as depth-first search (DFS) or breadth-first search (BFS).

Adjacency Matrix

Adjacency matrix is a grid where rows and columns represent vertices:

Each cell in the matrix either has a 1 or a 0.
A cell has a 1 for an existing edge between its corresponding vertices, and a 0 when there's no edge.

This representation is efficient for dense graphs (graphs with many edges) because it provides constant-time access to check if an edge exists between any two vertices. It is well-suited for operations that involve checking the existence of an edge between two vertices.

Graph Traversals

Graph traversal algorithms are techniques used to visit and systematically process all the vertices in a graph. These algorithms play a key role in various graph operations, such as finding paths, detecting cycles, and exploring the structure of the graph.

There are different ways to traverse a graph, but we'll focus on the two most commonly used graph traversal algorithms: Breadth-First Traversal and Depth-First Traversal. If you're familiar with tree traversals, these names might sound familiar. Although the main mechanism regarding the traversal direction is conceptually similar, they work slightly differently when it comes to graphs.

Unlike tree traversals, where there is a clear hierarchical structure and a defined root node, graph traversals can start from any vertex (node). Additionally, we don't have subgroups such as pre-order, in-order, or post-order when it comes to depth-first traversals in graphs.

Since we don't follow a directed traversal like in trees, we must manage the potential cycles to avoid infinite loops during the process. This is typically done by keeping track of visited vertices and avoiding revisiting them.

If you don't have prior knowledge about tree traversals, it would be beneficial to check out the comprehensive tree traversal guide article below. Understanding tree traversals will provide a solid foundation and make it easier to grasp the concepts of graph traversals:

A Comprehensive Tree Traversal Guide in Javascript - General and Binary Tree Traversals

Breadth First Traversal

The Breadth-First Traversal algorithm explores all the vertices at the current depth level before moving on to vertices at the next depth level. It traverses the graph level by level, starting from a given source vertex. It uses a queue data structure to keep track of the vertices to be visited.

Depth First Traversal

The Depth-First Traversal algorithm explores as far as possible along each branch before backtracking. It visits all the vertices along a path before moving to the next path. It uses a stack data structure to keep track of the vertices to be visited.

When to use Breadth-First vs Depth-First in Graphs?

The choice between Breadth-First and Depth-First depends on the specific problem and the desired behavior. Breadth-First is useful for finding the shortest path between two vertices in an unweighted graph, while Depth-First is useful for topological sorting, detecting cycles, and exploring deeply nested structures.

Once again it's important to note that graph traversal algorithms must handle cycles to avoid infinite loops. This is typically done by keeping track of visited vertices and avoiding revisiting them. Additionally, traversal algorithms can be modified to accommodate different graph types, such as directed or weighted graphs, by adjusting the traversal rules accordingly.

When to Use a Graph

The decision to use a graph data structure often stems from the need to efficiently model and analyze relationships or connections between entities. Here are some common use cases for graphs:

Social Networks: Graphs are ideal for representing connections between people in social networks, where vertices represent users, and edges represent relationships or interactions.
Routing and Navigation Systems: Graphs can model transportation networks, with vertices representing locations (cities, intersections, etc.) and edges representing the routes or paths between them. Weighted edges can represent distances or travel times.
Recommendation Systems: E-commerce sites and content platforms can use graphs to represent relationships between products, users, and their preferences, enabling personalized recommendations.
Computer Networks: Graphs can model computer networks, with vertices representing devices (routers, servers, etc.) and edges representing the connections between them.
Dependency Tracking: In software development, graphs can model dependencies between modules, libraries, or components, helping to analyze and manage complex systems.

To motivate the choice of using a graph, let's take a look at the Big O time complexity of common operations:

Here, V represents the number of vertices, and E represents the number of edges.

While adjacency matrices provide constant-time access for querying relationships, they can be inefficient for sparse graphs (graphs with relatively few edges compared to the maximum possible) due to their quadratic space complexity. Adjacency lists often perform better in these cases, with a space complexity proportional to the number of edges.

Graph Implementation in Javascript

To implement a graph in JavaScript, we'll use an object-oriented approach with a Graph class and a separate Vertex class. I'll be sharing both adjacency list and adjacency matrix based implementations below. Each variant supports both directed and undirected graphs, as well as weighted and unweighted edges.

Here's the list of methods in the implementations:

Adjacency List based Graph implementation

Vertex Class:

constructor(key, value = null): Initializes a new instance of the Vertex class with the provided key and optional value.
addEdge(destinationKey, weight = 1): Adds a new edge to the adjacency list of the vertex, with the destinationKey and an optional weight. If no weight is provided, the default value of 1 is used.
removeEdge(destinationKey): Removes an edge from the adjacency list of the vertex by deleting the entry with the given destinationKey.

Graph Class:

constructor(directed = true): Initializes a new instance of the Graph class. It takes an optional directed parameter (default: true) to determine whether the graph should be directed or undirected.
addVertex(key, value = null): Adds a new vertex to the graph with the provided key and optional value. If the vertex already exists, it updates the value.
addEdge(sourceKey, destinationKey, weight = 1): Adds an edge between the vertices identified by sourceKey and destinationKey. If the graph is undirected, it adds an edge in both directions. It also supports an optional weight for the edge. The default value for an unweighted edge is set to 1.
removeVertex(key): Removes the vertex with the given key from the graph. It also removes all edges connected to this vertex.
removeEdge(sourceKey, destinationKey): Removes the edge between the vertices identified by sourceKey and destinationKey. If the graph is undirected, it removes the edge in both directions.
breadthFirstSearch(startingVertexKey, targetKey): Performs a breadth-first search (BFS) starting from the vertex identified by startingVertexKey to find the vertex with the targetKey. Returns the target vertex if found, otherwise null.
depthFirstSearch(startingVertexKey, targetKey): Performs a depth-first search (DFS) starting from the vertex identified by startingVertexKey to find the vertex with the targetKey. Returns the target vertex if found, otherwise null.
breadthFirstTraversal(startingVertexKey): Performs a breadth-first traversal starting from the vertex identified by startingVertexKey. Returns an array of vertex keys in the order they were visited.
depthFirstTraversal(startingVertexKey): Performs a depth-first traversal starting from the vertex identified by startingVertexKey. Returns an array of vertex keys in the order they were visited.
getNeighbors(vertexKey): Returns an array of keys representing the neighboring vertices of the vertex identified by vertexKey.
printGraph(): Prints the graph representation in an adjacency list format, showing each vertex and its connected edges.

Adjacency Matrix based Graph implementation:

Vertex Class:

constructor(key, value = null): Initializes a new instance of the Vertex class with the provided key and optional value.

Graph Class:

addVertex(key, value = null): Adds a new vertex to the graph with the provided key and optional value. If the vertex already exists, it updates the value.
addEdge(sourceKey, destinationKey, weight = 1): Adds an edge between the vertices identified by sourceKey and destinationKey. If the graph is undirected, it adds an edge in both directions. It also supports optional weight for the edge. Unweighted edge default value is set to 1.
removeVertex(key): Removes the vertex with the given key from the graph. It also removes all edges connected to this vertex.
removeEdge(sourceKey, destinationKey): Removes the edge between the vertices identified by sourceKey and destinationKey. If the graph is undirected, it removes the edge in both directions.
breadthFirstSearch(startingVertexKey, targetKey): Performs a breadth-first search (BFS) starting from the vertex identified by startingVertexKey to find the vertex with the targetKey. Returns the target vertex if found, otherwise null.
depthFirstSearch(startingVertexKey, targetKey): Performs a depth-first search (DFS) starting from the vertex identified by startingVertexKey to find the vertex with the targetKey. Returns the target vertex if found, otherwise null.
breadthFirstTraversal(startingVertexKey): Performs a breadth-first traversal starting from the vertex identified by startingVertexKey. Returns an array of vertex keys in the order they were visited.
depthFirstTraversal(startingVertexKey): Performs a depth-first traversal starting from the vertex identified by startingVertexKey. Returns an array of vertex keys in the order they were visited.
getNeighbors(vertexKey): Returns an array of keys representing the neighboring vertices of the vertex identified by vertexKey.
printGraph(): Prints the graph representation in an adjacency matrix format, showing a matrix of edges between vertices.
_indexToKey(index): A private helper function that converts a vertex index to its corresponding key.

Graphs may seem intimidating, yet they powerfully handle interconnected data and solve complex problems that challenge other data structures. If you want to see how graphs work in an interactive way, I highly recommend playing around with these great graph visualizers at the links below:

Graph Data Structures Visualizer: https://visualgo.net/en/graphds?slide=1
Graph Traversal Visualizer: https://visualgo.net/en/dfsbfs?slide=1

I've also included line-by-line explanations for each method in the adjacency list and adjacency matrix implementations for you to follow along with what's happening in the code.

I hope this article helped you understand what graphs are and how they work! Understanding Graphs for the first time is a solid challenge, it will definitely require investing time into experimentation and exploration - so I'd like to encourage you to experiment with the implementations provided below in your favorite code editor.

Thanks for reading!

Adjacency List based Graph implementation

class Vertex {
  // Constructor to create a vertex object
  constructor(key, value = null) {
    this.key = key; // Unique identifier for the vertex
    this.value = value; // Optional value held by the vertex
    this.edges = new Map(); // Initialize a map to store edges connected to this vertex
  }

  // Method to add an edge to another vertex with an optional weight
  addEdge(destinationKey, weight = 1) {
    this.edges.set(destinationKey, weight); // Adds an edge to the destination vertex with the given weight
  }

  // Method to remove an edge to another vertex
  removeEdge(destinationKey) {
    this.edges.delete(destinationKey); // Removes the edge to the destination vertex
  }
}

class AdjacencyListGraph {
  // Constructor to create a graph object
  constructor(directed = true) {
    this.directed = directed; // Boolean to indicate if the graph is directed
    this.vertices = new Map(); // Initialize a map to store vertices by their keys
  }

  // Method to add a vertex to the graph
  addVertex(key, value = null) {
    if (!this.vertices.has(key)) {
      // Check if the vertex does not already exist
      const vertex = new Vertex(key, value); // Create a new vertex instance
      this.vertices.set(key, vertex); // Add the vertex to the vertices map
    } else {
      this.vertices.get(key).value = value; // Update the value of an existing vertex
    }
  }

  // Method to add an edge between two vertices with an optional weight
  addEdge(sourceKey, destinationKey, weight = 1) {
    if (!this.vertices.has(sourceKey) || !this.vertices.has(destinationKey)) {
      throw new Error("Both vertices must exist to add an edge."); // Ensure both vertices exist
    }
    this.vertices.get(sourceKey).addEdge(destinationKey, weight); // Add the edge from source to destination
    if (!this.directed) {
      // If the graph is undirected,
      this.vertices.get(destinationKey).addEdge(sourceKey, weight); // add a reverse edge as well
    }
  }

  // Method to remove a vertex from the graph
  removeVertex(key) {
    if (!this.vertices.has(key)) return; // If the vertex does not exist, return
    const vertex = this.vertices.get(key); // Get the vertex object
    vertex.edges.forEach((_, destKey) => {
      // Remove all outgoing edges
      this.vertices.get(destKey).removeEdge(key); // Remove reverse edges from connected vertices
    });
    this.vertices.forEach((v) => v.removeEdge(key)); // Remove this vertex as a destination from other vertices
    this.vertices.delete(key); // Remove the vertex from the vertices map
  }

  // Method to remove an edge between two vertices
  removeEdge(sourceKey, destinationKey) {
    if (!this.vertices.has(sourceKey) || !this.vertices.has(destinationKey)) {
      throw new Error("Both vertices must exist to remove an edge."); // Ensure both vertices exist
    }
    this.vertices.get(sourceKey).removeEdge(destinationKey); // Remove the edge from source to destination
    if (!this.directed) {
      this.vertices.get(destinationKey).removeEdge(sourceKey); // If undirected, remove the reverse edge as well
    }
  }

  // Method for breadth-first search starting from a given vertex and aiming to find a specific vertex
  breadthFirstSearch(startingVertexKey, targetKey) {
    if (!this.vertices.has(startingVertexKey)) {
      throw new Error("Starting vertex does not exist."); // Ensure the starting vertex exists
    }

    const queue = [startingVertexKey]; // Initialize the queue with the starting vertex
    const visited = new Set(); // Set to track visited vertices

    while (queue.length > 0) {
      const currentKey = queue.shift(); // Dequeue the front vertex
      if (currentKey === targetKey) {
        return this.vertices.get(currentKey); // If the target is found, return the vertex
      }

      if (!visited.has(currentKey)) {
        visited.add(currentKey); // Mark the current vertex as visited
        const neighbors = Array.from(
          this.vertices.get(currentKey).edges.keys()
        ); // Get all neighbors
        queue.push(...neighbors.filter((neighbor) => !visited.has(neighbor))); // Enqueue unvisited neighbors
      }
    }
    return null; // Return null if the target is not found
  }

  // Method for depth-first search starting from a given vertex and aiming to find a specific vertex
  depthFirstSearch(startingVertexKey, targetKey) {
    if (!this.vertices.has(startingVertexKey)) {
      throw new Error("Starting vertex does not exist."); // Ensure the starting vertex exists
    }
    const stack = [startingVertexKey]; // Initialize the stack with the starting vertex
    const visited = new Set(); // Set to track visited vertices

    while (stack.length > 0) {
      const currentKey = stack.pop(); // Pop the top vertex from the stack
      if (currentKey === targetKey) {
        return this.vertices.get(currentKey); // If the target is found, return the vertex
      }

      if (!visited.has(currentKey)) {
        visited.add(currentKey); // Mark the current vertex as visited
        const neighbors = Array.from(
          this.vertices.get(currentKey).edges.keys()
        ); // Get all neighbors
        stack.push(
          ...neighbors.filter((neighbor) => !visited.has(neighbor)).reverse()
        ); // Push unvisited neighbors onto the stack, reversed to maintain order
      }
    }
    return null; // Return null if the target is not found
  }

  // Method for breadth-first traversal of the graph starting from a given vertex
  breadthFirstTraversal(startingVertexKey) {
    if (!this.vertices.has(startingVertexKey)) {
      throw new Error("Starting vertex does not exist."); // Ensure the starting vertex exists
    }
    const queue = [startingVertexKey]; // Initialize the queue with the starting vertex
    const visited = new Set(); // Set to track visited vertices
    const result = []; // List to store the order of visited vertices

    while (queue.length > 0) {
      const currentKey = queue.shift(); // Dequeue the front vertex
      if (!visited.has(currentKey)) {
        visited.add(currentKey); // Mark the current vertex as visited
        result.push(currentKey); // Add the vertex to the result list
        const neighbors = Array.from(
          this.vertices.get(currentKey).edges.keys()
        ); // Get all neighbors
        queue.push(...neighbors.filter((neighbor) => !visited.has(neighbor))); // Enqueue unvisited neighbors
      }
    }

    return result; // Return the list of visited vertices in order
  }

  // Method for depth-first traversal of the graph starting from a given vertex
  depthFirstTraversal(startingVertexKey) {
    if (!this.vertices.has(startingVertexKey)) {
      throw new Error("Starting vertex does not exist."); // Ensure the starting vertex exists
    }
    const stack = [startingVertexKey]; // Initialize the stack with the starting vertex
    const visited = new Set(); // Set to track visited vertices
    const result = []; // List to store the order of visited vertices

    while (stack.length > 0) {
      const currentKey = stack.pop(); // Pop the top vertex from the stack
      if (!visited.has(currentKey)) {
        visited.add(currentKey); // Mark the current vertex as visited
        result.push(currentKey); // Add the vertex to the result list
        const neighbors = Array.from(
          this.vertices.get(currentKey).edges.keys()
        ); // Get all neighbors
        stack.push(
          ...neighbors.filter((neighbor) => !visited.has(neighbor)).reverse()
        ); // Push unvisited neighbors onto the stack, reversed to maintain order
      }
    }

    return result; // Return the list of visited vertices in order
  }

  // Method to get all neighbors of a vertex
  getNeighbors(vertexKey) {
    if (!this.vertices.has(vertexKey)) {
      throw new Error("Vertex does not exist."); // Ensure the vertex exists
    }
    return Array.from(this.vertices.get(vertexKey).edges.keys()); // Return all neighboring vertex keys
  }

  // Method to print the entire graph
  printGraph() {
    this.vertices.forEach((vertex, key) => {
      const edges = Array.from(vertex.edges).map(
        // Format each edge with its destination and weight
        ([destinationKey, weight]) => `${destinationKey}(${weight})`
      );
      // Print each vertex and its connected edges
      console.log(`${key} -> ${edges.join(", ")}`);
    });
  }
}

// Usage example setup code
const graph = new AdjacencyListGraph(); // Directed graph using adjacency list
// Add vertices
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addVertex(4);
graph.addVertex(5);
graph.addVertex(6);
graph.addVertex(7);

// Add edges
graph.addEdge(1, 2);
graph.addEdge(1, 4);
graph.addEdge(1, 5);
graph.addEdge(2, 3);
graph.addEdge(2, 6);
graph.addEdge(2, 7);

graph.printGraph();

console.log("BF TRAVERSAL-----------");
graph.breadthFirstTraversal(1);
console.log("DF TRAVERSAL-----------");
graph.depthFirstTraversal(1);

console.log("------------");

graph.breadthFirstSearch(1, 7);
graph.depthFirstSearch(1, 5);

/*
TEST RESULTS:

BFS
Directed - 1, 2, 4, 5, 3, 6, 7
Undirected - 1, 2, 4, 5, 3, 6, 7

DFS
Directed - 1, 2, 3, 6, 7, 4, 5
Undirected - 1, 2, 3, 6, 7, 4, 5
*/

Adjacency Matrix based Graph implementation:

class Vertex {
  // Constructor to initialize a vertex with a key and an optional value
  constructor(key, value = null) {
    this.key = key; // Unique identifier for the vertex
    this.value = value; // Value associated with the vertex (optional)
  }
}

class AdjacencyMatrixGraph {
  // Constructor to create a graph object
  constructor(directed = true) {
    this.directed = directed; // Boolean to indicate if the graph is directed
    this.vertices = new Map(); // Map to store vertices with their keys
    this.edges = []; // Array to represent the adjacency matrix
  }

  // Method to add a vertex to the graph
  addVertex(key, value = null) {
    if (!this.vertices.has(key)) {
      // Check if the vertex does not already exist
      const vertex = new Vertex(key, value); // Create a new vertex
      const index = this.vertices.size; // Determine the next index for the new vertex
      this.vertices.set(key, vertex); // Add the vertex to the map
      vertex.index = index; // Store the index within the vertex for quick access
      this.edges.forEach((row) => row.push(0)); // Extend each existing row in the adjacency matrix with a zero
      this.edges.push(new Array(this.vertices.size).fill(0)); // Add a new row for the new vertex
    } else {
      this.vertices.get(key).value = value; // Update the value of an existing vertex
    }
  }

  // Method to add an edge between two vertices with an optional weight
  addEdge(sourceKey, destinationKey, weight = 1) {
    if (!this.vertices.has(sourceKey) || !this.vertices.has(destinationKey)) {
      throw new Error("Both vertices must exist to add an edge."); // Ensure both vertices exist
    }
    const sourceIndex = this.vertices.get(sourceKey).index; // Get the matrix index of the source vertex
    const destIndex = this.vertices.get(destinationKey).index; // Get the matrix index of the destination vertex
    this.edges[sourceIndex][destIndex] = weight; // Set the weight in the adjacency matrix
    if (!this.directed) {
      // If the graph is undirected,
      this.edges[destIndex][sourceIndex] = weight; // set the reciprocal edge as well
    }
  }

  // Method to remove a vertex from the graph
  removeVertex(key) {
    if (!this.vertices.has(key)) return; // If the vertex does not exist, just return
    const index = this.vertices.get(key).index; // Get the matrix index of the vertex
    this.edges.splice(index, 1); // Remove the row from the adjacency matrix
    this.edges.forEach((row) => row.splice(index, 1)); // Remove the column from the adjacency matrix
    this.vertices.delete(key); // Remove the vertex from the map
    this.vertices.forEach((v, k) => {
      if (v.index > index) {
        // Adjust the indices of vertices that followed the removed vertex
        v.index--;
      }
    });
  }

  // Method to remove an edge between two vertices
  removeEdge(sourceKey, destinationKey) {
    if (!this.vertices.has(sourceKey) || !this.vertices.has(destinationKey)) {
      throw new Error("Both vertices must exist to remove an edge."); // Ensure both vertices exist
    }
    const sourceIndex = this.vertices.get(sourceKey).index; // Get the matrix index of the source vertex
    const destIndex = this.vertices.get(destinationKey).index; // Get the matrix index of the destination vertex
    this.edges[sourceIndex][destIndex] = 0; // Set the weight to zero in the adjacency matrix
    if (!this.directed) {
      this.edges[destIndex][sourceIndex] = 0; // If undirected, also remove the reciprocal edge
    }
  }

  // Method to perform a breadth-first search from a starting vertex to find a target vertex
  breadthFirstSearch(startingVertexKey, targetKey) {
    if (!this.vertices.has(startingVertexKey)) {
      throw new Error("Starting vertex does not exist."); // Ensure the starting vertex exists
    }

    const startVertex = this.vertices.get(startingVertexKey); // Get the start vertex
    const queue = [startVertex.index]; // Initialize the queue with the index of the start vertex
    const visited = new Set(); // Set to track visited vertex indices

    while (queue.length > 0) {
      const currentIndex = queue.shift(); // Dequeue the first element
      const currentKey = this._indexToKey(currentIndex); // Convert index back to vertex key

      if (currentKey === targetKey) {
        return this.vertices.get(currentKey); // If the target vertex is found, return it
      }

      if (!visited.has(currentIndex)) {
        visited.add(currentIndex); // Mark the current index as visited
        this.edges[currentIndex].forEach((weight, index) => {
          if (weight > 0 && !visited.has(index)) {
            queue.push(index); // Enqueue the index of connected vertices
          }
        });
      }
    }
    return null; // Return null if the target is not found
  }

  // Method to perform a depth-first search from a starting vertex to find a target vertex
  depthFirstSearch(startingVertexKey, targetKey) {
    if (!this.vertices.has(startingVertexKey)) {
      throw new Error("Starting vertex does not exist."); // Ensure the starting vertex exists
    }

    const startVertex = this.vertices.get(startingVertexKey);
    const stack = [startVertex.index]; // Initialize the stack with the index of the start vertex
    const visited = new Set(); // Set to track visited vertex indices

    while (stack.length > 0) {
      const currentIndex = stack.pop(); // Pop the top element
      const currentKey = this._indexToKey(currentIndex); // Convert index back to vertex key

      if (currentKey === targetKey) {
        return this.vertices.get(currentKey); // If the target vertex is found, return it
      }

      if (!visited.has(currentIndex)) {
        visited.add(currentIndex); // Mark the current index as visited
        const neighbors = []; // List to hold neighbor indices
        this.edges[currentIndex].forEach((weight, index) => {
          if (weight > 0 && !visited.has(index)) {
            neighbors.push(index); // Collect unvisited connected indices
          }
        });

        neighbors.reverse().forEach((index) => stack.push(index)); // Reverse and push to maintain correct order
      }
    }

    return null; // Return null if the target is not found
  }

  // Method to perform a breadth-first traversal from a specified starting vertex
  breadthFirstTraversal(startingVertexKey) {
    if (!this.vertices.has(startingVertexKey)) {
      throw new Error("Starting vertex does not exist."); // Ensure the starting vertex exists
    }

    const startVertex = this.vertices.get(startingVertexKey); // Get the start vertex
    const queue = [startVertex.index]; // Initialize the queue with the index of the start vertex
    const visited = new Set(); // Set to track visited vertex indices
    const result = []; // List to store the order of visited vertices

    while (queue.length > 0) {
      const currentIndex = queue.shift(); // Dequeue the first element
      const currentKey = this._indexToKey(currentIndex); // Convert index back to vertex key

      if (!visited.has(currentIndex)) {
        visited.add(currentIndex); // Mark the current index as visited
        result.push(currentKey); // Add the current key to result list
        this.edges[currentIndex].forEach((weight, index) => {
          if (weight > 0 && !visited.has(index)) {
            queue.push(index); // Enqueue the index of connected vertices
          }
        });
      }
    }

    return result; // Return the list of visited vertices in order
  }

  // Method to perform a depth-first traversal from a specified starting vertex
  depthFirstTraversal(startingVertexKey) {
    if (!this.vertices.has(startingVertexKey)) {
      throw new Error("Starting vertex does not exist."); // Ensure the starting vertex exists
    }

    const startVertex = this.vertices.get(startingVertexKey);
    const stack = [startVertex.index]; // Initialize the stack with the index of the start vertex
    const visited = new Set(); // Set to track visited vertex indices
    const result = []; // List to store the order of visited vertices

    while (stack.length > 0) {
      const currentIndex = stack.pop(); // Pop the top element
      const currentKey = this._indexToKey(currentIndex); // Convert index back to vertex key

      if (!visited.has(currentIndex)) {
        visited.add(currentIndex); // Mark the current index as visited
        result.push(currentKey); // Add the current key to result list

        const neighbors = []; // List to hold neighbor indices
        this.edges[currentIndex].forEach((weight, index) => {
          if (weight > 0 && !visited.has(index)) {
            neighbors.push(index); // Collect unvisited connected indices
          }
        });

        neighbors.reverse().forEach((index) => stack.push(index)); // Reverse and push to maintain correct order
      }
    }

    return result; // Return the list of visited vertices in order
  }

  // Method to get all neighbors of a specific vertex
  getNeighbors(vertexKey) {
    if (!this.vertices.has(vertexKey)) {
      throw new Error("Vertex does not exist."); // Ensure the vertex exists
    }
    const index = this.vertices.get(vertexKey).index; // Get the matrix index of the vertex
    const neighbors = [];
    this.edges[index].forEach((weight, idx) => {
      if (weight > 0) {
        neighbors.push(this._indexToKey(idx)); // Convert indices to keys and collect as neighbors
      }
    });
    return neighbors; // Return the list of neighbor vertices
  }

  // Method to print the graph as an adjacency matrix
  printGraph() {
    const verticesArray = Array.from(this.vertices.keys()); // Extract vertex keys
    console.log("  " + verticesArray.join(" ")); // Print header row with vertex keys
    this.edges.forEach((row, i) => {
      console.log(verticesArray[i] + " " + row.join(" ")); // Print each row of the adjacency matrix
    });
  }

  // Private helper method to convert a matrix index back to a vertex key
  _indexToKey(index) {
    return Array.from(this.vertices.keys())[index]; // Convert index to key using map keys extraction
  }
}

// Usage example setup code
const graph = new AdjacencyMatrixGraph(false); // Undirected graph using adjacency matrix
// Add vertices
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addVertex(4);
graph.addVertex(5);
graph.addVertex(6);
graph.addVertex(7);

// Add edges
graph.addEdge(1, 2);
graph.addEdge(1, 4);
graph.addEdge(1, 5);
graph.addEdge(2, 3);
graph.addEdge(2, 6);
graph.addEdge(2, 7);

graph.printGraph();

console.log("BF TRAVERSAL-----------");
graph.breadthFirstTraversal(1);
console.log("DF TRAVERSAL-----------");
graph.depthFirstTraversal(1);

console.log("------------");

graph.breadthFirstSearch(1, 7);
graph.depthFirstSearch(1, 5);

/*
TEST RESULTS:

BFS
Directed - 1, 2, 4, 5, 3, 6, 7
Undirected - 1, 2, 4, 5, 3, 6, 7

DFS
Directed - 1, 2, 3, 6, 7, 4, 5
Undirected - 1, 2, 3, 6, 7, 4, 5
*/

Deep Dive into Data structures using Javascript - Trie

Şahin Arslan — Sun, 14 Jan 2024 12:49:33 +0000

Trie, often referred to as a prefix tree, stands out as a specialized data structure tailored for handling string-based data. Its design is unique among tree structures, focusing on storing associative data that can be accessed quickly and dynamically - which is a necessity for extensive word databases. This makes it particularly suited for applications such as autocomplete systems and spell-check tools, where rapid data retrieval is key.

The real strength of Trie lies in its approach to organizing data. Unlike binary search trees which sort data by node value, Tries are built around character sequences. This structural difference is what sets Trie apart, offering a more direct route for tasks like searching specific strings or prefixes.

This article assumes you're already comfortable with basic tree data structures and JavaScript. If you need a quick refresher, I'd suggest you to start from "Introduction to Trees" article below, then come back and continue here later. Once you're up to speed, you'll find diving into Tries much more straightforward:

Deep dive into data structures using Javascript - Introduction to Trees

Anatomy of a Trie

A Trie consists of connected nodes that form a hierarchy, where each node represents a character, and each node can have any number of children nodes, each representing a different character. The Trie starts with a root node, and every node in the tree descends from it. There can be only one root in the Trie and it does not hold any letter of alphabet in it's value property - as it serves as the common starting point which all words in Trie to branch out. Due to this reason it is often initialized with an empty string value.

The Building Blocks: Nodes and Pointers

Nodes: Each node in a Trie represents a single character of a string. Some nodes are flagged to emphasize the end of a word, making it easy to determine when a complete word has been formed.
Pointers: These are the connectors between nodes, forming paths from the root to the individual characters of stored words. They are the key concept for navigating through the Trie and for constructing words.

Node Representation: Objects vs. Arrays

When constructing a Trie, there are two primary ways to represent the children of each node: using objects or arrays. We'll be taking a look at the both approaches, and I'll be sharing the implementation for both of them at the end of this article.

Trie using Object based implementation

This approach uses an object to store children nodes. Each key represents a character, and the value is the corresponding child node. This method offers more flexibility and can handle dynamic and larger character sets more efficiently. It also simplifies operations like insertion and search, as it allows direct access to child nodes without needing to calculate index positions.

Trie using Array based implementation

In this approach, each node is an array where each index corresponds to a character. This can be efficient for fixed-size character sets, like the 26 letters of the English alphabet, but may not be as flexible or space-efficient for larger or dynamic character sets.

The Process of Storing Data

In a Trie, data insertion starts at the root. As each character of a word is processed, the Trie either uses existing nodes (for common prefixes) or creates new ones. This method maximizes space efficiency and speeds up data retrieval, especially noticeable in applications dealing with large datasets.

Take a look at the visual below to see how space efficient insertion flow works in Trie:

Key Characteristics

Space Optimization: By sharing common prefixes, Tries efficiently utilize space. This is particularly effective for datasets with overlapping strings.
Dynamic Adaptability: The structure of a Trie naturally expands or contracts based on the data it holds.
Search Efficiency: Trie enables quick searches, where the time taken is proportional to the length of the word, rather than the size of the dataset.

When to Use a Trie

Since Trie is a specialized data structure, it's unique properties makes it favorable in specialized cases. Let's start with taking a quick look at the Big O of common operations:

Insertion Operation (Insert): For inserting a new word, the time complexity is O(L), where L is the length of the word. This is because the operation only needs to process each character of the word once.

Search Operation (Search): Searching for a word also has a time complexity of O(L), where L is the length of the word. This efficiency is due to the direct path traversal from the root to the node representing the last character.

Deletion Operation (Delete): Deletion in a Trie can vary, but it is generally O(L) for deleting a word, as it involves traversing the word and potentially cleaning up nodes.

Finding All Words Starts With a Given Prefix: This operation is where Tries truly shine, with an initial O(L) complexity to find the prefix, and then an additional cost proportional to the number of results found.

Autocomplete: Autocomplete operation has a time complexity of O(L + n), where L is the length of the prefix and n is the total number of characters in the resulting words.

Given these time complexity characteristics, Tries become particularly advantageous in scenarios like:

Autocomplete Systems: Tries are ideal for autocomplete systems where the user inputs a few characters and the system suggests possible completions. The Trie’s ability to quickly find all words with a given prefix makes it a perfect fit.

Spell Checking and Word Games: With their quick search capability, Tries are well-suited for spell checking and word games where rapid validation of word existence is crucial.

Prefix-Based Search: Any application that requires frequent prefix-based searches, such as searching for contacts in a phone book, can benefit from the structure of a Trie, as it allows for a quick retrieval of all entries under a specific prefix.

Dictionary Implementation: Tries are effective for implementing dictionaries due to their quick insert and search operations for words, and their ability to easily handle dynamic word addition and removal.

IP Routing: In networking, Tries can be used for storing and searching IP routing information efficiently, where IP addresses are viewed as strings of bits.

Bioinformatics Applications: Due to their efficiency in dealing with strings, Tries are used in various bioinformatics applications for pattern matching within DNA sequences.

Trie implementation in Javascript

We will be using ES6 Classes to build our Trie in both object and array based implementations. Here is the list of methods in the implementations:

Object based Trie implementation:

insert(word): Integrates a new word into the Trie, creating a path of nodes that represents the word if it does not already exist.
search(word): Confirms whether a word is present in the Trie by traversing the nodes corresponding to the characters of the word.
delete(word): Removes a word from the Trie, carefully detaching nodes when necessary to avoid disrupting the remaining words.
startsWith(prefix): Determines if any word in the Trie begins with the given prefix, an essential feature for prefix-based queries.
autocomplete(prefix): Retrieves a list of all words that stem from the given prefix, providing the backbone for functionalities like search prediction.
_deleteRecursively(node, word, index): A private helper function to support the delete operation.
_findAllWords(node, prefix): A private helper function that recursively accumulates all words that start from the given node, used in the autocomplete method.
displayAllWords(): Gathers and returns all words currently stored in the Trie. It traverses the Trie and accumulates complete words, providing a clear view of the Trie's content.
displayTrie(): Executes a breadth-first traversal, yielding the Trie's contents level by level, which is instrumental for visualization and verification during development.

Array based Trie implementation:

insert(word): Adds a new word to the Trie. It iterates over each character of the word, creating a path of nodes that represents the word. For each character, it converts it to an index and to make sure there is a corresponding TrieNode in the children array. The final node in the path is marked as the end of a word.
search(word): Checks if a word is present in the Trie. This method traverses the Trie, following the path of nodes corresponding to each character in the word. If all characters are found in sequence, and the final node is marked as the end of a word, the method returns true, indicating the word exists in the Trie.
delete(word): Removes a word from the Trie. It uses a recursive helper function to traverse the Trie and unset the endOfWord flag at the final node of the word. It also checks whether each node along the path can be removed (i.e., if it has no children and is not part of another word).
startsWith(prefix): Determines if there is any word in the Trie that starts with the given prefix. It traverses the Trie using the characters of the prefix. If the traversal can continue for the entire length of the prefix, it returns true, indicating that there is at least one word in the Trie that starts with that prefix.
autocomplete(prefix): Finds all words in the Trie that start with the given prefix. It first finds the node corresponding to the last character of the prefix, then uses a recursive helper function to find and return all words that stem from that node.
_charToIndex(char): A private helper function that converts a character into an index (0-25). This is used to map each character to a specific index in the children array of a TrieNode.
_findAllWords(node, prefix): A private recursive helper function that accumulates all words starting from a given node. It is used in the autocomplete method to find all continuations of a prefix, constructing words by appending characters to the prefix as it traverses the Trie.
displayAllWords(): Gathers and returns all words currently stored in the Trie. It traverses the Trie and accumulates complete words, providing a clear view of the Trie's content.
displayTrie(): Performs a level-order traversal of the Trie and displays the contents of the children arrays at each level. This method provides a visualization of the Trie's structure, showing which characters are present at each node's children array.

Tries may seem straightforward, but their underlying power is in the systematic way they handle strings. If you want to see how Trie works in an interactive way, I highly recommend playing around with this great Trie visualizer at the link below:

https://www.cs.usfca.edu/~galles/visualization/Trie.html

Furthermore, I’ve also included line-by-line explanations for each method in the implementation for you to follow up what is happening in the code. I hope this article helped you to understand what Tries are and how they work! I’d like to encourage you to experiment with the implementations below in your favorite code editor. Thanks for reading!

Object based Trie implementation:

class TrieNode {
  constructor(value = "") {
    // Initialize an empty object to hold child nodes.
    this.children = {};
    // Flag to indicate whether this node represents the end of a word.
    this.endOfWord = false;
    // The value property stores the character value for this Trie node.
    this.value = value;
  }
}

class Trie {
  constructor() {
    // The root node, which acts as the
    // starting point of the Trie and holds no character value.
    this.root = new TrieNode();
  }

  // Inserts a word into the trie
  insert(word) {
    // Start at the root node.
    let current = this.root;
    // Iterate over each character in the word.
    for (let char of word) {
      // If the current node doesn't have
      // a child with the current character...
      if (!current.children[char]) {
        // ...create a new TrieNode and assign it
        // to the corresponding character in the children object.
        current.children[char] = new TrieNode(char);
      }
      // Move the current pointer to the
      // child node of the current character.
      current = current.children[char];
    }
    // After inserting the last character of the word,
    // set the endOfWord flag to true.
    current.endOfWord = true;
  }

  // Search for a word in the trie
  search(word) {
    // Start at the root node.
    let current = this.root;
    // Iterate over each character in the word.
    for (let char of word) {
      // If the current node doesn't have a child
      // with the current character...
      if (!current.children[char]) {
        // ...the word doesn't exist in the trie.
        return false;
      }
      // Move the current pointer to the
      // child node of the current character.
      current = current.children[char];
    }
    // Return true if the current node has
    // the endOfWord flag set to true,
    // indicating the end of the word
    // has been reached and the word exists.
    return current.endOfWord;
  }

  // Delete a word from the trie
  delete(word) {
    // Begin the recursive deletion process starting from the root node.
    this._deleteRecursively(this.root, word, 0);
  }

  // Helper function for delete
  _deleteRecursively(node, word, index) {
    // If the end of the word has been reached...
    if (index === word.length) {
      // ...and the current node marks the end of a word...
      if (node.endOfWord) {
        // ...unset the endOfWord flag,
        // indicating that the word is no longer valid.
        node.endOfWord = false;
      }
      // Return true if the node has no children,
      // indicating it can be deleted from its parent.
      return Object.keys(node.children).length === 0;
    }

    // Get the character at the current index of the word.
    const char = word[index];
    // Find the child node that corresponds to the character.
    const childNode = node.children[char];

    // If the child node does not exist...
    if (childNode == null) {
      // ...the word is not present in the Trie,
      // and there's nothing to delete.
      return false;
    }

    // Recursively attempt to delete the next node in the sequence.
    const shouldDeleteChild = this._deleteRecursively(
      childNode,
      word,
      index + 1
    );

    // If the recursive call returns true (the child can be deleted)...
    if (shouldDeleteChild) {
      // ...delete the reference to the child node.
      delete node.children[char];

      // Return true if the current node has no more children
      // and it's not marking the end of another word,
      // signaling that this node can also be potentially deleted.
      return Object.keys(node.children).length === 0 && !node.endOfWord;
    }

    // If the child node should not be deleted, return false,
    // indicating this node still has valid children.
    return false;
  }

  // Check if there is any word in the trie that starts with the given prefix
  startsWith(prefix) {
    // Start at the root node of the Trie.
    let current = this.root;
    // Iterate over each character in the prefix.
    for (let char of prefix) {
      // If the current node does not
      // have a child corresponding to the character...
      if (!current.children[char]) {
        // ...then no words with this prefix exist in the Trie.
        return false;
      }
      // Move to the child node associated with the character.
      current = current.children[char];
    }
    // If all characters in the prefix are found, return true.
    return true;
  }

  // Find all words in the trie that start with the given prefix
  autocomplete(prefix) {
    // Start the search at the root of the Trie.
    let current = this.root;
    // Iterate over each character in the prefix.
    for (let char of prefix) {
      // If a character in the prefix is not found...
      if (!current.children[char]) {
        // ...return an empty array as there are no words with this prefix.
        return [];
      }
      // Proceed to the next node
      // corresponding to the character in the prefix.
      current = current.children[char];
    }
    // Once the end of the prefix is reached,
    // find all words starting from this node.
    return this._findAllWords(current, prefix);
  }

  // Helper function to recursively find all words starting from a given node
  _findAllWords(node, prefix) {
    // Initialize an array to hold all the words found.
    let words = [];
    // If the current node marks the end of a word...
    if (node.endOfWord) {
      // ...add the prefix to the list of words as it's a valid word.
      words.push(prefix);
    }

    // Iterate over each child node.
    for (let char in node.children) {
      // Recursively find all words from the child node,
      // adding the current character to the prefix.
      words = words.concat(
        this._findAllWords(node.children[char], prefix + char)
      );
    }

    // Return the list of words found.
    return words;
  }

  // Method to display all words stored in the Trie
  displayAllWords() {
    // Initialize an array to hold all the words found
    let words = [];

    // Recursive helper function to find all words from a given node
    const findAllWords = (node, currentWord) => {
      // If the current node marks the end of a word...
      if (node.endOfWord) {
        // ...add the current word to the list of words
        words.push(currentWord);
      }

      // Iterate over each child node
      for (let char in node.children) {
        // Recursively call the function for each child node,
        // adding the character to the current word
        findAllWords(node.children[char], currentWord + char);
      }
    };

    // Start the recursive process from the root node with an empty string
    findAllWords(this.root, "");
    return words; // Return the list of words found in the Trie
  }

  // Displays an array that will represent the Trie
  // in level-order, with each sub-array representing a level of the Trie.
  // such as: [ [ 'c' ], [ 'a' ], [ 't', 'r', 'p' ] ]
  displayTrie() {
    // Initialize the array that will hold the level-order representation of the Trie.
    let result = [];
    // Start with a queue containing the root node.
    let queue = [this.root];

    // Continue looping until there are no more nodes to process.
    while (queue.length > 0) {
      // Number of nodes at the current level.
      let currentLevelSize = queue.length;
      // Array to hold the values of nodes at the current level.
      let currentLevel = [];

      // Iterate over all nodes at the current level.
      for (let i = 0; i < currentLevelSize; i++) {
        // Get the next node from the queue.
        let currentNode = queue.shift();
        // If the current node is not the root node...
        if (currentNode !== this.root) {
          // ...add its value to the current level array.
          currentLevel.push(currentNode.value);
        }

        // Iterate over all children of the current node.
        for (let child in currentNode.children) {
          // Add each child node to the queue to process at the next level.
          queue.push(currentNode.children[child]);
        }
      }

      // If the current level has nodes...
      if (currentLevel.length > 0) {
        // ...add the array of values for this level to the result array.
        result.push(currentLevel);
      }
    }

    // Return the level-order representation of the Trie.
    return result;
  }
}

let trie = new Trie();
trie.insert("cat");
trie.insert("cap");
trie.insert("car");
trie.insert("card");
trie.insert("caramel");

trie.autocomplete("car");
trie.delete("car");
trie.autocomplete("ca");

trie.displayAllWords()
trie.displayTrie()

Array based Trie implementation:

class TrieNode {
  constructor() {
    // A node in the Trie may have a maximum of 26 children,
    // one for each letter of the English alphabet
    this.children = new Array(26);
    this.endOfWord = false; // Indicates whether the node represents the end of a word
  }
}

class Trie {
  constructor() {
    // The root node, which acts as the
    // starting point of the Trie and holds no character value.
    this.root = new TrieNode();
  }

  // Inserts a word into the trie
  insert(word) {
    // Start at the root node of the Trie.
    let current = this.root;
    // Iterate over each character in the word.
    for (let char of word) {
      // Convert the character to its corresponding index in the children array.
      const index = this._charToIndex(char);
      // If there is no node at this index...
      if (!current.children[index]) {
        // ...create a new TrieNode at this index.
        current.children[index] = new TrieNode();
      }
      // Move to the node that represents the current character.
      current = current.children[index];
    }
    // Mark the end of the word by setting endOfWord to true at the final node.
    current.endOfWord = true;
  }

  // Search for a word in the trie
  search(word) {
    // Start at the root node of the Trie.
    let current = this.root;
    // Iterate over each character in the word.
    for (let char of word) {
      // Convert the character to its corresponding index in the children array.
      const index = this._charToIndex(char);
      // If there is no node at this index...
      if (!current.children[index]) {
        // ...the word does not exist in the trie.
        return false;
      }
      // Move to the node that represents the current character.
      current = current.children[index];
    }
    // Return true if the final node marks the end of a word,
    // indicating that the word exists in the Trie.
    return current.endOfWord;
  }

  // Deletes a word from the trie
  delete(word) {
    const deleteRecursively = (node, idx) => {
      // Check if the end of the word is reached
      if (idx === word.length) {
        // The word is not in the trie
        if (!node.endOfWord) return false;
        // Mark the endOfWord as false
        node.endOfWord = false;
        // Check if node has no children and can be deleted
        return Object.keys(node.children).every((key) => !node.children[key]);
      }

      // Get the index of the current character
      const charIndex = this._charToIndex(word[idx]);
      // Get the child node corresponding to the current character
      const childNode = node.children[charIndex];

      // If the child node does not exist, the word is not in the trie
      if (!childNode) return false;

      // Recursively call delete on the child node
      const shouldDeleteChild = deleteRecursively(childNode, idx + 1);

      if (shouldDeleteChild) {
        // Delete the child node if it is no longer needed
        delete node.children[charIndex];
        // Check if the current node has no more children
        // and is not the end of another word
        return (
          !node.endOfWord &&
          Object.keys(node.children).every((key) => !node.children[key])
        );
      }

      // If the child node should not be deleted, return false
      return false;
    };

    // Start the deletion process from the root
    deleteRecursively(this.root, 0);
  }

  // Checks if there is any word in the trie that starts with the given prefix
  startsWith(prefix) {
    // Start at the root node of the Trie
    let current = this.root;
    // Iterate over each character in the prefix
    for (let char of prefix) {
      // Get the index of the current character
      const index = this._charToIndex(char);
      // If the current node doesn't have a child for the given character, return false
      if (!current.children[index]) {
        return false;
      }
      // Move to the child node associated with the current character
      current = current.children[index];
    }
    // All characters in the prefix are found, return true
    return true;
  }

  // Finds all words in the trie that start with the given prefix
  autocomplete(prefix) {
    // Start at the root node
    let current = this.root;
    // Iterate over each character in the prefix
    for (let char of prefix) {
      // Convert the character to its corresponding index
      const index = this._charToIndex(char);
      // If there is no child for this character,
      // return an empty array (no words with this prefix)
      if (!current.children[index]) {
        return [];
      }
      // Move to the child node for the current character
      current = current.children[index];
    }
    // Call the helper function to find all words starting from the current node
    return this._findAllWords(current, prefix);
  }

  // Helper function to convert a character into an index (0-25)
  _charToIndex(char) {
    // Convert 'a' to 0, 'b' to 1, ..., 'z' to 25
    return char.charCodeAt(0) - "a".charCodeAt(0);
  }

  // Recursive helper function to find all words starting from a given node
  _findAllWords(node, prefix) {
    // Initialize an array to hold words
    let words = [];
    // If this node marks the end of a word, add the prefix to the list of words
    if (node.endOfWord) {
      words.push(prefix);
    }
    // Iterate over each potential child node
    for (let i = 0; i < node.children.length; i++) {
      const child = node.children[i];
      // If the child node exists...
      if (child !== undefined) {
        // Convert the index back to a character
        const char = String.fromCharCode("a".charCodeAt(0) + i);
        // Recursively find words from the child node,
        // adding the current character to the prefix
        words = words.concat(this._findAllWords(child, prefix + char));
      }
    }
    // Return the list of words found
    return words;
  }

  displayAllWords() {
    // Define a recursive function to find all words from a given Trie node
    const findAllWords = (node, prefix) => {
      // Initialize an array to store words
      let words = [];
      // If the current node represents the end of a word, 
      // add the prefix to the words array
      if (node.endOfWord) {
        words.push(prefix);
      }
      // Iterate over the possible children of the node
      for (let i = 0; i < node.children.length; i++) {
        // Get the child node at index i
        const child = node.children[i];
        // If the child node exists...
        if (child) {
          // Convert the index to a character
          const char = String.fromCharCode("a".charCodeAt(0) + i);
          // Recursively find all words from the child node
          // and concatenate them with the current prefix
          words = words.concat(findAllWords(child, prefix + char));
        }
      }
      // Return the array of words found from this node
      return words;
    };

    // Start the recursive word finding process from
    // the root node with an empty string as the initial prefix
    return findAllWords(this.root, "");
  }

  // Displays an array that will represent the Trie
  // in level-order, with each sub-array representing a level of the Trie.
  // such as: [ [ 'c' ], [ 'a' ], [ 't', 'r', 'p' ] ]
  // empty indexes are indicated with "null"
  displayTrie() {
    // Initialize an array to hold the level order representation of the Trie
    const result = [];
    // Start with a queue containing the root node and its level
    const queue = [{ node: this.root, level: 0 }];

    // Continue until there are no nodes left to process
    while (queue.length > 0) {
       // Dequeue the next node along with its level
      const { node, level } = queue.shift();

      // Initialize the sub-array for this level if it doesn't already exist
      if (result[level] === undefined) {
        result[level] = [];
      }

      // Flag to check if the current node has any children
      let hasChildren = false;
      // Create an array representing the current node's children
      const childrenRepresentation = new Array(26).fill(null);
      // Iterate through the possible children
      for (let i = 0; i < node.children.length; i++) {
        // If a child node exists at index i...
        if (node.children[i]) {
          // Convert the index to a character
          const char = String.fromCharCode('a'.charCodeAt(0) + i);
          // Place the character in the children representation array
          childrenRepresentation[i] = char;
          // Enqueue the child node along with the next level information
          queue.push({ node: node.children[i], level: level + 1 });
          // Mark that the current node has children
          hasChildren = true;
        }
      }

      // Only add the children representation if the node has children
      if (hasChildren) {
        result[level].push(childrenRepresentation);
      }
    }

    // Return the level order representation of the Trie
    return result;
  }
}

let trie = new Trie();
trie.insert("cat");
trie.insert("cap");
trie.insert("car");
trie.insert("card");
trie.insert("caramel");

trie.autocomplete("car");
trie.delete("car");
trie.autocomplete("ca");

trie.displayAllWords()
trie.displayTrie()

Deep Dive into Data structures using Javascript - Priority Queue

Şahin Arslan — Sun, 12 Nov 2023 21:07:15 +0000

Priority Queue is a versatile and efficient data structure, that represents sophisticated and practical approach to data processing. By design, elements are managed not just by the order of their arrival but according to their priority. This mechanism plays an important role in optimizing tasks in numerous applications, from algorithm design to system resource management.

While Priority Queues can be implemented with various data structures like Arrays, Linked Lists, Heaps or Binary Trees - using a Binary Heap is the most popular choice and that's the implementation we will be focusing on through this article.

Binary Heaps, a common implementation of Heaps, lay the groundwork for Priority Queues. They come in two main types: Max Heaps and Min Heaps. Max Heaps places greater values to be processed first, while the Min Heaps does the opposite - lesser values are favored to be processed first. For Priority Queues, although both types are applicable, the Min Heap version is often favored due to its effectiveness in sorting elements where lower values signify higher priority. I will be sharing an implementation that covers both cases at the end of this article.

In order to fully understand Priority Queues, a solid understanding of Heaps is essential. Therefore the tone of this article is assuming you are familiar with the concept of Heaps. If that’s not the case or you need a quick refreshment, I’d suggest you start from the “Heap” article by following the link below, then come back and continue here later:

Deep dive into data structures using Javascript - Heap

Anatomy of a Priority Queue

Priority Queue format we are discussing here is built on top of Binary Heap, therefore the anatomy is almost identical - except one distinct aspect: the utilization of a "priority" property for each element.

This is the feature where Priority Queue differs from a standard Heap. In a Min or Max heap, the placement mechanism works based on given value, while in the Priority Queue it is based on given priority. The underlying architecture of a Priority Queue is typically an array, mirroring the array representation of a Heap. In this array, each index doesn’t just hold a value but an object or a pair containing the value and its priority.

Take a look at the visual below to see the distinction between a Priority Queue using a Min Heap as underlying structure versus a regular Min Heap. Both are shown with their Binary Heap representation, we add the same values following the same order. But there is a small twist - each element added to the Priority Queue has different priorities assigned to them:

When to Use a Priority Queue

Priority Queues are mostly suited for particular scenarios where the order of item processing is important. Let’s start with taking a look at the Big O of common operations:

Insertion Operation (Enqueue): The insertion of an element, which involves adding a value with a given priority, typically requires O(log n) time complexity. The newly added element may need to ascend towards the front of the queue, especially if it has a high priority, respecting the queue's ordering rules.

Removal Operation (Dequeue): Removing the element with the highest priority, which is generally at the front of the queue, also takes O(log n) time complexity. This operation may trigger a reorganization of the queue to ensure the next highest priority element comes to the forefront.

Peek Operation: Accessing the element with the highest priority is a constant time operation, O(1), since it is always at the front of the queue, ready to be processed next.

Update Priority Operation (optional): Updating the priority of an element in the Priority Queue can vary in time complexity depending on the underlying implementation.

With a map: If an internal map is utilized to track the indices and an external reference (ID) is kept for each element, the updatePriority operation can be performed in O(log n) time complexity. This is because the map allows us to directly access the element in the heap, and the only remaining operation is the reorganization of the heap (heapify), which takes O(log n).
Without a map: In the absence of such a map, updating the priority requires a linear search to find the element, resulting in O(n) time complexity. After finding the element, we would still need to perform the heap reorganization, but the dominant factor is the linear search time.

Search Operation (optional): While not a primary function, searching for an element in a Priority Queue, due to its array-based implementation, has a time complexity of O(n). This is because it may require a linear scan to find a particular element if its priority is unknown.

Considering the time complexities above, Priority Queues prove to be exceptionally beneficial in several use cases:

Task Scheduling: Priority Queues are ideal for managing tasks where certain tasks take precedence over others due to urgency or importance.

Simulation Systems: In simulations where events are processed at varying speeds or frequencies, Priority Queues manage the event schedule effectively, making sure high-priority events are processed first.

Dijkstra’s Algorithm for Shortest Paths: Just like Heaps are used in graph algorithms, Priority Queues are crucial for efficiently finding the shortest path in a weighted graph where the processing order of nodes is determined by their path costs.

Load Balancing and Resource Management: Systems that manage computing resources often utilize Priority Queues to handle jobs according to their resource demands or time constraints.

Real-time Data Processing: In systems where data is processed in real-time, such as stock price updates or sensor data, Priority Queues makes sure that the most critical data is handled promptly.

Priority Queue implementation in Javascript

We will be using ES6 Classes to build our Priority Queue. As mentioned earlier, if we include an "updatePriority" method, we need 2 variations. One would need to involve internal map keeping track of indexes, while the other won't. Therefore I will be sharing both implementations:

A simple version that does not utilize a map for tracking element indexes, suitable for smaller data sets or when maximum performance is not critical.
An optimized version that includes a map to efficiently track and update element indexes, providing faster lookup times which are essential for larger data sets.

Here is the list of methods that we are going to implement:

Simple Priority Queue:

size(): Returns the current number of items in the priority queue.
isEmpty(): Determines whether the priority queue is empty.
peek(): Retrieves the element with the highest priority (the front of the queue) without removing it.
enqueue(value, priority): Inserts a new value with its associated priority into the queue, adjusting the queue to maintain the priority ordering.
dequeue(): Removes and returns the element with the highest priority from the queue while preserving the priority order of the remaining elements.
updatePriority(value, newPriority, equalityFn): This method allows the priority of an existing element in the queue to be changed. It first locates the element within the queue based on a given value, using the equalityFn to determine equality. If the element is found, its priority is updated to the new value specified. The queue is then reorganized to maintain the correct priority order. This reorganization involves either moving the element up (_heapifyUpFromIndex) if its new priority is higher, or moving it down (_heapifyDownFromIndex) if its new priority is lower compared to its original priority. This makes sure that the queue continuously maintains its priority order even after the priorities of its elements are altered.
search(value, equalityFn): (Optional) Locates an element within the queue by its value using a custom equality function, necessary for the non-map-based implementation to update priorities without an external reference.
toSortedArray(): (Optional) Returns the heap array in a sorted format. Sorting is based on the type of Heap (Min or Max) the Priority Queue is built upon. A Min Heap based Priority Queue will have the smallest element at the first index, for Max Heap based version is the opposite.

Utility methods:

_parentIndex(i), _leftChildIndex(i), _rightChildIndex(i), _hasLeftChild(i), _hasRightChild(i): Utility methods that assist in navigating the internal heap structure of the priority queue.
_heapifyUp(), _heapifyDown(): Essential methods for maintaining the heap structure after insertions or deletions, helps to keep the heap property of the queue based on the priority ordering.
_heapifyUpFromIndex(i), _heapifyDownFromIndex(i): Essential methods for maintaining the heap structure after priority updates, helps to keep the heap property of the queue based on the priority ordering.

Optimized Priority Queue:

Optimized version shares the majority of methods as the simple version, but there are a couple differences with the methods below:

enqueue(value, priority): While adding a new element, the optimized version not only inserts the value into the heap but also updates an internal map. This map tracks the index of each element using its unique ID as the key. This makes sure that the element's position can be quickly referenced during future operations, providing a significant performance boost for priority updates.

dequeue(): The removal process in the optimized version is augmented by the necessity to maintain the internal map's accuracy. After the highest priority element is removed from the heap, the map is updated to remove the entry corresponding to this element's ID. If the last element in the heap is moved to the front (to replace the removed top element), the map is also updated to reflect this new position. This makes sure that subsequent operations on the queue can proceed with the most current information.

updatePriority(id, newPriority): This method in the optimized priority queue is more efficient version for updating the priority of an existing element. The cornerstone of this optimization lies in the use of an internal map (this._map), which stores the indexes of elements in the heap against their unique IDs. When this method is called, it first retrieves the element's index from the heap using its unique ID, thanks to the map. This approach is significantly more efficient than searching through the entire heap, as it allows for direct access to the element in constant time.

Once the index is obtained, the method checks if the element exists (if the index is not undefined). If the element is found, its priority in the heap is updated to the new value. The queue then needs to adjust to maintain the priority order. This adjustment depends on whether the new priority is higher or lower than the old one. For a higher new priority (a lower numeric value in a min-heap), the element is moved up the heap using _heapifyUpFromIndex. For a lower new priority (a higher numeric value), the method employs _heapifyDownFromIndex to move the element down the heap.

This map-based approach in the optimized priority queue is specially useful with large data sets, or in scenarios where frequent updates to priorities are common.

_generateId(): This method is a private utility function used within the optimized priority queue class. Its purpose is to generate a unique identifier (ID) for each new element added to the queue. It works by maintaining an internal counter (_nextId) that is incremented each time a new ID is required. When called, the method returns the current value of _nextId and then increments the counter. This mechanism provides every element in the queue a distinct ID, which is crucial for efficiently updating an element's priority in the queue - as this ID is used to quickly locate the element in the internal heap structure. This method is an essential part of the efficiency optimizations in this priority queue implementation.

Priority Queues can be initially challenging to grasp. As mentioned earlier, I would recommend getting familiar with the underlying heap structure that a Priority Queue is built upon — specifically, its array representation. This involves understanding how to identify the parent, left, and right children of any given element using simple array index calculations. Once comfortable with navigating this structure, one should then explore the dynamic nature of Priority Queues, focusing on how the enqueue and dequeue operations work in tandem with heapifyUp and heapifyDown to maintain order according to priority levels.

Additionally, I’ve also included line-by-line explanations for each method in the implementation for you to follow up what is happening in the code. I hope this article helped you to understand what Priority Queues are and how they work! I’d like to encourage you to experiment with the implementations below in your favorite code editor. Thanks for reading!

Simple Priority Queue implementation:

class PriorityQueue {
  // The constructor method is called when a new instance of Priority Queue is created.
  constructor(comparator) {
    // Initialize the heap array.
    this.heap = [];

    // Set the comparator method for comparing nodes in the heap.
    // If no comparator function is provided, it defaults to a comparison
    // function that sorts in ascending order (a min-heap).
    this.comparator = comparator || ((a, b) => a - b);
  }

  // Return the number of items in the heap.
  size() {
    return this.heap.length;
  }

  // Check if the heap is empty.
  isEmpty() {
    return this.size() === 0;
  }

  // Get the top element in the heap without removing it.
  // For a min-heap, this will be the smallest element;
  // for a max-heap, it will be the largest.
  peek() {
    return this.heap[0] ? this.heap[0].value : null;
  }

  // Add a new value to the heap.
  enqueue(value, priority) {
    // First, add the new value to the end of the array.
    this.heap.push({ value, priority });
    // Then, move the new value up the heap to its correct position.
    this._heapifyUp();
  }

  // Remove and return the top element in the heap.
  dequeue() {
    // If the heap is empty, just return null
    if (this.isEmpty()) {
      return null;
    }
    // Save the top element so we can return it later
    const poppedValue = this.peek();

    // If there is more than one node in the heap, move the last node to the top.
    const bottom = this.size() - 1;
    if (bottom > 0) {
      this._swap(0, bottom);
    }

    // Remove the last node (which is now the top node) from the heap.
    this.heap.pop();

    // Move the new top node down the heap to its correct position.
    this.heapifyDown();

    // Finally, return the original top element.
    return poppedValue;
  }

  // This method updates the priority of a specific value in the heap.
  updatePriority(value, newPriority, equalityFn) {
    // Find the index of the item in the heap that matches the given value.
    const index = this.heap.findIndex((item) => equalityFn(item.value, value));

    // If the item is not found, exit the function.
    if (index === -1) {
      return; // Item not found
    }

    // Update the priority of the found item to the new priority.
    const oldPriority = this.heap[index].priority;
    this.heap[index].priority = newPriority;

    // Re-heapify based on whether the new priority is higher or lower than the old priority.
    if (
      this.comparator({ priority: newPriority }, { priority: oldPriority }) < 0
    ) {
      // If the new priority is higher, heapify up from the current index.
      this._heapifyUpFromIndex(index);
    } else {
      // If the new priority is lower, heapify down from the current index.
      this._heapifyDownFromIndex(index);
    }
  }

  search(value, equalityFn) {
    // Find the item in the heap using the provided equality function
    const item = this.heap.find((item) => equalityFn(item.value, value));
    return item ? item : null;
  }

  toSortedArray() {
    const sortedList = [...this.heap];
    return sortedList.sort((a, b) => this.comparator(a.priority, b.priority));
  }

  // ********************* Helper methods below: *********************

  // Method to get the index of a node's parent.
  _parentIndex(index) {
    /*
    About Math.floor:

    We take the floor value of the division to 
    make sure we get the nearest lower integer value. 
    This is important because array indexes
    are integer values and cannot have fractional parts.
    */
    return Math.floor((index - 1) / 2);
  }

  // Method to get the index of a node's left child.
  _leftChildIndex(index) {
    return 2 * index + 1;
  }

  // Method to get the value of a node's right child.
  _rightChildIndex(index) {
    return 2 * index + 2;
  }

  // Method to check if a node has left child.
  // It returns true if the left child index is within the valid range of heap indexes,
  // which indicates that a left child exists.
  _hasLeftChild(index) {
    return this._leftChildIndex(index) < this.size();
  }

  // Method to check if a node has right child.
  // It returns true if the right child index is within the valid range of heap indexes,
  // which indicates that a right child exists.
  _hasRightChild(index) {
    return this._rightChildIndex(index) < this.size();
  }

  // Method to swap the values of two nodes in the heap.
  _swap(i, j) {
    // Swap the values of elements at indices i and j without using a temporary variable:
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  // This method rearranges the heap after adding a new element.
  _heapifyUp() {
    // Start with the last element added to the heap
    let nodeIndex = this.size() - 1;

    // Loop until the node reaches the root or the heap property is maintained
    while (
      nodeIndex > 0 &&
      // Compare the current node with its parent
      this.comparator(
        this.heap[nodeIndex].priority,
        this.heap[this._parentIndex(nodeIndex)].priority
      ) < 0
    ) {
      // If the current node's priority is higher than its parent, swap them
      this._swap(nodeIndex, this._parentIndex(nodeIndex));
      // Move to the parent node and continue
      nodeIndex = this._parentIndex(nodeIndex);
    }
  }

  // This method rearranges the heap after removing the top element.
  _heapifyDown() {
    // Start with the root node
    let currNodeIndex = 0;

    // Loop as long as the current node has a left child
    while (this._hasLeftChild(currNodeIndex)) {
      // Assume the left child is the smaller child
      let smallerChildIndex = this._leftChildIndex(currNodeIndex);

      // Check if the right child exists and is smaller than the left child
      if (
        this._hasRightChild(currNodeIndex) &&
        this.comparator(
          this.heap[this._rightChildIndex(currNodeIndex)].priority,
          this.heap[smallerChildIndex].priority
        ) < 0
      ) {
        // If so, the right child is the smaller child
        smallerChildIndex = this._rightChildIndex(currNodeIndex);
      }

      // If the current node is smaller than its smallest child, the heap is correct
      if (
        this.comparator(
          this.heap[currNodeIndex].priority,
          this.heap[smallerChildIndex].priority
        ) <= 0
      ) {
        break;
      }

      // Otherwise, swap the current node with its smallest child
      this._swap(currNodeIndex, smallerChildIndex);
      // Move to the smaller child and continue
      currNodeIndex = smallerChildIndex;
    }
  }

  // This method rearranges the heap upwards from a given index.
  _heapifyUpFromIndex(index) {
    // Start from the given index
    let currentIndex = index;

    // Continue as long as the current index is not the root
    while (currentIndex > 0) {
      // Find the parent index of the current index
      let parentIndex = this._parentIndex(currentIndex);

      // Compare the current node with its parent
      if (
        this.comparator(this.heap[currentIndex], this.heap[parentIndex]) < 0
      ) {
        // If current node is smaller than the parent, swap them
        this._swap(currentIndex, parentIndex);
        // Move to the parent node and continue
        currentIndex = parentIndex;
      } else {
        // If the current node is not smaller than the parent, stop the process
        break;
      }
    }
  }

  // This method rearranges the heap downwards from a given index.
  _heapifyDownFromIndex(index) {
    // Start from the given index
    let currentIndex = index;

    // Continue as long as the current node has a left child
    while (this._hasLeftChild(currentIndex)) {
      // Assume the left child is the smaller child
      let smallerChildIndex = this._leftChildIndex(currentIndex);

      // Check if the right child exists and is smaller than the left child
      if (
        this._hasRightChild(currentIndex) &&
        this.comparator(
          this.heap[this._rightChildIndex(currentIndex)],
          this.heap[smallerChildIndex]
        ) < 0
      ) {
        // If so, the right child is the smaller child
        smallerChildIndex = this._rightChildIndex(currentIndex);
      }

      // If the current node is smaller or equal to its smallest child, the heap is correct
      if (
        this.comparator(
          this.heap[currentIndex],
          this.heap[smallerChildIndex]
        ) <= 0
      ) {
        break;
      }

      // Otherwise, swap the current node with its smallest child
      this._swap(currentIndex, smallerChildIndex);
      // Move to the smaller child and continue
      currentIndex = smallerChildIndex;
    }
  }
}

// Using as MaxPriorityQueue:

class MaxPriorityQueue extends PriorityQueue {
  constructor() {
    // MaxPriorityQueue uses a comparator that sorts the internal heap in descending order
    super((a, b) => b - a);
  }
}

// Usage (works as MinPriorityQueue by default)

const priorityQueue = new PriorityQueue();

priorityQueue.enqueue("A", 40);
priorityQueue.enqueue("B", 10);
priorityQueue.enqueue("C", 50);
priorityQueue.enqueue("D", 30);
priorityQueue.enqueue("E", 60);
priorityQueue.enqueue("G", 50);
priorityQueue.enqueue("F", 20);

priorityQueue.toSortedArray();

priorityQueue.updatePriority("A", 5, (a, b) => a === b);
priorityQueue.updatePriority("E", 7, (a, b) => a === b);

priorityQueue.toSortedArray();

Optimized Priority Queue implementation:

class PriorityQueue {
  // The constructor method is called when a new instance of Priority Queue is created.
  constructor(comparator) {
    // Initialize the heap array.
    this.heap = [];

    // Set the comparator method for comparing nodes in the heap.
    // If no comparator function is provided, it defaults to a comparison
    // function that sorts in ascending order (a min-heap).
    this.comparator = comparator || ((a, b) => a - b);

    // Map stores internal indexes for more efficient updatePriority
    this._map = new Map();

    // Counter for the next ID to assign
    this._nextId = 0;
  }

  // Return the number of items in the heap.
  size() {
    return this.heap.length;
  }

  // Check if the heap is empty.
  isEmpty() {
    return this.size() === 0;
  }

  // Get the top element in the heap without removing it.
  // For a min-heap, this will be the smallest element;
  // for a max-heap, it will be the largest.
  peek() {
    return this.heap[0] ? this.heap[0].value : null;
  }

  // This method adds a new element with its priority into the priority queue.
  enqueue(value, priority) {
    // Generate a unique identifier for the new element.
    const _id = this._generateId();

    // Create an entry object containing the value, priority, and the generated ID.
    const entry = { value, priority, _id };

    // Add the new entry to the end of the heap array.
    this.heap.push(entry);

    // Store the index of this new entry in the map using its ID for efficient lookups.
    // This is important for the updatePriority operation, allowing us to quickly find an element's index.
    this._map.set(_id, this.heap.length - 1);

    // Reorganize the heap to maintain the heap property after adding a new element.
    // This ensures that the heap structure is maintained (either min-heap or max-heap).
    this._heapifyUp();

    // Return the unique ID of the new entry. This ID can be used later for operations like updatePriority.
    return _id;
  }

  // This method removes and returns the element with the highest priority (at the root of the heap).
  dequeue() {
    // Check if the heap is empty. If it is, return null.
    if (this.isEmpty()) {
      return null;
    }

    // The item to be dequeued is always at the root of the heap (index 0).
    const dequeuedItem = this.heap[0];

    // Remove the dequeued item's entry from the map using its unique ID.
    // This keeps the map updated with only current heap elements.
    this._map.delete(dequeuedItem._id);

    // Find the index of the last element in the heap.
    const bottom = this.size() - 1;

    // Check if there are more elements left in the heap after dequeuing.
    if (bottom > 0) {
      // Replace the root of the heap with the last element.
      this.heap[0] = this.heap[bottom];

      // Update the position of the moved item in the map.
      this._map.set(this.heap[0]._id, 0);

      // Remove the last element (now moved to the root) from the heap.
      this.heap.pop();

      // Reorganize the heap to maintain the heap property after the root change.
      this._heapifyDown();
    } else {
      // If there is only one element in the heap, remove it and clear the map.
      this.heap.pop();
      this._map.clear();
    }

    // Return the value of the dequeued item.
    return dequeuedItem.value;
  }

  // This method updates the priority of an element in the priority queue.
  updatePriority(id, newPriority) {
    // Retrieve the index of the element in the heap using the unique ID from the map.
    const index = this._map.get(id);

    // If the element with the given ID is not found in the map, exit the function early.
    if (index === undefined) {
      return;
    }

    // Retrieve the old priority of the element for comparison.
    const oldPriority = this.heap[index].priority;

    // Update the priority of the element in the heap with the new priority.
    this.heap[index].priority = newPriority;

    // Decide whether to heapify up or down based on the new priority.
    // If the new priority is higher (smaller value for min-heap), heapify up.
    // If the new priority is lower (larger value for min-heap), heapify down.
    if (
      this.comparator({ priority: newPriority }, { priority: oldPriority }) < 0
    ) {
      this._heapifyUpFromIndex(index);
    } else {
      this._heapifyDownFromIndex(index);
    }
  }

  search(value, equalityFn) {
    // Find the item in the heap using the provided equality function
    const item = this.heap.find((item) => equalityFn(item.value, value));
    return item ? item : null;
  }

  toSortedArray() {
    const sortedList = [...this.heap];
    return sortedList.sort((a, b) => this.comparator(a.priority, b.priority));
  }

  // ********************* Helper methods below: *********************

  // Method to generate unique ID for internal lookup map
  _generateId() {
    return this._nextId++; // Increment the ID counter and return the new ID
  }

  // Method to get the index of a node's parent.
  _parentIndex(index) {
    /*
    About Math.floor:

    We take the floor value of the division to 
    make sure we get the nearest lower integer value. 
    This is important because array indexes
    are integer values and cannot have fractional parts.
    */
    return Math.floor((index - 1) / 2);
  }

  // Method to get the index of a node's left child.
  _leftChildIndex(index) {
    return 2 * index + 1;
  }

  // Method to get the value of a node's right child.
  _rightChildIndex(index) {
    return 2 * index + 2;
  }

  // Method to check if a node has left child.
  // It returns true if the left child index is within the valid range of heap indexes,
  // which indicates that a left child exists.
  _hasLeftChild(index) {
    return this._leftChildIndex(index) < this.size();
  }

  // Method to check if a node has right child.
  // It returns true if the right child index is within the valid range of heap indexes,
  // which indicates that a right child exists.
  _hasRightChild(index) {
    return this._rightChildIndex(index) < this.size();
  }

  // Method to swap the values of two nodes in the heap.
  _swap(i, j) {
    // Swap the elements in the heap array at indices i and j.
    // This is commonly needed during heapify operations to maintain the heap invariant.
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];

    // After swapping the elements in the heap array, their positions (indices) have changed.
    // We must update the map to reflect these new positions.
    // Set the map entry for the element that was originally at index i (now at index j)
    // to the new index (j). The _id property is used as the key in the map.
    this._map.set(this.heap[i]._id, i);

    // Similarly, set the map entry for the element that was originally at index j (now at index i)
    // to the new index (i). As before, the _id property is used as the key in the map.
    this._map.set(this.heap[j]._id, j);
  }

  // This method rearranges the heap after adding a new element.
  _heapifyUp() {
    // Start with the last element added to the heap
    let nodeIndex = this.size() - 1;

    // Loop until the node reaches the root or the heap property is maintained
    while (
      nodeIndex > 0 &&
      // Compare the current node with its parent
      this.comparator(
        this.heap[nodeIndex].priority,
        this.heap[this._parentIndex(nodeIndex)].priority
      ) < 0
    ) {
      // If the current node's priority is higher than its parent, swap them
      this._swap(nodeIndex, this._parentIndex(nodeIndex));
      // Move to the parent node and continue
      nodeIndex = this._parentIndex(nodeIndex);
    }
  }

  // This method rearranges the heap after removing the top element.
  _heapifyDown() {
    // Start with the root node
    let currNodeIndex = 0;

    // Loop as long as the current node has a left child
    while (this._hasLeftChild(currNodeIndex)) {
      // Assume the left child is the smaller child
      let smallerChildIndex = this._leftChildIndex(currNodeIndex);

      // Check if the right child exists and is smaller than the left child
      if (
        this._hasRightChild(currNodeIndex) &&
        this.comparator(
          this.heap[this._rightChildIndex(currNodeIndex)].priority,
          this.heap[smallerChildIndex].priority
        ) < 0
      ) {
        // If so, the right child is the smaller child
        smallerChildIndex = this._rightChildIndex(currNodeIndex);
      }

      // If the current node is smaller than its smallest child, the heap is correct
      if (
        this.comparator(
          this.heap[currNodeIndex].priority,
          this.heap[smallerChildIndex].priority
        ) <= 0
      ) {
        break;
      }

      // Otherwise, swap the current node with its smallest child
      this._swap(currNodeIndex, smallerChildIndex);
      // Move to the smaller child and continue
      currNodeIndex = smallerChildIndex;
    }
  }

  // This method rearranges the heap upwards from a given index.
  _heapifyUpFromIndex(index) {
    // Start from the given index
    let currentIndex = index;

    // Continue as long as the current index is not the root
    while (currentIndex > 0) {
      // Find the parent index of the current index
      let parentIndex = this._parentIndex(currentIndex);

      // Compare the current node with its parent
      if (
        this.comparator(this.heap[currentIndex], this.heap[parentIndex]) < 0
      ) {
        // If current node is smaller than the parent, swap them
        this._swap(currentIndex, parentIndex);
        // Move to the parent node and continue
        currentIndex = parentIndex;
      } else {
        // If the current node is not smaller than the parent, stop the process
        break;
      }
    }
  }

  // This method rearranges the heap downwards from a given index.
  _heapifyDownFromIndex(index) {
    // Start from the given index
    let currentIndex = index;

    // Continue as long as the current node has a left child
    while (this._hasLeftChild(currentIndex)) {
      // Assume the left child is the smaller child
      let smallerChildIndex = this._leftChildIndex(currentIndex);

      // Check if the right child exists and is smaller than the left child
      if (
        this._hasRightChild(currentIndex) &&
        this.comparator(
          this.heap[this._rightChildIndex(currentIndex)],
          this.heap[smallerChildIndex]
        ) < 0
      ) {
        // If so, the right child is the smaller child
        smallerChildIndex = this._rightChildIndex(currentIndex);
      }

      // If the current node is smaller or equal to its smallest child, the heap is correct
      if (
        this.comparator(
          this.heap[currentIndex],
          this.heap[smallerChildIndex]
        ) <= 0
      ) {
        break;
      }

      // Otherwise, swap the current node with its smallest child
      this._swap(currentIndex, smallerChildIndex);
      // Move to the smaller child and continue
      currentIndex = smallerChildIndex;
    }
  }
}

// Using as MaxPriorityQueue:

class MaxPriorityQueue extends PriorityQueue {
  constructor() {
    // MaxPriorityQueue uses a comparator that sorts the internal heap in descending order
    super((a, b) => b - a);
  }
}

// Usage (works as MinPriorityQueue by default)

// Usage
const priorityQueue = new PriorityQueue();

priorityQueue.enqueue("A", 40);
priorityQueue.enqueue("B", 10);
priorityQueue.enqueue("C", 50);
priorityQueue.enqueue("D", 30);
priorityQueue.enqueue("E", 60);

// keep track of ids:
const idJohn = priorityQueue.enqueue({ message: "hey", name: "john" }, 22);
const idA = priorityQueue.enqueue("F", 20);

console.log("BEFORE:");

priorityQueue.toSortedArray();

console.log("AFTER:");

// Now use the ID to update the priority
priorityQueue.updatePriority(idA, 1);
priorityQueue.updatePriority(idJohn, 55);

priorityQueue.toSortedArray();

Deep Dive into Data structures using Javascript - Heap

Şahin Arslan — Mon, 21 Aug 2023 17:00:09 +0000

Heap is a fundamental data structure that is constructed as a specialized form of a complete binary tree. They are known to be efficient at organizing data for quick access to the highest or lowest value element based on the "Heap property".

"Heap property" can be classified into two main types: Max Heaps and Min Heaps. In a Max Heap, each parent node has a value greater than or equal to its child nodes, while in a Min Heap, each parent node has a value less than or equal to its child nodes. Heaps are widely used to create efficient algorithms and support operations for priority queues. They are essential for many applications.

There are various forms of heaps, the most common implementation is the "Binary Heap" - which we will focus on in this article. The tone of this article is assuming you are at least familiar with the concept of Tree data structure and Binary Tree. If that’s not the case or you need a quick refreshment, I’d suggest you start from the “Introduction to Trees” article by following the link below, then come back and continue here later:

Deep dive into data structures using Javascript - Introduction to Trees

Anatomy of a Binary Heap

Heap has an interesting anatomy. It follows the structural design of a complete binary tree - which means that all levels of the tree, except possibly the last, are completely filled, and the nodes in the last level are aligned to the left. The most interesting part is the underlying structure used to achieve this binary tree-like behavior is not a traditional binary tree. Instead, an Array is utilized to represent the Heap to allow efficient access and manipulation of the elements.

Every Heap has two important properties:

Heap Order Property: This property determines the relationship between parent and child nodes. In a Max Heap, parents have values greater than or equal to their children. In a Min Heap, parents have values lesser than or equal to their children.

When it comes to implementations, Min and Max Heaps are nearly identical, except for one key difference: the 'comparator.' The comparator is a property that defines the order of the heap. The usual approach is to have a base Heap class, and then extend it by providing a comparator that specifies the desired heap order.

Heap Shape Property: This property guarantees the completeness of the binary tree forming the heap, where all levels, except potentially the last, are fully filled, and the nodes in the last level are arranged in a left-to-right fashion.

In order to maintain these properties and the binary-tree-like behavior, we utilize an array by employing various formulas - such as determining the parent, left, or right child of any element within the Heap.

They play an important role when we maintain the order of the Heap during insertion or deletions. Let's start with taking a deeper look at how Array representation works in practice.

Array Representation of Binary Heap in Detail

Heap representation in an Array is a popular implementation choice due to its efficient memory usage. In this representation, the positions of the nodes in the heap are mapped to indexes in the array. To figure out the tree-like node positions such as parent, left or right child nodes, we use 3 different formulas:

Parent: The parent node of a node at index ("i") can be found at the position determined by (i - 1) / 2 using integer division. In Javascript, this calculation is wrapped with a Math.floor method, such as: Math.floor((i - 1) / 2). The reason we need the floor value of the division is to make sure we get the nearest lower integer value. This is important because array indexes are integer values and cannot have fractional parts.
Left child: The left children of a node at index ("i") can be found at positions calculated using the formula 2i+1 or (2 x i) + 1
Right child: The right children of a node at index ("i") can be found at positions calculated using the formula 2i+2 or (2 x i) + 2

Take a look at the visual down below to see a basic example of how all these formulas work in practice:

How does Heap order stays maintained

The order of a heap is maintained through a process known as "heapifying". There are two types of heapify operations: heapifyUp (also known as siftUp or bubbleUp), which is usually performed after an insertion, and heapifyDown (also known as siftDown or bubbleDown), which is generally done after a removal.

Insertion and heapifyUp

When a new element is inserted into a heap, it is initially placed at the next available position in the array representation of the heap (which is the end of the array). But this might violate the heap property as the newly inserted element might be greater (or smaller, in case of a min heap) than its parent.

To restore the heap property, the heapifyUp operation is performed. During heapifyUp, we compare the inserted element with its parent. If the inserted element is smaller than it's parent in a min heap (or larger in a max heap), then we swap the element with its parent. We continue this process up the heap until the heap property is restored, i.e., each parent node is greater (or smaller, for a min heap) than its child nodes.

In simpler terms:

We insert the element at the end of the array.
We bubble up the newly inserted element by starting from the last node.
We take 2 actions on each step: first we compare a node with it's parent and swap their values if necessary, then move to the next parent until we reach to the root node.

Take a closer look at the gif below to visualize how heapifyUp works in practice in a Min Heap:

- Visual generated at: https://www.cs.usfca.edu/~galles/visualization/Heap.html

Removal and heapifyDown

When an element is removed from a heap, we typically remove the root element, as this operation can be performed in constant time. But this leaves a hole at the root of the heap. To fill this gap, we move the last element in the heap into the root position. This might violate the heap property, as this element element might be larger (or less, in case of a max heap) than its children.

To restore the heap property, the heapifyDown operation is performed. During heapifyDown, we compare the root element with its children. If the root element is larger than either of its children in a min heap (or smaller in a max heap), we swap the root element with its smaller (or larger, for a max heap) child. We continue this process down the heap until the heap property is restored.

These heapify operations ensure that a heap maintains its order and satisfies the heap property at all times, whether we're adding new elements or removing existing ones from the heap. By using an array representation and the heapifyUp and heapifyDown operations, we can guarantee that the heap remains balanced, making operations like insertions, deletions, and finding the min/max element highly efficient.

Take a closer look at the gif below to visualize how heapifyDown works in practice in a Min Heap:

- Visual generated at: https://www.cs.usfca.edu/~galles/visualization/Heap.html

When to use Heap

Heaps have unique properties that make them useful in specific situations. Let’s start with taking a look at the Big O of common operations in Heap:

Insertion Operation (Insert): It takes O(log n) time complexity. In the worst case, we may have to go up to the root (the height of the heap) while inserting.

Deletion Operation (Delete): It also takes O(log n) time complexity. Removing a node could require traversing the heap from the root to the leaf node.

Getting Minimum/Maximum (Peek): It takes O(1) time complexity. The minimum or maximum element (depending on the heap type) is always at the root.

Search (optional): Search is not the main objective of a Heap, as it is mainly used for maintaining quick access to minimum or maximum value. In case of search, since we utilize an array, the time complexity will be same as array - which is O(n)

Considering these time complexity analyses, heaps are incredibly useful in the following situations:

Priority Queues: Heaps are the preferred data structure for implementing priority queues. A priority queue is a special type of queue where each element has a priority and is served according to that priority.

Heap Sort: Heapsort is a sorting algorithm that uses a binary heap data structure. It has a time complexity of O(n log n), which makes it efficient for large datasets.

Graph Algorithms: Heaps are widely used in graph algorithms like Dijkstra's algorithm and Prim's algorithm. These algorithms require a data structure that can quickly provide the minimum or maximum element, which heaps handle efficiently.

K'th Largest/Smallest Element: Heaps can efficiently solve problems related to finding the k'th smallest or largest element in an array. This involves building a min heap or max heap and performing remove operations k times.

Sliding Window Problems: Heaps are helpful in problems where you need to find the maximum/minimum element in a sliding window. They can perform insertions and deletions in logarithmic time.

Heap implementation in Javascript

We will be using ES6 Classes to build our Heap. The MinHeap and MaxHeap subclasses are also included - they inherit from the Heap class. MinHeap uses a comparator that sorts the heap in ascending order, while MaxHeap uses a comparator that sorts the heap in descending order.

Here is the list of methods we are going to implement:

size(): Returns the number of items in the heap.
isEmpty(): Checks if the heap is empty.
peek(): Returns the top element (minimum or maximum value) in the heap without removing it.
insert(value): Adds a new value to the heap and maintains the heap property. It's a fundamental operation for adding elements to the heap.
delete(): Removes and returns the top element (minimum or maximum value) in the heap while maintaining the heap property. It's a fundamental operation for removing elements from the heap.
parentIndex(i), parentValue(i), leftChildIndex(i), leftChildValue(i), hasLeftChild(i), rightChildIndex(i), rightChildValue(i), hasRightChild(i): Helper methods for navigating the heap structure. They are relevant for calculating indexes and accessing parent and child node indexes or values.
heapifyUp(): Rearranges the heap after adding a new element. It ensures the heap property is maintained and is relevant to the insertion process.
heapifyDown(): Moves a node down the heap until it's in the correct position. It ensures the heap property is maintained and is relevant to the deletion process.
displayHeap(heap): Displays the heap as a binary tree in level-order. It's useful for visualization and debugging purposes.

Heaps are not the most advanced data structures, but they can be still tricky to understand at the beginning. My suggestion would be first getting familiar with its array representation of a binary tree - which includes how to find parent, left or right child of any element by using the array index formulas. Then taking a closer look at the mechanics of how does insert and delete utilizes heapifyUp and heapifyDown methods.

If you want to see how Heap operations work in a practical way, I highly recommend playing around with this great Heap visualizer at the link below:

https://www.cs.usfca.edu/~galles/visualization/Heap.html

Additionally, I’ve also included line-by-line explanations for each method in the implementation for you to follow up what is happening in the code. I hope this article helped you to understand what Heaps are and how they work! I’d like to encourage you to experiment with the implementation below in your favorite code editor. Thanks for reading!

Implementation of Heap in Javascript

class Heap {
  // The constructor method is called when a new instance of Heap is created.
  constructor(comparator) {
    // Initialize the heap array.
    this.heap = [];

    // Set the comparator method for comparing nodes in the heap.
    // If no comparator function is provided, it defaults to a comparison
    // function that sorts in ascending order (a min-heap).
    this.comparator = comparator || ((a, b) => a - b);
  }

  // Return the number of items in the heap.
  size() {
    return this.heap.length;
  }

  // Check if the heap is empty.
  isEmpty() {
    return this.size() == 0;
  }

  // Get the top element in the heap without removing it.
  // For a min-heap, this will be the smallest element;
  // for a max-heap, it will be the largest.
  peek() {
    return this.heap[0];
  }

  // Add a new value to the heap.
  insert(value) {
    // First, add the new value to the end of the array.
    this.heap.push(value);

    // Then, move the new value up the heap to its correct position.
    this.heapifyUp();
  }

  // Remove and return the top element in the heap.
  delete() {
    // If the heap is empty, just return null
    if (this.isEmpty()) {
      return null;
    }
    // Save the top element so we can return it later.
    const poppedValue = this.peek();

    // If there is more than one node in the heap, move the last node to the top.
    const bottom = this.size() - 1;
    if (bottom > 0) {
      this.swap(0, bottom);
    }

    // Remove the last node (which is now the top node) from the heap.
    this.heap.pop();

    // Move the new top node down the heap to its correct position.
    this.heapifyDown();

    // Finally, return the original top element.
    return poppedValue;
  }

  // Method to get the index of a node's parent.
  parentIndex(i) {
    /*
    About Math.floor:

    We take the floor value of the division to 
    make sure we get the nearest lower integer value. 
    This is important because array indexes
    are integer values and cannot have fractional parts.
    */
    return Math.floor((i - 1) / 2);
  }

  // Method to get the value of a node's parent.
  parentValue(i) {
    /*
   Check if the index is within the bounds of the heap and the parent exists. 
   If the index is less than the heap's size and the parent index is greater than or equal to 0, it means the parent exists. 
   If it doesn't exist or the index is out of bounds, we return undefined.
  */
    return i < this.size() && this.parentIndex(i) >= 0
      ? this.heap[this.parentIndex(i)]
      : undefined;
  }

  // Method to get the index of a node's left child.
  leftChildIndex(i) {
    return 2 * i + 1;
  }

  // Method to get the value of a node's left child.
  leftChildValue(i) {
    /*
   Check if the left child exists. 
   If the left child index is less than the size of the heap, it means the left child exists. 
   If it doesn't exist, we return undefined.
  */
    return this.hasLeftChild(i) ? this.heap[this.leftChildIndex(i)] : undefined;
  }

  // Method to check if a node has left child.
  // It returns true if the left child index is within the valid range of heap indexes, 
  // which indicates that a left child exists.
  hasLeftChild(i) {
    return this.leftChildIndex(i) < this.size();
  }

  // Method to get the index of a node's right child.
  rightChildIndex(i) {
    return 2 * i + 2;
  }

  // Method to get the value of a node's right child.
  rightChildValue(i) {
    /*
     Check if the right child exists. 
     If the right child index is less than the size of the heap, it means the right child exists. 
     If it doesn't exist, we return undefined.
    */
    return this.hasRightChild(i)
      ? this.heap[this.rightChildIndex(i)]
      : undefined;
  }

  // Method to check if a node has right child.
  // It returns true if the right child index is within the valid range of heap indexes, 
  // which indicates that a right child exists.
  hasRightChild(i) {
    return this.rightChildIndex(i) < this.size();
  }

  // Method to swap the values of two nodes in the heap.
  swap(i, j) {
    // Swap the values of elements at indices i and j without using a temporary variable:
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  // This method is used to rearrange the heap after adding a new element.
  heapifyUp() {
    // We start from the last node in the heap. This is the node that was most recently added.
    let nodeIndex = this.size() - 1;

    /*
    In the while loop, we swap the values to maintain the heap property.
    When? If the following 2 conditions are true:

    - "nodeIndex > 0": 
      This means we haven't reached to the main parent yet.

    - "this.comparator(parentNodeValue, currentNodeValue) > 0":
      If this is true, it means the heap property is violated and we need to swap values.
      "comparator" function here compares if the current node is smaller or bigger than it's parent. 
      Based on the heap order, comparator function will be slightly different. Such as:
        ((a, b) => (a - b) for min heap
        ((a, b) => (b - a) for max heap
    */

    while (
      // The node is not the root (it has a parent).
      nodeIndex > 0 &&
      this.comparator(this.parentValue(nodeIndex), this.heap[nodeIndex]) > 0
    ) {
      // The heap property is violated for our node and its parent. We need to swap them to restore the heap property.
      this.swap(nodeIndex, this.parentIndex(nodeIndex));

      // After swapping, our node has moved one level up the heap. We update nodeIndex to the index of the parent.
      // In the next iteration of the loop, we'll check the heap property for the node and its new parent.
      nodeIndex = this.parentIndex(nodeIndex);
    }
  }

  // Method to move a node down the heap until it is in the correct position.
  // Used after a deletion
  heapifyDown() {
    // We start from the top node in the heap which is the root, always at index 0.
    // So we initialize the current node index at 0.
    let currNodeIndex = 0;

    // The 'while' loop continues as long as the current node has a left child.
    // The reason for this is that a heap is a complete binary tree and hence,
    // a node would have a left child before it has a right child.
    while (this.hasLeftChild(currNodeIndex)) {
      // Assume the smaller child is the left one.
      let smallerChildIndex = this.leftChildIndex(currNodeIndex);

      /*
      Check if there's a right child and compare it to the left child.
      If the right child is smaller, update the smallerChildIndex to the right child's index
      Based on the heap order, comparator function will be slightly different. Such as:
        ((a, b) => (a - b) for min heap
        ((a, b) => (b - a) for max heap
      */
      if (
        this.hasRightChild(currNodeIndex) &&
        this.comparator(
          this.rightChildValue(currNodeIndex),
          this.leftChildValue(currNodeIndex)
        ) < 0
      ) {
        smallerChildIndex = this.rightChildIndex(currNodeIndex);
      }

      // If the current node is smaller or equal to its smaller child, then it's already in correct place.
      // This means the heap property is maintained, so we break the loop.
      if (
        this.comparator(
          this.heap[currNodeIndex],
          this.heap[smallerChildIndex]
        ) <= 0
      ) {
        break;
      }

      // If the current node is not in its correct place (i.e., it's larger than its smaller child),
      // then we swap the current node and its smaller child.
      this.swap(currNodeIndex, smallerChildIndex);

      // After swapping, the current node moves down to the position of its smaller child.
      // Update the current node index to the smaller child's index for the next iteration of the loop.
      currNodeIndex = smallerChildIndex;
    }
  }

  // Displays an array that will represent the heap as a binary tree
  // in level-order, with each sub-array representing a level of the tree.
  // such as: [ [ 1 ], [ 5, 3 ], [ 9, 6, 8 ] ]
  displayHeap() {
    let result = [];
    let levelCount = 1; // Counter for how many elements should be on the current level.
    let currentLevel = []; // Temporary storage for elements on the current level.

    for (let i = 0; i < this.size(); i++) {
      currentLevel.push(this.heap[i]);

      // If the current level is full (based on levelCount), add it to the result and reset currentLevel.
      if (currentLevel.length === levelCount) {
        result.push(currentLevel);
        currentLevel = [];
        levelCount *= 2; // The number of elements on each level doubles as we move down the tree.
      }
    }

    // If there are any elements remaining in currentLevel after exiting the loop, add them to the result.
    if (currentLevel.length > 0) {
      result.push(currentLevel);
    }

    return result;
  }
}

class MinHeap extends Heap {
  constructor() {
    super((a, b) => a - b); // MinHeap uses a comparator that sorts in ascending order
  }
}

class MaxHeap extends Heap {
  constructor() {
    super((a, b) => b - a); // MaxHeap uses a comparator that sorts in descending order
  }
}

DEV Community: Şahin Arslan

A Voyage through Algorithms using Javascript - Radix Sort

What is Radix Sort?

How Radix Sort Works

Implementing Radix Sort in JavaScript

Key Implementation Details for Radix Sort

1. The Exponential Loop Magic

2. The Digit Extraction Trick

3. Why Stability is Non-Negotiable

4. The Backwards Pass Trick

5. Handling Zero Values

Radix Sort's Stability Chain Pattern

Time and Space Complexity Analysis

Is Radix Sort Stable?

Advantages and Disadvantages of Radix Sort

When to Choose Radix Sort

Radix Sort vs Counting Sort: When to Use Which?

Real-World Applications

Handling Negative Numbers

Conclusion

A Voyage through Algorithms using Javascript - Counting Sort

What is Counting Sort?

How Counting Sort Works

Implementing Counting Sort in JavaScript

Key Implementation Details for Counting Sort

1. The Range Calculation Magic

2. The Compression Trick: value - minOffset

3. Sparse Arrays Are Your Friend

4. The Expansion Trick: i + minOffset

5. Handling Negative Numbers

Is Counting Sort Stable?

Time and Space Complexity Analysis

When to Choose Counting Sort

Real-World Applications

Counting Sort Implementation (Object based variant)

Conclusion

A Voyage through Algorithms using Javascript - Quick Sort

What is Quick Sort?

How Quick Sort Works

Implementing Quick Sort in JavaScript

Key Implementation Details for Quick Sort

Step 1: Creating a Boundary with In-Place Organization

Step 2: Swapping to Maintain the Boundary

Step 3: Pivot Is Placed, Time for Recursion

Step 4: When Does the Recursion Stop?

Is Quick Sort Stable?

Time and Space Complexity Analysis

Advantages and Disadvantages of Quick Sort

When to Use Quick Sort

When NOT to Use Quick Sort

Practical Applications and Use Cases

Conclusion

A Voyage through Algorithms using Javascript - Merge Sort

What is Merge Sort?

How Merge Sort Works

Implementing Merge Sort in JavaScript

Key Implementation details for Merge Sort

The Math.floor() Decision Point When Splitting Arrays

Common Edge Cases

Avoiding the O(n²) Performance Trap

Time and Space Complexity Analysis

Advantages and Disadvantages of Merge Sort

When to Use Merge Sort

Practical Applications and Use Cases

Conclusion

A Voyage through Algorithms using Javascript - Insertion Sort

What is Insertion Sort?

How Insertion Sort Works

Implementing Insertion Sort in JavaScript

Key Points:

Is Insertion Sort Stable?

Time and Space Complexity Analysis

Advantages and Disadvantages of Insertion Sort

When to Use Insertion Sort

Practical Applications and Use Cases

Conclusion

A Voyage through Algorithms using Javascript - Selection Sort

What is Selection Sort?

How Selection Sort Works

Implementing Selection Sort in JavaScript

2. The Compression Trick: `value - minOffset`

4. The Expansion Trick: `i + minOffset`