QuickSort: Adding Recursion

While we have successfully partitioned the array and placed the pivot element in its correct position, we still need to consider the other elements. Relative to the pivot element, they are on the correct side but not in their proper places within the array. This is where recursion comes into play. After performing the initial partition, we treat the subarrays to the left and right of the pivot as their own arrays and recursively repeat the partitioning process. This recursive approach allows us to sort the entire array.

---

Algorithm

Here are the step-by-step instructions for implementing the Quicksort algorithm:

1. Partition the array based on a chosen pivot element. Select a pivot element from the array and rearrange the elements so that all elements smaller than the pivot are placed to its left, and all elements greater than the pivot are placed to its right.

2. Treat the subarrays to the left and right of the pivot as their own arrays and recursively repeat the first step. Partition each smaller subarray by selecting a new pivot and applying the partitioning process again.

3. Continue recursively partitioning the subarrays until you reach subarrays that have zero or one element. These smaller subarrays serve as the base case, as an empty array or an array with one element is already sorted.

Walkthrough

Let's continue with our example from the array [5, 3, 1, 7, 8, 9] where the original pivot 7 is in its correct place.

---

Subarray [5, 3, 1]

We will first focus on the left partition of this array, the subarray [5,3,1]. The part of the array that we are not working on will be grayed out in the images.

Step 1

• Choose the pivot element - in this case, it is the number 5.

Step 2

• Assign the left and right pointers to the leftmost and rightmost indices of the remaining array. In this case, left will be set to the index 1, pointing to the value 3, and right will be set to the index 2, pointing to the value 1.

Step 3

• Increment the left pointer until it reaches a value greater than or equal to the pivot or becomes greater than the right pointer. In this case, the left pointer moves until it becomes greater than the right pointer because none of the elements are greater than or equal to the pivot.

Step 4

• Decrement the right pointer until it reaches a value less than or equal to the pivot or becomes smaller than the left pointer. In this case, the right pointer already points to a value less than the pivot element.

Step 5

• Since the left pointer is greater than the right pointer, we swap the pivot element with the element at the right pointer, resulting in the array [1, 3, 5].

At the end of step 5, Our subarray [5, 3, 1] has been partitioned. This partition resulted in only one new subarray, [1, 3], because our pivot happened to be the largest element. If our pivot were a middle element, like 3, we would have two new subarrays to partition recursively.

Subarray [1, 3]

In the next step, we need to partition the subarray [1, 3].

Step 1

• Choose the pivot element: in this case, it is the number 1.

Step 2

• Assign the left and right pointers to the leftmost and rightmost indices of the remaining array. In this case, they are both set at index 1, which points to element 3.

Step 3

• Since the left pointer is already at the element that is greater than the pivot, we don't move it.

Step 4

• The right pointer is at the element greater than the pivot, so we decrement it by 1. Since it is now smaller than left pointer we stop.

Step 5

• Since the right pointer is smaller than the left pointer, we swap the values at the pivot element and the right pointer, but since it is the same element, it just remains where it is. Now the array is [1, 3].

After this swap, we're left with only one new subarray that hasn't been partitioned, [3].

Subarray [3]

The right partition contains only one element, [3], which is our base case.

Subarray [8, 9]

Now we have the array [1, 3, 5, 7, 8, 9]. We started with 7 as the pivot and recursively partitioned the subarray to its left, [1, 3, 5]. On the right side, we have a two-element array, [8, 9]. Let's continue with that subarray:

Step 1

• Choose the pivot element: number 8.

Step 2

• Assign the left and right pointers to the leftmost and rightmost indices of the remaining array. In this case, they are both set at index 1, which points to element 9.

Step 3

• Since the left pointer is already at the element that is greater than the pivot, we don't move it.

Step 4

• The right pointer is at an element greater than the pivot, so we decrement it by one. Since it is now smaller than left pointer, we stop.

Step 5

• Since the right pointer is smaller than the left pointer, we swap the values at the pivot element and the right pointer, but since it is the same element, it just remains where it is. Now the array is [8, 9].

Subarray [9]

Finally, the right partition contains only one element, [9], which is our base case.

---

Implementation

Here's the final code implementation for the QuickSort algorithm in JavaScript:

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

  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
  // thus putting it at its correct spot
  [arr[low], arr[right]] = [arr[right], arr[low]];
  // Return the pivot index
  return right;
}

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
}

const arr = [7, 3, 9, 8, 5, 1];
quickSort(arr);
console.log(arr); // Output: [1, 3, 5, 7, 8, 9]

In this code, the partition function implements the partitioning logic, while the quickSort function recursively calls itself to sort the subarrays.

The partition function selects a pivot element, moves the left and right pointers, and swaps elements until they meet. Finally, the pivot element is placed at its correct position, and the function returns the pivot index. You may have noticed that we modified the implementation slightly from the initial one mentioned above. Since the left and right pointers can vary depending on the subarrays we are working on, we introduced additional arguments, low and high, to specify the range. This allows us to set the pivot, left, and right based on these values. Ultimately, the partition function returns the index of the pivot rather than the modified array.

The quickSort function takes an array, arr, and optional low and high indices. By default, if the low and high indices are not provided, it assumes the entire array needs to be sorted. The function partitions the array using the partition function and recursively calls itself on the left and right subarrays until the base case is reached. The base case occurs when the subarrays have zero or one element, which are already sorted.

In this assignment, we've used the first element in the array as the pivot. However, remember that we mentioned that this might not be the most efficient choice. We will discuss this in the next assignment.