Animated Sorting Algorithm Demo: Quick Sort

Algorithm

# choose pivot
i = rand(1,n)
swap a[1,i]

# 2-way partition
k = 0
for i = 2:n, if a[i] < a[1], swap a[++k,i]
swap a[1,k]

# recursive sorts
sort a[1..k-1]
sort a[k+1,n]
        

Properties

• Not stable
• In place
• Worst case O(n) extra space for recursion stack
• Best case Ω(lg(n)) extra space for recursion stack
• Worst case O(n²) time
• Typically O(n·lg(n)) time
• Basically non-adaptive

Discussion

When carefully implemented, quicksort has low overhead. When a stable sort is not needed, quicksort is a decent general-purpose sort -- though the 3-way partitioning version should be used to avoid quadratic behavior.

The time complexity ranges between n*lg(n) and n² depending on the key distribution and the pivot choices. When the key distribution has low entropy (many different values), choosing a pivot randomly guarantees O(n*lg(n)) time with very high probability. However, when there are O(1) unique keys, the standard 2-way partitioning quicksort exhibits its worst case O(n²) time complexity no matter the pivot choices.

Directions

• Click on to restart the animations.
• Click on a size number to change the size of the examples.
• Click on a cell to restart an individual animation.
• Click on a cell title to explore that input order.

Key

• Black values are sorted.
• Gray values are unsorted.
• Dark gray values show the current sub-array that is being sorted recursively.
• A pair of red triangles mark the left and right pointers traditionally used in quicksort.

References

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.