Introduction to C-Programming As seen in ENGS 20

QuickSort is a divide and conquer algorithm: rather than repeatedly scanning the whole list like bubble sort does, it picks one element of the list— called the pivot— and rearranges the list so that every element smaller than the pivot ends up to its left, and every element larger ends up to its right. This rearranging step is called partitioning. Once the list has been partitioned around the pivot, the pivot itself is in its final, correct position, and QuickSort is called recursively on the (smaller) sublist to its left and the (smaller) sublist to its right.

In the example below, the pivot is chosen to always be the last element of the (sub)list being partitioned. The function partition() rearranges the list around the pivot and returns the pivot’s final index; quickSort() then calls itself on the two sides:

Notice that printArray() is called inside partition() after every partitioning step— run the code above and watch how the list gradually becomes sorted, one pivot at a time.

The animation below might help you visualize how QuickSort functions.