7.7. Quick sort

The quick sort uses divide and conquer to gain the same advantages as the merge sort, while not using additional storage. As a trade-off, however, it is possible that the list may not be divided in half. When this happens, we will see that performance is diminished.

A quick sort first selects a value, which is called the pivot value. Although there are many different ways to choose the pivot value, we will simply use the first item in the list. The role of the pivot value is to assist with splitting the list. The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will be used to divide the list for subsequent calls to the quick sort.

The following sequence shows how partitioning places the first pivot, 54, at its split point. The marker scans and exchanges lead to a completed partition ready for recursive sorting.

Quick sort: choose a pivot, partition, and recurse

Card 1: Choose 54 as the first pivot.

The first item, 54, is the pivot value. Partitioning will find its split point and exchange items so that smaller values lie to its left and larger values lie to its right.

Text description

Array with 9 cells. From left to right: index 0: “54”, index 1: “26”, index 2: “93”, index 3: “17”, index 4: “77”, index 5: “31”, index 6: “44”, index 7: “55”, and index 8: “20”.

index 0: “54” is highlighted.

Indicator “pivot” points to cell 0, value “54”.

Card 2: Start the left and right markers.

Set leftmark to position 1 and rightmark to position 8. These markers scan toward each other through the items after the pivot.

Advance leftmark past values less than or equal to the pivot. Move rightmark left past values greater than or equal to the pivot. Each scan stops if the markers cross. Equal values may end up on either side of the pivot.

Text description

Array with 9 cells. From left to right: index 0: “54”, index 1: “26”, index 2: “93”, index 3: “17”, index 4: “77”, index 5: “31”, index 6: “44”, index 7: “55”, and index 8: “20”.

index 1: “26” and index 8: “20” are highlighted.

Indicator “pivot” points to cell 0, value “54”.

Indicator “leftmark” points to cell 1, value “26”.

Indicator “rightmark” points to cell 8, value “20”.

Card 3: Move leftmark past 26; stop at 93.

At position 1, 26 is less than 54, so advance leftmark to position 2. Stop there because 93 is greater than the pivot. This value belongs on the right side of the eventual split point.

Text description

Array with 9 cells. From left to right: index 0: “54”, index 1: “26”, index 2: “93”, index 3: “17”, index 4: “77”, index 5: “31”, index 6: “44”, index 7: “55”, and index 8: “20”.

index 2: “93” is highlighted.

Indicator “pivot” points to cell 0, value “54”.

Indicator “leftmark” points to cell 2, value “93”.

Indicator “rightmark” points to cell 8, value “20”.

Card 4: Stop rightmark at 20.

At position 8, 20 is less than 54, so rightmark stops immediately. The markers have not crossed: position 2 is before position 8. The values 93 and 20 are on the wrong sides and must be exchanged.

Text description

Array with 9 cells. From left to right: index 0: “54”, index 1: “26”, index 2: “93”, index 3: “17”, index 4: “77”, index 5: “31”, index 6: “44”, index 7: “55”, and index 8: “20”.

index 2: “93” and index 8: “20” are highlighted.

Indicator “pivot” points to cell 0, value “54”.

Indicator “leftmark” points to cell 2, value “93”.

Indicator “rightmark” points to cell 8, value “20”.

Card 5: Exchange 93 and 20.

Exchange the values at positions 2 and 8. Position 2 now holds 20, and position 8 holds 93. Keep the pivot at position 0 and resume the scans from the current marker positions.

Text description

Array with 9 cells. From left to right: index 0: “54”, index 1: “26”, index 2: “20”, index 3: “17”, index 4: “77”, index 5: “31”, index 6: “44”, index 7: “55”, and index 8: “93”.

index 2: “20” and index 8: “93” are highlighted.

Indicator “pivot” points to cell 0, value “54”.

Indicator “leftmark” points to cell 2, value “20”.

Indicator “rightmark” points to cell 8, value “93”.

Card 6: Move leftmark past 20 and 17; stop at 77.

The values 20 at position 2 and 17 at position 3 are less than 54. Advance leftmark past both to position 4. Stop at 77 because it is greater than the pivot.

Text description

Array with 9 cells. From left to right: index 0: “54”, index 1: “26”, index 2: “20”, index 3: “17”, index 4: “77”, index 5: “31”, index 6: “44”, index 7: “55”, and index 8: “93”.

index 4: “77” is highlighted.

Indicator “pivot” points to cell 0, value “54”.

Indicator “leftmark” points to cell 4, value “77”.

Indicator “rightmark” points to cell 8, value “93”.

Card 7: Move rightmark past 93 and 55; stop at 44.

The values 93 at position 8 and 55 at position 7 are greater than 54. Move rightmark left past both to position 6. Stop at 44 because it is less than the pivot. The markers have not crossed, so exchange 77 and 44.

Text description

Array with 9 cells. From left to right: index 0: “54”, index 1: “26”, index 2: “20”, index 3: “17”, index 4: “77”, index 5: “31”, index 6: “44”, index 7: “55”, and index 8: “93”.

index 4: “77” and index 6: “44” are highlighted.

Indicator “pivot” points to cell 0, value “54”.

Indicator “leftmark” points to cell 4, value “77”.

Indicator “rightmark” points to cell 6, value “44”.

Card 8: Exchange 77 and 44.

Exchange the values at positions 4 and 6. Position 4 now holds 44, and position 6 holds 77. Resume both scans to find the split point.

Text description

Array with 9 cells. From left to right: index 0: “54”, index 1: “26”, index 2: “20”, index 3: “17”, index 4: “44”, index 5: “31”, index 6: “77”, index 7: “55”, and index 8: “93”.

index 4: “44” and index 6: “77” are highlighted.

Indicator “pivot” points to cell 0, value “54”.

Indicator “leftmark” points to cell 4, value “44”.

Indicator “rightmark” points to cell 6, value “77”.

Card 9: Move leftmark past 44 and 31; stop at 77.

The values 44 at position 4 and 31 at position 5 are less than 54. Advance leftmark to position 6 and stop at 77. Both markers now point to position 6; they have met but have not yet crossed.

Text description

Array with 9 cells. From left to right: index 0: “54”, index 1: “26”, index 2: “20”, index 3: “17”, index 4: “44”, index 5: “31”, index 6: “77”, index 7: “55”, and index 8: “93”.

index 6: “77” is highlighted.

Indicator “pivot” points to cell 0, value “54”.

Indicator “leftmark” points to cell 6, value “77”.

Indicator “rightmark” points to cell 6, value “77”.

Card 10: Move rightmark left; the markers cross.

At position 6, 77 is greater than 54, so move rightmark left to position 5, which holds 31. Now rightmark is less than leftmark: 5 is less than 6. Stop scanning without another exchange between the markers. Position 5 is the split point.

Text description

Array with 9 cells. From left to right: index 0: “54”, index 1: “26”, index 2: “20”, index 3: “17”, index 4: “44”, index 5: “31”, index 6: “77”, index 7: “55”, and index 8: “93”.

index 5: “31” and index 6: “77” are highlighted.

Indicator “pivot” points to cell 0, value “54”.

Indicator “leftmark” points to cell 6, value “77”.

Indicator “rightmark” points to cell 5, value “31”.

Card 11: Exchange the pivot with 31 at the split point.

Exchange the pivot at position 0 with 31 at position 5. The pivot value 54 is now at its final sorted position.

Positions 0 through 4 contain [31, 26, 20, 17, 44], all less than 54. Positions 6 through 8 contain [77, 55, 93], all greater than 54. The two ranges are partitioned, but are not yet sorted.

Text description

Array with 9 cells. From left to right: index 0: “31”, index 1: “26”, index 2: “20”, index 3: “17”, index 4: “44”, index 5: “54”, index 6: “77”, index 7: “55”, and index 8: “93”.

index 0: “31” and index 5: “54” are highlighted.

Indicator “pivot” points to cell 5, value “54”.

Card 12: Recursively sort the ranges on either side of 54.

Apply quick sort to positions 0 through 4, then to positions 6 through 8. Each recursive call selects the first item of its range as a pivot and repeats the same partition process.

These ranges stay in the original array. Exclude position 5 from both calls because 54 is already in place. A range with zero or one item is sorted by definition and needs no partition. Continuing the recursion produces [17, 20, 26, 31, 44, 54, 55, 77, 93].

Text description

Array with 9 cells. From left to right: index 0: “31”, index 1: “26”, index 2: “20”, index 3: “17”, index 4: “44”, index 5: “54”, index 6: “77”, index 7: “55”, and index 8: “93”.

index 5: “54” is highlighted.

Indicator “pivot” points to cell 5, value “54”.

Quick Sort

The partition function implements the process described earlier. The following program sorts the list that was used in the example above.

Run It

The Quick Sort

#include <iostream>
#include <string>
#include <utility>
#include <vector>
using std::vector;

void print(const vector<int>& data) {
   for (const auto& value: data) {
      std::cout << value << ' ';
   }
   std::cout << '\n';
}

template <typename RandomIt>
RandomIt partition(RandomIt first, RandomIt last) {
   if (first == last) return first;

   auto pivotvalue = *first;
   RandomIt leftmark  = first + 1;
   RandomIt rightmark = last - 1;
   bool done = false;
   while (!done) {
      while(leftmark <= rightmark &&
            *leftmark <= pivotvalue) {
        ++leftmark;
      }
      while(rightmark >= leftmark &&
            *rightmark >= pivotvalue) {
        --rightmark;
      }
      if(rightmark<leftmark) {
         done = true;
      } else {
         std::swap(*rightmark, *leftmark);
      }
   }
   std::swap(*rightmark, *first); //*
   return rightmark;
}

template <typename RandomIt>
void quick_sort(RandomIt first, RandomIt last)
{
   if (std::distance(first, last) > 1) {
        RandomIt pivot = partition(first, last);
        quick_sort(first, pivot);
        quick_sort(pivot + 1, last);
   }
}

int main() {
  vector<int> data = {54, 26, 93, 17, 77, 31, 44, 55, 20};
  quick_sort(data.begin(), data.end());
  print(data);
  return 0;
}

The following animations show quick sort in action. Yellow marks the current pivot, red marks values being compared or exchanged, teal marks a scan boundary, and gray marks pivot values that have been placed.

Average case

Open video

Best case

Open video

Worst case

Open video

7.7.1. Quick sort analysis

To analyze the quick_sort function, note that for a list of length n, if the partition always occurs in the middle of the list, there will again be \(\log n\) divisions. In order to find the split point, each of the n items needs to be checked against the pivot value. Therefore, the average case complexity is \(n\cdot \log n\). In addition, there is no copying of list data as in the merge sort process.

The ideal pivot selection point is the median value in the data set, however the cost to find the median often exceeds the benefits for many typical data sets.

Unfortunately, in the worst case, the split points may not be in the middle and can be very skewed to the left or the right, leaving a very uneven division. In this case, sorting a list of n items divides into sorting a list of 0 items and a list of \(n-1\) items. Then sorting a list of \(n-1\) divides into a list of size 0 and a list of size \(n-2\), and so on. The result is an \(O(n^{2})\) sort with all of the overhead that recursion requires. This worst case example is shown in the above code example.

A recursive \(O(n^{2})\) algorithm makes quick sort susceptible to stack overflow errors on very large data sets.

Quick sort therefore poses an interesting dilemma. The quick sort average case is very fast. It tends to be the fastest, on average, of the known \(O(n \cdot log{n})\) average case sorting algorithms in actual clock time. But its worst case is just dreadful.

So the suitability of quick sort winds up coming down to a question of how often we would actually expect to encounter the worst case or nearly worst case behavior. That, in turn, depends upon the choice of pivot.

We mentioned earlier that there are different ways to choose the pivot value. In particular, we can attempt to alleviate some of the potential for an uneven division by using a technique called median of three. To choose the pivot value, we will consider the first, the middle, and the last element in the list. In our example, those are 54, 77, and 20. Now pick the median value, in our case 54, and use it for the pivot value (of course, that was the pivot value we used originally). The idea is that in the case where the first item in the list does not belong toward the middle of the list, the median of three will choose a better "middle" value. This will be particularly useful when the original list is somewhat sorted to begin with. We leave the implementation of this pivot value selection as an exercise.

Self Check

Q1

Given the following list of numbers [14, 17, 13, 15, 19, 10, 3, 16, 9, 12] which answer shows the contents of the list after the second partitioning according to the quicksort algorithm?

[9, 3, 10, 13, 12]

It's important to remember that quicksort works on the entire list and sorts it in place.

[9, 3, 10, 13, 12, 14]

Remember quicksort works on the entire list and sorts it in place.

[9, 3, 10, 13, 12, 14, 17, 16, 15, 19]

The first partitioning works on the entire list, and the second partitioning works on the left partition not the right.

[9, 3, 10, 13, 12, 14, 19, 16, 15, 17]

The first partitioning works on the entire list, and the second partitioning works on the left partition.

Check answer

Q2

Given the following list of numbers [1, 20, 11, 5, 2, 9, 16, 14, 13, 19] what would be the first pivot value using the median of 3 method?

1

The three numbers used in selecting the pivot are 1, 9, 19. 1 is not the median, and would be a very bad choice for the pivot since it is the smallest number in the list.

9

Good job.

16

although 16 would be the median of 1, 16, 19 the middle is at len(list) // 2.

19

the three numbers used in selecting the pivot are 1, 9, 19. 9 is the median. 19 would be a bad choice since it is almost the largest.

Check answer

Q3

Which of the following sort algorithms are guaranteed to be O(n log n) even in the worst case?

Shell Sort

Shell sort is between O(n) and O(n^2)

Quick Sort

Quick sort can be O(n log n), but if the pivot points are not well chosen and the list is just so, it can be O(n^2).

Merge Sort

Merge Sort is the only guaranteed O(n log n) even in the worst case. The cost is that merge sort uses more memory.

Insertion Sort

Insertion sort is O(n^2)

Check answer

Q4

Match each sorting method with its appropriate estimated comparisons.

Insertion/Bubble/Merge Choose a definition between O(n) and O(n^2) O(n log n) O(n log n) or O(n^2) O(n^2)

Merge Sort Choose a definition between O(n) and O(n^2) O(n log n) O(n log n) or O(n^2) O(n^2)

Quick Sort Choose a definition between O(n) and O(n^2) O(n log n) O(n log n) or O(n^2) O(n^2)

Shell Sort Choose a definition between O(n) and O(n^2) O(n log n) O(n log n) or O(n^2) O(n^2)

Check answer

Q5

Which sort should you use for best efficiency if you need to sort through 100,000 random items in a list?

Merge

Correct!

Selection

Selection sort is inefficient in large lists.

Bubble

Bubble sort works best with mostly sorted lists.

Insertion

Insertion sort works best with either small or mostly sorted lists.

Check answer

More to Explore

• OpenDSA: Quicksort

• C++ std::nth_element

• Quick Sort visualization

Acknowledgements

This section is adapted from Problem Solving with Algorithms and Data Structures using C++, by Brad Miller and David Ranum, Luther College, and Jan Pearce, Berea College released under the CC BY-NC-SA 4.0.