3.3.6 Quick Sort

Knowledge Base > Algorithm > Sorting

Overview

Quick Sort is well known as ’the best practical sorting algorithm’. It makes Θ(n ⋅ lgn) comparisons on average, and O(n²) comparisons in the worst case. Typically, Quick Sort performs faster than other O(n ⋅ lgn) sorting algorithms.

Algorithm

Pseudocode

Quick-Sort(A)

1 if p < r 2    then q ← Partition(A,p,r) 3       Quick-Sort(A,p,q - 1) 4       Quick-Sort(A,q + 1,r)

Partition(A,p,r)

1 x ← A[r] 2 i ← p - 1 3 for j ← p to r - 1 4 do if A[j] ≤ x 5          then i ← i + 1 6             swap A[i] ↔ A[j] 7 swap A[i + 1] ↔ A[r] 8 return i + 1

Quicksort sorts by applying a divide and conquer strategy (of method 3.1.6) to divide a list into two sublists, and performs the following operations:

• Pick an element, called a pivot, from the list.
• Partition the list so that all elements which are less than the pivot come before the pivot, and elements greater than the pivot come after it. For instance,
  
• Recursively repeat those operations to sort the sublists of lesser elements and of greater elements.

Time Complexity

The performance of Quick Sort always depends on the position of selected pivot. A bad pivot could lead to poor performance, for instance, selecting position 1 as the pivot produces a recursion tree of height n. Conversely, a good pivot would operate at best performance of O(n ⋅ lgn) of tree height Θ(lgn), pivot at the middle of the list, for instance. Therefore, trivial cases, such as sorting a list of sorted element, or of all duplicated elements, have no direct effect on performance.

Similar to merge sort, Quick sort can at most compare and swap every elements for each pass, and lg n of iterations for total. Thus, a O(n ⋅ lg n) of comparisons and swaps can be expected in the worst case.

This brings up with an idea of Randomized Quick Sort, which is implemented to choose the pivot at random. Ideally, this approach performs at average-case behaviors, but in practice, choosing the right pivot dominates the performance.

Space Complexity

Quick sort does not sort in place, meaning that a new memory space must be allocated for the sorted output to be stored in whenever the partition operation is performed. The recursive tree can help us view it; only constant space O(1) at each level of partition multiplies the height of the tree, which is lg n. Thus, a total of O(lg n) extra space is used.

Stability

Quick Sort is not a stable sort, because the order of occurrence of duplicated elements is miss-ordered during the operation of swap.

Source Code

• Quick Sort (C)