Quicksort

Quicksort is a recursive sorting algorithm which use a pivot and compare it to other items in the array. It will split items into two sections where one represent items that are smaller than the pivot and the other larger.

Analysis

• It will result in \(O(N \log N)\) in average case and \(O(N^2)\) in the worst case
• The worst case scenario is unlikely if the pivot is chosen wisely

Attention

• It is advised to avoid using Quicksort on small arrays (\(N \le 20\)). They could be sorted by 202202220937 instead.
• Do not choose the first element as the pivot! This will result in \(O(N^2)\) for presorted array.

Implementation

The following algorithm will use the Median-of-Three partitioning strategy Hoare partition scheme to choose a pivot.

Note: It sorts the array in ascending order.

ElementType Median3(ElementType A[], int Left, int Right) {
  int Center = (Left + Right) / 2;

  if (A[Left] > A[Center])
    Swap(&A[Left], &A[Center]);
  if (A[Left] > A[Right])
    Swap(&A[Left], &A[Right]);
  if (A[Center] > A[Right])
    Swap(&A[Center], &A[Right]);

  Swap(&A[Center], &A[Right - 1]);  // Hide pivot
  return A[Right - 1];              // Return pivot
}

int Partition(ElementType A[], int Left, int Right)
{
  ElementType Pivot = Median3(A, Left, Right);
  int i = Left - 1;
  int j = Right + 1;

  for (;;) {
    while (A[++i] < Pivot) {}
    while (A[--j] > Pivot) {}
    if (i >= j) {
      return j;
    } 

    Swap(&A[i], &A[j]);
  }
}

void Qsort(ElementType A[], int Left, int Right) {
  if (Left < Right) {
    int Pivot = Partition(A, Left, Right);
    Qsort(A, Left, Pivot);
    Qsort(A, Pivot + 1, Right);
  }
}

void Quicksort(ElementType A[], int N) {
  Qsort(A, 0, N - 1);
}