How To Do Quick Sort In JavaScript

Quick Sort is one of the most popular and efficient sorting algorithms. It uses the divide and conquer strategy, similar to Merge Sort, but it often outperforms Merge Sort in practice due to its in-place sorting nature. In this blog post, we will explore how to implement Quick Sort in JavaScript, discuss its time and space complexities, and walk through the algorithm step-by-step.

What is Quick Sort?

Quick Sort selects a “pivot” element from the array and partitions the other elements into two sub-arrays: one with elements smaller than the pivot and one with elements greater than the pivot. The pivot is then placed in its correct position in the sorted array, and the process is recursively applied to the sub-arrays.

Pseudocode for Quick Sort

Here’s the basic pseudocode for Quick Sort:

procedure quickSort(arr, low, high)
    if low < high then
        pivotIndex = partition(arr, low, high)   // Step 1: Partition the array
        quickSort(arr, low, pivotIndex - 1)      // Step 2: Recursively sort the left sub-array
        quickSort(arr, pivotIndex + 1, high)     // Step 3: Recursively sort the right sub-array

procedure partition(arr, low, high)
    pivot = arr[high]        // Step 4: Choose the pivot (last element in the array)
    i = low - 1              // Step 5: Initialize i to point to the element before the sub-array

    for j = low to high - 1  // Step 6: Iterate over the array from low to high - 1
        if arr[j] <= pivot then
            i = i + 1          // Step 7: Increment i
            swap arr[i] with arr[j]  // Step 8: Swap arr[i] and arr[j] (elements less than the pivot)

    swap arr[i + 1] with arr[high]  // Step 9: Place the pivot in its correct position
    return i + 1                   // Step 10: Return the pivot index

---

Step-by-Step Breakdown of the Pseudocode

Quick Sort Function (Main Recursive Function)

1. Base Condition:
   • The function checks if low is less than high. If not, it means the array or sub-array has only one or zero elements, which is already sorted, so we stop.
   • This condition ensures the recursive function terminates when the sub-array size becomes 1 or 0.
2. Partition the Array:
   • The partition() function is called to rearrange the elements in the array so that all elements smaller than the pivot are on the left and all elements larger are on the right. The pivot is placed in its correct position in the sorted array.
   • After the partitioning step, the array is divided into two sections: the left and right of the pivot.
3. Recursively Sort the Left and Right Sub-arrays:
   • The quickSort() function is called recursively on the left sub-array (low to pivotIndex - 1), which contains elements smaller than the pivot.
   • It is also called on the right sub-array (pivotIndex + 1 to high), which contains elements larger than the pivot.
   • This process continues until all sub-arrays are fully sorted.

Partition Function (Rearranges the Array Around the Pivot)

4. Select the Pivot:
   • The pivot is usually selected as the last element (arr[high]). The goal is to place this pivot in its correct sorted position.
5. Initialize the Index for Smaller Elements (i):
   • Set i to low - 1, which points to the position before the first element of the sub-array. This is important because i will track the “boundary” between elements smaller than the pivot and those larger than the pivot.
6. Iterate Over the Array (j Loop):
   • A loop runs from low to high - 1 (excluding the pivot itself).
   • We compare each element in this loop to the pivot.
7. Check If the Current Element is Smaller or Equal to the Pivot:
   • If the element at arr[j] is smaller than or equal to the pivot, it means it should be on the left side of the pivot.
   • We increment i to include the current element in the “smaller elements” section.
8. Swap Elements to Place Smaller Elements on the Left:
   • Swap arr[i] with arr[j]. This ensures that all elements less than or equal to the pivot end up on the left side of the pivot.
9. Place the Pivot in the Correct Position:
   • After the loop ends, swap arr[i + 1] with the pivot (arr[high]). This places the pivot in its correct position in the sorted array, as all elements to its left are smaller, and all elements to its right are larger.
10. Return the Pivot Index:

• Finally, return i + 1 as the new pivot index. This index will further divide the array into sub-arrays for recursive sorting.

Time Complexity of Quick Sort

• Best Case: O(n log n) – This occurs when the pivot divides the array into two nearly equal halves, leading to logarithmic recursive depth.
• Average Case: O(n log n) – Quick Sort performs O(n log n) operations on average, making it highly efficient for most datasets.
• Worst Case: O(n²) – The worst-case scenario occurs when the pivot repeatedly selects the smallest or largest element, leading to unbalanced partitions. This can happen if the array is already sorted.

Space Complexity of Quick Sort

• Space Complexity: O(log n) – Quick Sort uses recursive calls, which take up stack space. The recursion depth is proportional to the logarithm of the array size in the best and average cases.

JavaScript Implementation of Quick Sort

Here’s how you can implement Quick Sort in JavaScript:

// Partition function to place the pivot in the correct position
function partition(arr, low, high) {
    const pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];  // Swap arr[i] and arr[j]
        }
    }

    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];  // Place pivot in correct position
    return i + 1;
}

// Recursive Quick Sort function
function quickSort(arr, low = 0, high = arr.length - 1) {
    if (low < high) {
        const pivotIndex = partition(arr, low, high);

        // Recursively sort elements before and after the partition
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
    return arr;
}

// Example usage
const arr = [10, 80, 30, 90, 40, 50, 70];
console.log("Initial array:", arr);
console.log("Sorted array:", quickSort(arr));

Output:

Initial array: [
  10, 80, 30, 90,
  40, 50, 70
]
Sorted array: [
  10, 30, 40, 50,
  70, 80, 90
]

Step-by-Step Walkthrough of Quick Sort

Let’s walk through Quick Sort using the array [10, 80, 30, 90, 40, 50, 70].

Step 1: First Partitioning

• Select 70 as the pivot.
• Rearrange the array so that elements smaller than 70 are on the left and elements larger are on the right:
  • Compare 10 with 70 (no swap, move to next).
  • Compare 80 with 70 (no swap).
  • Compare 30 with 70 (swap 80 and 30).
  • Compare 90 with 70 (no swap).
  • Compare 40 with 70 (swap 80 and 40).
  • Compare 50 with 70 (swap 80 and 50).
• Place 70 in its correct position, swapping it with 80.
• Array after the first partition: [10, 30, 40, 50, 70, 90, 80]

---

Step 2: Sort Left Sub-array

• Recursively apply Quick Sort to the left sub-array [10, 30, 40, 50] using the same logic.
• The left sub-array is already sorted after one recursive call:
  • Array after sorting left sub-array: [10, 30, 40, 50]

---

Step 3: Sort Right Sub-array

• Now apply Quick Sort to the right sub-array [90, 80].
• Select 80 as the pivot and swap it with 90:
  • Array after sorting right sub-array: [80, 90]

---

Step 4: Final Array

• After recursively sorting the left and right sub-arrays, the final sorted array is:
  • Sorted Array: [10, 30, 40, 50, 70, 80, 90]

To see how Quick Sort works in practice, go to the Sorting Algorithm Visualizer!

Pros and Cons of Using Quick Sort

Pros:

1. Efficient for Large Datasets: Quick Sort has an average-case time complexity of O(n log n), making it one of the fastest sorting algorithms.
2. In-Place Sorting: Unlike Merge Sort, Quick Sort sorts the array in place, so it doesn’t require additional memory.
3. Widely Used: Quick Sort is the go-to algorithm for many practical implementations due to its speed and efficiency.

Cons:

1. Worst-Case Performance: In the worst case, Quick Sort’s time complexity degrades to O(n²) when the pivot selection is poor (e.g., choosing the smallest or largest element).
2. Not Stable: Quick Sort is not a stable sorting algorithm, meaning it does not preserve the relative order of equal elements.

When to Use Quick Sort

Quick Sort is ideal when:

1. You need a fast, in-place sorting algorithm: With O(n log n) average-case time complexity and in-place sorting, Quick Sort is great for large datasets where memory usage matters.
2. Random or unsorted data: Quick Sort works well with data that has no clear ordering, as its performance is generally consistent.
3. You need general-purpose sorting: Quick Sort is widely used in practical applications because of its speed and versatility.

However, for datasets that are already sorted or nearly sorted, Merge Sort or Insertion Sort might be a better choice due to Quick Sort’s poor performance in its worst case.

Conclusion

Quick Sort is a fast and efficient sorting algorithm, but optimizing it for various scenarios can further improve its performance. Here are some key optimizations:

• Median-of-three pivot selection: Using the median of the first, middle, and last elements as the pivot helps ensure more balanced partitions and avoids worst-case scenarios.
• Insertion Sort for small sub-arrays: Switching to Insertion Sort for small sub-arrays reduces overhead and speeds up sorting.
• Tail call optimization: Limits recursion depth and prevents stack overflow by sorting larger sub-arrays iteratively.
• Three-way partitioning: Handles arrays with many duplicates more efficiently by reducing unnecessary swaps and comparisons.
• Hybrid algorithms (IntroSort): Switching to algorithms like Heap Sort if the recursion depth gets too deep ensures performance doesn’t degrade to O(n²).

These optimizations make Quick Sort faster and more reliable, especially for large datasets or special cases where the default version may struggle.

Congratulations on reading to the end of the tutorial!

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

In Python – How to do Quick Sort in Python

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

Have fun and happy researching!