QuickSort: Choosing Pivot Element

A very important factor that significantly impacts QuickSort's performance is the selection of the pivot element. In this assignment, we'll delve into the differences between choosing the first element and the middle element as the pivot in QuickSort. We'll explore why using the first element as the pivot can lead to poor performance and how selecting the middle element improves efficiency.

When the first element of the array is chosen as the pivot, several issues can arise. One major drawback is the potential for poor worst-case performance. If the input array is already sorted or nearly sorted, using the first element as the pivot can lead to inefficient partitioning and a time complexity of O(N^2). This poor performance is undesirable and defeats QuickSort's main goal of efficient sorting.

Consider a sorted array [1, 2, 3, 4, 5, 6]. If we choose the first element as the pivot:

• Pivot: 1
• Partitions:[ ] and [2, 3, 4, 5, 6]

Each recursive call processes one element less than the previous call:

• [2, 3, 4, 5, 6] with pivot 2
• [3, 4, 5, 6] with pivot 3
• and so on...

This results in highly unbalanced partitions, and the depth of recursion equals the length of the array. Therefore, the total number of recursive calls is N, leading to O(N^2) time complexity.

To avoid these issues, we can choose the middle element of the array as the pivot. This choice significantly improves QuickSort's performance. By selecting a pivot that is more likely on average to be closer to the median element, we reduce the chances of encountering arrays that are already sorted or nearly sorted. This decreases the risk of worst-case scenarios and allows QuickSort to work more efficiently.

Moreover, selecting the middle element as the pivot leads to more balanced partitioning. The resulting partitions are usually of similar sizes, ensuring that subsequent recursive calls work on subarrays of comparable lengths. This balance makes sorting more efficient, as each recursive call processes a significant portion of the remaining unsorted elements.

Let's revisit our sorted array [1, 2, 3, 4, 5, 6]. If we choose the middle element as the pivot:

• Pivot: 3 (middle element)
• Partitions: [1, 2], and [4, 5, 6]

Each recursive call processes roughly half of the elements:

1. Left Partition: [1, 2]
   • Pivot: 1
   • Partitions: [] and [2]
2. Right Partition: [4, 5, 6]
   • Pivot: 5
   • Partitions: [4] and [6]

This reduces the depth of the call stack and achieves O(Nlog⁡N) time complexity.

---

Implementation

The implementation of QuickSort differs slightly depending on whether the first or middle element is chosen as the pivot. When we choose the middle index as the pivot, the only change is that at the beginning of the partition step, we swap it with the first element of the array segment. This standardizes the partitioning process, allowing us to continue as usual. Below is the code with the middle index chosen as the pivot, and the adjusted line is highlighted.

function partition(arr, low = 0, high = arr.length - 1) {
  const pivotIndex = Math.floor((low + high) / 2);
  const pivot = arr[pivotIndex];

  #highlight
  // Move pivot to the beginning of the array segment
  [arr[pivotIndex], arr[low]] = [arr[low], arr[pivotIndex]];
  #endhighlight

  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]];
      left++;
      right--;
    }
  }

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

Note that this implementation works for any pivot position. When the pivot is at the beginning, as in the previous assignment, there is no need for a swap since it would just swap the element with itself.

In the next assignment, we will learn about the "Divide and Conquer" algorithm steps in the QuickSort algorithm.