Quicksort

Introduction

Quicksort is the fastest known comparison-based sorting algorithm for arrays in the average case.

Caveat: Merge sort works better on linked lists, and there are other non-comparison based algorithms that outperform quicksort.

$$$$

Quick sort algorithm

1. Start with an array of n elements.

2. Choose a pivot element from the array to be sorted.

3. Partition the array into two unsorted subarrays, such that all elements in one subarray are less than the pivot and all the elements in the other subarray are greater than the pivot.

4. Elements that are equal to the pivot can go in either subarray.

5. Sort each subarray recursively to yield two sorted subarrays.

6. Concatenate the two sorted subarrays and the pivot to yield one sorted array.

Note that if we always pick the smallest element in the array as the pivot, the left-hand side array is always empty, and all the remaining items end up in the right-hand side array. This means that the array will be subdivided a total of $O(n)$ times. Since the partitioning takes $O(n)$ time for each divide step., this has a total time complexity of $O(n^2)$. This is the worst-case time complexity for Quicksort because the depth of recursion is maximum.

The following set of slides shows the partitioning at each recursive depth for a worst-case scenario