Quick Sort made easy in javascript

Quick Sort is a divide-and-conquer algorithm that selects a pivot element from the array and partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. The pivot selection and partitioning steps can be performed in-place, making Quick Sort an efficient sorting algorithm with a space complexity of O(log n). Here’s an implementation in JavaScript:

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

function pivot(arr, start = 0, end = arr.length - 1) {
  let pivot = arr[start];
  let swapIndex = start;
  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      swapIndex++;
      [arr[swapIndex], arr[i]] = [arr[i], arr[swapIndex]];
    }
  }
  [arr[start], arr[swapIndex]] = [arr[swapIndex], arr[start]];
  return swapIndex;
}

Explanation

function quickSort(arr, left = 0, right = arr.length - 1) {

This is the main function that implements the quick sort algorithm. It takes an array arr as an input, and optional parameters left and right that indicate the starting and ending indices of the portion of the array to be sorted. If left and right are not provided, the entire array is sorted.

  if (left < right) {

This line checks if there are still elements in the portion of the array that need to be sorted. If left >= right, that means there's only one element or no elements left, which means the portion of the array is already sorted.

    let pivotIndex = pivot(arr, left, right);

This line calls the pivot function, passing the array arr and the indices left and right as arguments. The pivot function returns the index of the pivot element, which is used to partition the array into two sub-arrays.

    quickSort(arr, left, pivotIndex - 1);

This line sorts the sub-array on the left side of the pivot element. The portion of the array to be sorted is indicated by the indices left and pivotIndex - 1.

    quickSort(arr, pivotIndex + 1, right);

This line sorts the sub-array on the right side of the pivot element. The portion of the array to be sorted is indicated by the indices pivotIndex + 1 and right.

  }
  return arr;
}

Finally, this line returns the sorted array.

Now, let’s look at the pivot function:

function pivot(arr, start = 0, end = arr.length - 1) {

This is the pivot function that is used to find the pivot element in the portion of the array indicated by start and end.

  let pivot = arr[start];

This line selects the first element in the portion of the array as the pivot element.

  let swapIndex = start;

This line creates a variable swapIndex and initializes it with the value of start. swapIndex is used to keep track of the position of the pivot element as it is being moved to its final position.

  for (let i = start + 1; i <= end; i++) {

This line starts a for loop that iterates over the elements in the portion of the array, starting from the second element. The loop continues until i is greater than end.

    if (pivot > arr[i]) {

This line checks if the current element arr[i] is smaller than the pivot element pivot. If it is, the swapIndex is incremented and the current element arr[i] and the element at the swapIndex are swapped.

      swapIndex++;
      [arr[swapIndex], arr[i]] = [arr[i], arr[swapIndex]];
    }
  }

This line increments

Analogy: Quick Sort can be compared to how you would sort a deck of cards by picking a random card and putting all cards that are less than it to the left and all cards that are greater than it to the right, then repeating the process for each sub-deck until you have a sorted deck.

Limitations:

1. Performance of Quick Sort is sensitive to the choice of pivot element. If the pivot is chosen poorly, for example, if the pivot is the largest or smallest element in the array, the algorithm could result in a worst-case time complexity of O(n²).
2. Quick Sort is not stable, meaning that the relative order of equal elements may change after sorting.
3. Quick Sort can be vulnerable to stack overflow if the depth of the recursion is too large.