Quick Sort Algorithm

Quick Sort is one of the most efficient algorithms, and it uses the divide-and-conquer technique to sort arrays.

How Quick Sort Works

The main idea of Quick Sort is to help one element at a time move to its correct position in an unsorted array. This element is called the pivot.

The pivot element is in the correct position when:

1. All the elements to its left are smaller.
2. All the elements to its right are larger.

It doesn’t matter whether the numbers to the left or right are sorted yet. What matters is that the pivot is in the correct position in the array.

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

All these are valid output of an array where the pivot is 23.

Finding the Pivot's Correct Position

Quick Sort helps the pivot find its correct position in the array. For example, if the pivot is positioned at the beginning of the array but isn’t the smallest number, Quick Sort determines that it needs to move 5 steps to make room for the 5 smaller elements in the array -- assuming there are 5 such numbers.

Let's say we have the array: [10, 4, 15, 6, 23, 40, 1, 17, 7, 8] and 10 is the pivot:

At this point:

• The number 10 doesn’t know if it's in the correct position or how many steps it needs to move to get there. Quick Sort starts by comparing 10 with the value at the next index.
• Upon seeing that 4 is smaller, Quick Sort records that the pivot needs to move one step forward to allow 4 to come before it.
• So numberOfStepsToMove increases by 1.

Next, at index 2, the value is 15, which is greater than 10. Since no adjustment is needed, Quick Sort keeps the step count unchanged and moves on to the next element in the array.

At the next index, the value is 6, which is smaller than 10. Quick Sort increases the step count to 2, as the pivot now needs to make space for two smaller numbers: 4 and 6.

Now, 6 will need to swap with 15 to keep the smaller numbers next to each other at the left side of the array. We swap the numbers based on the current index and numberOfStepsToMove values.

Quick Sort continues looping through the array, increasing the numberOfStepsToMove based on how many numbers are smaller than the pivot. This helps determine how far the pivot needs to move to its correct position.

The numberOfStepsToMove doesn't change for 23 or 40 because both values are greater than the pivot and shouldn't come before it in the array:

Now, when Quick Sort loops to the value 1 at index 6, numberOfStepsToMove increases to 3 and swaps it the number at the index 3:

Quick Sort continues this process until it reaches the end of the array:

Now that we've reached the end of the array, we know that there are 5 numbers smaller than 10. Therefore, the pivot (10) must move 5 steps ahead to its correct position, where it is greater than all the numbers before it.

Let's see how that looks in the code:

const getNumberOfStepsToMove = (arr, start = 0, end = arr.length - 1) => {
  let numberOfStepsToMove = start;
  // we're picking the first element in the array as the pivot
  const pivot = arr[start];

  // start checking the next elements to the pivot
  for (let i = start + 1; i <= end; i++) {
    // is the current number less than the pivot?
    if (arr[i] < pivot) {
      // yes - so w should increase numberOfStepsToMove
// or the new index of the pivot
      numberOfStepsToMove++;

      // now swap the number at the index of numberOfStepsToMove with the smaller one
      [arr[i], arr[numberOfStepsToMove]] = [arr[numberOfStepsToMove], arr[i]];
    } else {
      // what if it's greater?
      // do nothing -- we need to move on to the next number
      // to check if we have more numbers less that pivot to increase numberOfStepsToMove or not
    }
  }

  // now we know the pivot is at arr[start] and we know that it needs to move numberOfStepsToMove
  // so we swap the numbers to place the pivot number to its correct position
  [arr[start], arr[numberOfStepsToMove]] = [
    arr[numberOfStepsToMove],
    arr[start],
  ];

  return numberOfStepsToMove;
};

Now that we have a function to help us find the where to place the pivot, let's see how Qucik Sort divides the array into smaller arrays and utilize the getNumberOfStepsToMove function to place all the array elements.

function quickSort(arr, left = 0, right = arr.length - 1) {
  // pivotIndex the new index of the pivot in in the array
  // in our array example, at the first call this will be 5, because we are checking 10 as the pivot
  // on the whole array
  let pivotIndex = getNumberOfStepsToMove(arr, left, right);
}

Quick Sort leverages recursion to efficiently divide the array into smaller subarrays, ensuring that elements are sorted by comparing them with a pivot.

function quickSort(arr, left = 0, right = arr.length - 1) {
  let pivotIndex = getNumberOfStepsToMove(arr, left, right);

  // the function starts calling itself from the beginning of the array where left = 0;
  // and right is the index before pivotIndex (4 when pivotIndex is 5)
  quickSort(arr, left, pivotIndex - 1);

 //Reaching this point means that the left side of the array is fully
// sorted, with each element positioned in its correct place

  return arr;
}

• The algorithm recursively sorts the left subarray that contains elements smaller than the pivot.
• The recursion stops when the subarray has one or zero elements, as it’s already sorted.

Now we need to do the same process to the right side of the array:

function quickSort(arr, left = 0, right = arr.length - 1) {
  // if the right index is greater, the sorting is done and we should return the array
  if (left < right) {
    let pivotIndex = getNumberOfStepsToMove(arr, left, right);

    // the function starts calling itself from the beginning of the array where left = 0;
    // and right is the index before pivotIndex (4 when pivotIndex is 4)
    quickSort(arr, left, pivotIndex - 1);

    // we then call the function from the index after the pivotIndex until the end of the array to handle the right subarray
    quickSort(arr, pivotIndex + 1, right);
  }

  // now all is sorted and placed correctly to the array
  return arr;
}

In this example, the right side is already sorted but the algorithm doesn't know that and it would have been sorted if it hadn't been.