Truly Understanding Quicksort

How to implement quicksort

Let us write a function “sort” that takes an array “a” and its size, “n”, as inputs and sorts the array in place.

void sort(int a[], int n)
{
}

Since the recursive calls should sort subarrays, we will need an auxiliary function

void sort_range(int a[], int first, int last)
{
}

that sorts the subrange of the array “a” between “first” and “last”.

The function “sort” then simply calls sort_range for the entire array:

void sort(int a[], int n)
{
  sort_range(a, 0, n - 1);
}

The sort_range function is a recursive function implementing the quicksort algorithm. As with any recursive function that terminates, we must have some base case where recursion is not necessary anymore. This is the case for subarrays having 0 or 1 elements, as these are already sorted:

void sort_range(int a[], int first, int last)
{
  if (first >= last) {
    // no need to do anything, we are done
  } else {
    // ...
  }
}

For the recursive case, recall that we first need to partition the subarray. We will define a function

int partition(int a[], int first, int last)
{
}

that will partition the array and return the position of the pivot after partitioning.

Assume for a second that partition is done. How do we use it to fill in our sort_range function?

In the recursive case, we first partition the array. This brings the pivot to position pivot_pos and this is, as discussed, the final position of the pivot in the sorted array. What remains to be done is for the two sides to be sorted recursively.

void sort_range(int a[], int first, int last)
{
  if (first >= last) {
    // no need to do anything, we are done
  } else {
    int pivot_pos = partition(a, first, last);
    sort_range(first, pivot_pos - 1);
    sort_range(pivot_pos + 1, last);
  }
}

It remains to fill in the “partition” function. We make use of the auxiliary function “swap” below:

void swap(int *a, int *b)
{
  int t = *a;
  *a = *b;
  *b = t;
}

In “partition”, we initialise “l” and “r” as explained earlier. The pivot is always at position “l”.

int partition(int a[], int first, int last)
{
  int l = first;
  int r = last;
  // ...
}

We must repeat the three steps until l and r become equal.

int partition(int a[], int first, int last)
{
  int l = first;
  int r = last;
  while (l != r) {
    if (a[r] >= a[l]) {
      r--;
    } else if (a[l + 1] <= a[l]) {
      swap(&a[l], &a[l + 1]);
      l++;
    } else {
      swap(&a[l + 1], &a[r]);
    }
  }
  return l;
}

Enjoyed our tutorial on quicksort? Cannot wait to understand more interesting algorithms and data structures? Subscribe to the TrulyUnderstandingAlgorithms Youtube channel to stay up to date with our videos. Also consider liking our video and leaving a comment with topics that you would like to us cover in the future.