How To Do Comb Sort in JavaScript

Sorting algorithms are a fundamental aspect of computer science, and Comb Sort offers an improvement over traditional algorithms like Bubble Sort. We will explore how Comb Sort works, its JavaScript implementation, and why it’s faster than Bubble Sort.

What is Comb Sort?

Comb Sort is an enhancement of Bubble Sort that reduces the number of comparisons required during the sorting process. Instead of comparing adjacent elements, Comb Sort compares farther apart elements, progressively shrinking the gap between compared elements on each iteration. This allows the algorithm to eliminate “turtles” (small values near the end of the list) more quickly than Bubble Sort. To see how Comb Sort and Bubble Sort work visually, go to our Sorting Algorithm Visualizer.

Pseudocode for Comb Sort

procedure combSort(arr)
    n = length(arr)
    gap = n
    shrinkFactor = 1.3
    swapped = true
    
    while gap > 1 or swapped == true
        gap = max(1, gap / shrinkFactor)  // Update the gap
        swapped = false
        
        for i = 0 to n - gap - 1
            if arr[i] > arr[i + gap]
                swap(arr[i], arr[i + gap])
                swapped = true

Step-by-Step Explanation:

• Initially, the gap between elements is set to the array’s length.
• In each iteration, the gap is reduced by a shrink factor (typically 1.3).
• Elements that are gap distance apart are compared, and swaps are made if they are in the wrong order.
• The process continues until the gap becomes one and no swaps are needed (essentially returning to Bubble Sort).

Time Complexity of Comb Sort

• Best Case: O(n log n) – In the best-case scenario, where the data is already nearly sorted, Comb Sort performs fewer comparisons as the gap decreases.
• Average Case: O(n²) – On average, it behaves similarly to Bubble Sort when the shrink factor is not optimized.
• Worst Case: O(n²) – Similar to Bubble Sort, Comb Sort can degrade to O(n²) when elements are placed in reverse order.

Space Complexity of Comb Sort

• Space Complexity: O(1) – Like Bubble Sort, Comb Sort is an in-place sorting algorithm, meaning it does not require additional memory.

JavaScript Implementation of Comb Sort

function combSort(arr) {
    let n = arr.length;
    let gap = n;
    const shrinkFactor = 1.3;
    let swapped = true;

    while (gap > 1 || swapped) {
        // Update gap for the next iteration
        gap = Math.floor(gap / shrinkFactor);
        if (gap < 1) gap = 1;

        swapped = false;

        // Perform a Bubble Sort-like pass with the current gap
        for (let i = 0; i + gap < n; i++) {
            if (arr[i] > arr[i + gap]) {
                [arr[i], arr[i + gap]] = [arr[i + gap], arr[i]]; // Swap
                swapped = true;
            }
        }
    }
    return arr;
}

// Example usage:
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("Initial array:",arr);
console.log("Sorted array:", combSort(arr));

Output:

Initial array: [
  64, 34, 25, 12,
  22, 11, 90
]
Sorted array: [
  11, 12, 22, 25,
  34, 64, 90
]

Explanation:

• The initial gap is set to the length of the array, and it shrinks by dividing by 1.3 in each iteration.
• The algorithm continues until the gap is one and no swaps are needed (i.e., the array is sorted).
• Comb Sort quickly moves elements to their final positions by starting with a large gap.

Pros and Cons of Using Comb Sort

Pros:

1. Faster Than Bubble Sort: Comb Sort improves upon Bubble Sort by quickly eliminating small elements (turtles).
2. Simple to Implement: The algorithm is straightforward and can be coded efficiently.
3. In-Place Sorting: It requires constant extra memory (O(1)).

Cons:

1. Still Inefficient for Large Arrays: Like Bubble Sort, Comb Sort can still have O(n²) time complexity, making it inefficient for extensive datasets.
2. Not Widely Used: More efficient algorithms like QuickSort or MergeSort are preferred in most real-world applications.

When to Use Comb Sort

Comb Sort can be a good choice when working with small datasets where ease of implementation is more important than optimal performance. It is faster than Bubble Sort, especially on arrays initially in reverse order. However, other algorithms like QuickSort or MergeSort are better choices for larger arrays or cases where efficiency is critical.

Conclusion

Comb Sort is a simple improvement over Bubble Sort that introduces a shrinking gap to optimize sorting. While it offers better performance for small datasets or nearly sorted arrays, it is still inefficient compared to advanced algorithms like QuickSort and MergeSort. Understanding Comb Sort is a great step in learning how small changes can enhance sorting algorithms, and it serves as a bridge between elementary and more complex sorting techniques.

Congratulations on reading to the end of this tutorial!

Read the following articles to learn how to implement Comb Sort:

In Python – How to do Comb Sort in Python

In C++ – How to Do Comb Sort in C++

Have fun and happy researching!