Algorithm - Quicksort

Quicksort is a divide and conquer algorithm. Quick Sort does sorting in place, this means no extra memory needed to store a copy on the data (like in the Merge step of a Merge Sort). Quicksort algorithm consists of two parts, the partition (split into smaller sets) by the pivot and the swapping of positions relative to the pivot (sort).

Quicksort partitions the dataset using a pivot value of the dataset. This value is used to compare if a value is smaller or greater than the pivot and values that are smaller than the pivot are moved left of the pivot and values that are greater than the pivot is moved right of the pivot. The end results is a set that is sorted relative to the pivot. At this point the sorting might not be compete.

Depending on the size of the dataset, multiple iterations (recursion) of the partition and swapping relative to the pivot has to occur. Each iteration using a different pivot value until eventually, a single element in the set. (Single elements in a set is by default sorted.)

Note that most of the work is done at the partition level, whereas for Merge sort, most work is done at the merge step.

Pseudocode

  1. start with any pivot point (any element in the array).

    • We use the head value of a set because it makes code simpler.
    • we will use array[0] for consistency.
  2. Starting from array[1] and array[array.length-1], track the index with l and r respectively.

  3. Compare array[l] with array[r]:

    • if array[0] (pivot) > array[l], increase index l by 1, l++;
    • if array[0] (pivot) < array[l], decrease index r by 1, r– until array[pivot] > array[r]
      • when array[pivot] > array[r], swap array[l] with array[r]
      • when r > l crossing point reached.
    • advance l…
  4. Repeat 1-3 until index l > r.

  5. swap array[0] with array[r] if l > r. (swap pivot with the last element of the partition, array[r])

    • array left of l will all be smaller than l.
    • array right of l will all be greater than l.
    • this is the end of the recursion.
  6. r is the new split pivot point.

  7. Repeat 1-5 until array cannot split annymore.

    • The partition will eventually be 1 array sized. (same as Merge sort), last-first <= 1
    • or l > r.

QuickSort recursion of partitioning and sorting elements relative to the pivot.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
function quickSort(array, first, last) {
// breaking condition, at some point the partition will only contain 1
//if (last - first > 1) {
if (last > first) {
var partitionIndex = partition(array, first, last);
quickSort(array, first, partitionIndex - 1);
quickSort(array, partitionIndex + 1, last);
}
}
function partition(array, first, last) {
const pivot = first;
let l = first + 1;
let r = last;

while (pivot < last) {
if (l > r) { // exit since l and r have crossed.
swap(array, pivot, r); // swap right with pivot
break;
}
// only swap if both L & R are not in correct position relative to pivot
// i.e.: L > pivot AND R < pivot
if (array[pivot] < array[l]) {
// L > pivot, must find R to swap with...
while (array[pivot] < array[r]) {
r--;
}
// found array[r] that is smaller than array[pivot]
// check that L/R have not crossed.
if (r > l) {
swap(array, l, r); // swap left with right
}
}
l++;
}
return r;
}
function swap(array, pointer1, pointer2) {
const temp = array[pointer1];
array[pointer1] = array[pointer2];
array[pointer2] = temp;
}
(() => {
const data = [20, 6, 8, 53, 23, 87, 42, 19];
quickSort(data, 0, data.length - 1);
console.log(data); //[ 6, 8, 19, 20, 23, 42, 53, 87]
})();

Selecting the Pivot

There are many variations of the Quicksort algorithm described. One such variation is how to select the pivot value.
Below are example pivots used:

  1. First element of partition
  2. Last element of partition
  3. Median value of partition

The pivot value will determine how evenly partitioned the sets will be. If a pivot value is unbalanced, depending on the data, most elements might end up on one side of the pivot.

Illustration of how a left/right pivot can lead to bad algorithmic performance

Above shows an example of an array of [2,1,6,7,13,16,15], and using 6 as a pivot. The following can be observed:

  • All (except 16) is smaller than the pivot, so most elements are not swapped.
  • for each recursion, there are n-1 comparison operations
  • The pivot for the remaining recursions for [1,6,7,13,16,15] are 1, 6, 7, etc… That is (n-1 operations) for (n-1) elements in the partition.

Using a median pivot value can prevent partition sets from being lopsided to the left/right of the pivot value. By dividing the partition in a balanced manner we get closer to a worst run time of O(nlog(2)n) instead of a O(n) or even O(n^2) operation. Using balanced partitions, the least number of recursions are needed to reach a partition of a single element. (Similar to searching a balanced vs un-balanced tree)

Time complexity

In dataset where the data is almost fully sorted, Quicksort performs badly with the worst case time complexity of O(n^2). This is because near sorted datasets in Quicksort would involve visiting n-1 elements where n is the number of elements in the array. Consider this for all the partitions and you can see that the run time ends up with n^2 comparisons in the worst case. (The pivot advances in a worst case fashion of n-1 in a nearly sorted set)

Other Factors

Quicksort has an advantage over Merge sort in that Quicksort does sorting in place. However in most real life use cases of sorting, memory usage isn’t a major concern. When evaluating whether to use Merge sort or Quicksort, the importance of the stability of sorting must be considered.

Quicksort should be avoided for nearly sorted data. (See selecting the pivot)

Source - Alternative QuickSort