Quick Sort

Quick Sort, as the name suggests, is a sorting algorithm known for its efficiency. It is one of the best-performing sorting algorithms, with a significant caveat: it should only be used when the worst-case scenario is unlikely to occur. Understanding its mechanics and performance profile is crucial for effective implementation.

Theory

Quick Sort follows the divide and conquer pattern, similar to Merge Sort. The algorithm works by selecting a 'pivot' value from the array and partitioning the input array into sub-arrays based on if the values are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Pivot Selection

The choice of pivot is critical. Ideally, the pivot should be the median of the array, but since the array is unsorted, this is not feasible. Common strategies include selecting the middle value we'll see later on why.

Partitioning Process

1. Initialization: Start with the pivot at the first position.
2. Comparison: Compare each subsequent value with the pivot.
3. Swapping: If a value is smaller than the pivot, swap it at the current pivot position and increment the pivot index.
4. Recursion: Repeat the process for the sub-arrays to the left and right of the pivot until the entire array is sorted.

Implementation

For clarity's sake let's start with the swap function:

const swap = (arr, idx1, idx2) => {
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};

Then our pivot helper:

function pivot(arr, start = 0, end = arr.length - 1) {
  let pivot = arr[start];
  let swapIdx = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }

  swap(arr, start, swapIdx);
  return swapIdx;
}

Explanation:

Now that we have our pivot helper we need a way to execute it recursively until everything is sorted because after one iteration only what is less than our pivot will end up to the left of it and what is greater to the right of it, in other words only our pivot is at the correct spot. To illustrate this with an example, consider an array 2, 4, 1:

• First Iteration: Nothing is swapped because 2 < 4, but i is incremented 2, 4, 1.
• Second Iteration: We swap 1 and 4 because 4 > 1 2, 1, 4.
• Last Swap: Pivot is placed where it should 1, 2, 4

Here with a small dataset one pivot execution is enough but if we were to have a larger one we would need to recursively do it until our array is fully sorted.

Let's find out how:

function quickSort(arr, start_index = 0, end_index = arr.length - 1) {
  if (start_index >= end_index) return arr;
  let pivot_index = pivot(arr, start_index, end_index);
  // Left
  quickSort(arr, start_index, pivot_index - 1);
  // Right
  quickSort(arr, pivot_index + 1, end_index);

  return arr;
}

const arr = [2, 4, 1, 3, 5, 1]
pivot(arr); // Just 1 pivot => [1, 1, 2, 3, 5, 4]
quickSort(arr); // Here 2 pivots => [1, 1, 2, 3, 4, 5]

Explanation:

• Base Case: We prevent the loop from running out of the array, the array is returned as is.
• Pivoting: The pivot function is called to place the pivot element at its initial position allowing us to divide from there.
• Recursion: The function recursively sorts the sub-arrays to the left and right of the pivot.

function pivot(arr, start = 0, end = arr.length - 1) {
  const pivot = arr[Math.floor((end + start) / 2)];
  let i = start;
  let j = end;
  while (i <= j) {
    while (arr[i] < pivot) {
      i++;
    }
    while (arr[j] > pivot) {
      j--;
    }
    if (i <= j) {
      swap(arr, i, j);
      i++;
      j--;
    }
  }
  return i;
}

Performance considerations

Quick Sort is highly efficient but has a significant caveat in its worst-case scenario:

• Worst-case scenario: O(n²) This occurs when the pivot is consistently the smallest or largest element, leading to a large number of iterations.
• Best-case scenario: O(n log n) This occurs when the pivot is consistently dividing the array into two sub arrays with equal length.
• Average-case scenario: O(n log n) On average, Quick Sort performs efficiently with a time complexity of O(n log n).

Practical Use Cases

Quick Sort is suitable for most sorting tasks, especially when the worst-case scenario is unlikely. However, other algorithms like Merge Sort may be more consistent and stable in certain scenarios.

Conclusion

Quick Sort is a powerful and efficient sorting algorithm with an average time complexity of O(n log n). However, it is essential to be aware of its worst-case scenario, which can degrade performance to O(n^2). By carefully selecting the pivot and understanding the algorithm's mechanics, you can leverage Quick Sort effectively in your projects.

Happy coding!