Learning the 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:

// 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]

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.

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;
};

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) {
  // 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);
}

• 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:

// 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]

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.

The above is the detailed content of Learning the Quick Sort Algorithm. For more information, please follow other related articles on the PHP Chinese website!