QuickSort: Partitioning

In the Introduction to Data Structures and Algorithms book, we discussed various methods for sorting arrays, such as Bubble Sort, Selection Sort, and Insertion Sort. We mentioned that there are more efficient algorithms to explore. It's now time to delve into one such algorithm: QuickSort.

QuickSort is a popular sorting algorithm used by many programming languages due to its exceptional speed and efficiency, particularly in average scenarios. Though it performs similarly to Insertion Sort and Selection Sort in worst-case scenarios (such as when dealing with inversely sorted arrays), it significantly outperforms them in average scenarios, which are more commonly encountered in practice.

The fundamental part of the QuickSort algorithm is partitioning. To partition the array, we first select a pivot point, which is a somewhat random element in the array. Afterwards, we arrange the elements such that elements smaller than the pivot are positioned before it, while elements larger than the pivot are placed after it. Elements equal to the pivot can be placed on either the left or right side, as long as we are consistent throughout the partitioning process.

For now, we'll use the first element in the array as the pivot point. This differs from how we usually partition an array, but this works well as a starting point for understanding how the partitioning step works. We'll explain how to use a different pivot point soon, as well as why we would want to. The visual explanation below illustrates this partitioning step:

---

Algorithm

We saw above that our partitioning process aims to move all elements smaller than our pivot to its left and all elements larger than our pivot to its right. To do so, we will use two pointers, left and right, that will move towards each other until they meet and cross. left will start from the left, checking that everything from here to the meeting point is less than our pivot. right will similarly start from the right, checking that everything from here to the meeting point is greater than our pivot. When we find elements that aren't in the correct place, we will swap them and continue. When left and right meet in the middle, we'll know where our pivot element should go.

Now, let's explain step-by-step how partitioning is performed. As before, we will take the first element in the array as the pivot element. It's important to note that the choice of the pivot can affect the algorithm's performance, but we'll discuss that later. Also, we will assume that elements equal to the pivot will go to the right side. Remember that we can choose any side as long as we are consistent.

Here's the step-by-step breakdown of the partitioning process:

1. Set the pivot element as the first element of the array.
2. Assign left and right pointers to the leftmost and rightmost indices of the remaining elements in the array, respectively.
3. Increment the left pointer continuously, one cell at a time, until it reaches a value that is greater than or equal to the pivot or until it becomes greater than right.
4. Decrement the right pointer continuously, one cell at a time, until it reaches a value that is less than the pivot, or until it becomes smaller than left. Notice that we're looking for values that are less than but not equal to our pivot. This stems from our decision to place values equal to the pivot to its right.
5. Once you're done incrementing and decrementing the pointers, evaluate whether the left pointer has gone beyond the right pointer.
   • If this is the case, move on to step 6.
   • If this is not the case, swap the values that the left and right pointers reference. Then, go back to step 3.
6. Swap the value at the pivot index with the value the right pointer is pointing to. This places the pivot at its correct position in the array.

---

Walkthrough

Let's apply this knowledge and walk through an example: [7, 3, 9, 8, 5, 1].

Step 1

• Set the pivot element - number 7 in this case.

Step 2

• Assign left and right pointers to the leftmost and rightmost indices of the remaining elements in the array. In this example, left will be set to index 1, pointing to the value 3, and the right pointer will be set to index 5, pointing to the value 1.

Step 3

• Move the left pointer continuously until it reaches a value greater than or equal to the pivot. In our case, we will move the left pointer by one cell to index 2, where element 9 is located.

Step 4

• Move the right pointer continuously until it reaches a value less than the pivot. In our case, the right pointer is already pointing to a value less than the pivot element.

Step 5

• Since the left pointer is less than the right pointer, swap the values they point to.

Step 6

• In this step, once again, we move the left pointer. We'll increment left once to reach the cell with value 8.

Step 7

• Now, we move the right pointer until it reaches a value less than or equal to the pivot. We decrement right once to reach 5, which is less than our pivot.

Step 8

• Since the left pointer is less than the right pointer, we swap the values they point to.

Step 9

After making a swap, we go back to step three in our algorithm. We only need to increment left once and we reach 8, which is greater than our pivot.

Step 10

Now, we need to decrement right until we reach an element that is less than our pivot, or until right is less than left. Neither of these conditions are true yet, so we decrement right and we end up at 5, which is less than our pivot. right has also become less than left.

Step 11

• Since the right pointer is now less than the left pointer, the only thing left to do is swap the pivot value with the value that the right pointer is pointing to. This results in the array [5, 3, 1, 7, 8, 9].

Though this array is not sorted, we have completed one partition. The pivot element, number 7, is in its correct place, as all the numbers to its left are smaller than it, and all the numbers to the right are greater than it.

---

Implementation

Let's look at the code implementation for the partitioning process we've just seen:

function partition(arr) {
  const pivot = arr[0];
  let left = 1;
  let right = arr.length - 1;

  while (left <= right) {
    while (left <= right && arr[left] < pivot) {
      left++;
    }

    while (left <= right && arr[right] >= pivot) {
      right--;
    }

    if (left < right) {
      // Swap values at left and right pointers
      [arr[left], arr[right]] = [arr[right], arr[left]];
    }
  }

  // Swap pivot with the element at the right pointer
  [arr[0], arr[right]] = [arr[right], arr[0]];

  // Return modified array
  return arr;
}

Now that we understand how partitioning works, we will add the recursion part in the next assignment.