Quick Sort

Quick Sort

Pseudocode

Algorithm 7: Quick Sort
Algorithm 8: In-Place Partition

Analysis

• The performance of Quick Sort is highly dependent on how evenly the partitioning is done.
• Partitioning efficiency depends directly on the pivot choice.

Best Case

• Ideal pivot choice: Always choose the median element.
• This evenly divides the list into two equal parts.
• Resulting in two recursive calls to Quick Sort on lists roughly half the size.
• It requires a linear number of comparisons to partition the elements.
• The recurrence relation is: $$C(n) = 2C\left(\frac{n}{2}\right) + n$$
• By the Master Theorem, the time complexity is $O(n \log n)$.

Worst Case

• Worst pivot choice: An extremal element (smallest or largest).
• Divides the list into an empty list and a list of size $(n - 1)$.
• Only one recursive call is necessary, but it is on a list of size $(n - 1)$.
• The recurrence relation is: $$C(n) = C(n - 1) + n$$
• Solving this by back substitution yields $O(n^2)$.

Average Case

• Even if the list is split by a constant proportion (e.g., 10% and 90%), the time complexity is still $O(n \log n)$.
• A careful average case analysis also yields $$C(n) \approx 1.38n \log n$$
• This remains $O(n \log n)$.

Pivot Choice: Strategies to Avoid the Worst Case

Pivot choice greatly affects performance; several common strategies include:

• Median-of-Three: Select the pivot as the median of three elements (typically the first, middle, and last elements).
– Guarantees that the pivot choice will never be the absolute worst case.
– Does not guarantee $\Theta(n \log n)$ in all edge cases, but is efficient in practice.
• Random Element: Randomly select an index for the pivot element.
– Guarantees an expected average running time of $\Theta(n \log n)$.
– Requires extra work for random number generation.
• Linear Time Median Finding.
– An algorithm exists that runs in $\Theta(n)$ time to find the true median of $n$ objects.
– Guarantees $\Theta(n \log n)$ in all cases (best, average, and worst).
– However, it is complicated, recursive, and has significant constant overhead.

Code Samples

Code Sample 15: Java Quick Sort for integers
1
2
3
4
5
6
7
private static void quickSort(int a[], int left, int right) {
  int index = partition(a, left, right);
  if (left < index - 1)
    quickSort(a, left, index - 1);
  if (index < right)
    quickSort(a, index, right);
}
Code Sample 16: Java Partition subroutine for integers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int partition(int a[], int left, int right)
{
  int i = left, j = right;
  int tmp;
  int pivot = a[(left + right) / 2];
  while (i <= j) {
    while (a[i] < pivot)
      i++;
    while (a[j] > pivot)
      j--;
    if (i <= j) {
      tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
      i++;
      j--;
    }
  }
  return i;
}
Code Sample 17: C Quick Sort for integers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void swap(int *a, int *b)
{
  int t = *a; *a = *b; *b = t;
}

void sort(int arr[], int beg, int end)
{
  if (end > beg + 1)
  {
    int piv = arr[beg], l = beg + 1, r = end;
    while (l < r)
    {
      if (arr[l] <= piv)
        l++;
      else
        swap(&arr[l], &arr[--r]);
    }
    swap(&arr[--l], &arr[beg]);
    sort(arr, beg, l);
    sort(arr, r, end);
  }
}

A good tutorial with a non-recursive C implementation can be found here: http://alienryderflex.com/quicksort/