Quicksort

Lecturer: Dr. Keyhanipour

 Outline
• Iterative sorting algorithms (comparison based)
• Selection Sort
• Bubble Sort
• Insertion Sort
• Recursive sorting algorithms (comparison based)
• Merge Sort
• Quick Sort
• Heap Sort
• Radix sort (non-comparison based)
• Properties of Sorting:
• In-place sort, stable sort

2
 Sorting Algorithms so far
• Insertion sort, Selection sort, and Bubble sort:
• Worst-case running time Θ(𝑛2); in-place
• Merge sort:
• Worst-case running time Θ(𝑛 log 𝑛), but requires additional memory
Θ(𝑛);

3
 Quick Sort
• Characteristics:
• Like insertion sort, but unlike merge sort, sorts in-place, i.e., does
not require any additional array
• Very practical, average sort performance 𝑂(𝑛 log 𝑛) (with small
constant factors), but worst case 𝑂(𝑛2)

4
 Quick Sort: The Principle
• A divide-and-conquer algorithm
• Divide: partition array into two subarrays such that:
• elements in the lower part <= elements in the higher part
• Conquer: recursively sort the two subarrays
• Combine: trivial since sorting is done in place

5
 Description of Quicksort
• Quicksort an 𝑛-element array:
1. Divide: Partition the array into two subarrays around a pivot 𝑥
such that elements in lower subarray ≤ 𝑥 ≤ elements in upper
subarray.

≤𝒙 𝒙 ≥𝒙

2. Conquer: Recursively sort the two subarrays.

3. Combine: Trivial.

6
 Description of Quicksort
• To sort a subarray 𝐴[𝑝. . 𝑟]:
1. Divide: PARTITION 𝐴[𝑝. . 𝑟] into two parts 𝐴[𝑝. . 𝑞 − 1] and
𝐴[𝑞 + 1. . 𝑟].
• ∀𝑎 ∈ 𝐴 𝑝. . 𝑞 − 1 : 𝑎 ≤ 𝐴[𝑞]
• ∀𝑎 ∈ 𝐴 𝑞 + 1. . 𝑟 : 𝑎 ≥ 𝐴[𝑞]
2. Conquer: sort the two subarrays by recursive calls to
QUICKSORT.
3. Combine: no work is needed, because they are sorted in place.

7
 Quicksort: Pseudocode
template<class T>
void quickSort(T data[], int p, int r) {
if (p < r) {
// partition data[] and return the index of the pivot item
q = Partition (data, p, r)
// recursively sort the two portions
quickSort (data, p, q-1);
quickSort (data, q+1, r);
}
}
Initial call: quickSort(data, 1, n)
8
 Partition(A, p, r)
• A linear time partitioning procedure.
• Partition always selects the last element A[r] in the subarray A[p .. r] as
the pivot — the element around which to partition.
• As the procedure executes, the array is partitioned into four regions,
some of which may be empty:
• All entries in A[p . . i] ≤ pivot .
• All entries in A[i+1 .. j-1] > pivot .
• A[r] = pivot.
• It’s not needed as part of the loop invariant, but the fourth region is A[j .. r-1],
whose entries have not yet been examined, and so we don’t know how they
compare to the pivot.

9
 Partition(A, p, r)
• The four regions maintained by the procedure Partition on a
subarray 𝐴[𝑝 . . 𝑟]:
• Entries in 𝐴[𝑝 . . 𝑖] ≤ 𝑝𝑖𝑣𝑜𝑡 .
• Entries in 𝐴[𝑖 + 1 . . 𝑗 − 1] > 𝑝𝑖𝑣𝑜𝑡 .
• 𝐴[𝑟] = 𝑝𝑖𝑣𝑜𝑡 .
• The subarray 𝐴[𝑗 . . 𝑟 − 1] can take on any values.

10
 Partitioning: Pseudocode
Partition (A, p, r)
1 x = A[r] // the pivot point
2 i = p–1
3 for j = p to r-1
4 if A[j] ≤ x // 𝐴[𝑝 . . 𝑖] ≤ 𝑝𝑖𝑣𝑜𝑡
5 i=i+1
6 exchange A[i] with A[j] // 𝐴[𝑖 + 1 . . 𝑗 − 1] > 𝑝𝑖𝑣𝑜𝑡
7 exchange A[i+1] with A[r] ≤𝒙 𝒙 ≥𝒙
8 return i+1

11
 Partitioning: Example
• Entry 𝐴[𝑟] becomes the pivot element 𝑥. Lightly shaded
elements are all in the first partition with values no greater than
𝑥. Heavily shaded elements are in the second partition with
values greater than 𝑥. The unshaded elements have not yet
decided, and the final white element is the pivot 𝑥.
• (a) The initial array and variable settings. None of the elements have
been placed in either of the first two partitions.
• (b) The value 2 is “swapped with itself” and put in the partition of
smaller values.
• (c)–(d) The values 8 and 7 are added to the partition of larger
values.
• (e) The values 1 and 8 are swapped, and the smaller partition grows.
• (f) The values 3 and 7 are swapped, and the smaller partition grows.
• (g)–(h) The larger partition grows to include 5 and 6, and the loop
terminates.
• (i) In lines 7–8, the pivot element is swapped so that it lies between
the two partitions.
12
 Partitioning
• The two cases for one iteration of
procedure Partition.
a) If 𝐴[𝑗] > 𝑥, the only action is to
increment 𝑗 , which maintains the
loop invariant.
b) If 𝐴[𝑗] ≤ 𝑥, index i is incremented,
𝐴[𝑖] and 𝐴[𝑗] are swapped, and then
𝑗 is incremented.

13
Partitioning

14
Partitioning: Animated Illustration

15
 Quicksort: Analysis
• Time complexity:
• Worst case performance: 𝑂(𝑛2 )
• Best case performance: 𝑂(𝑛 log 𝑛)
• Average case performance: 𝑂(𝑛 log 𝑛)

• Space complexity:
• Worst case space complexity: 𝑂(𝑛) total

16
 Summary
Space
Time Complexity
Sorting Complexity
Algorithm Average
Best Case Worst Case Worst Case
Case
Selection Sort Ω(𝑛2 ) Θ(𝑛2 ) 𝑂(𝑛2 ) 𝑂(1)
Bubble Sort Ω(𝑛) Θ(𝑛2 ) 𝑂(𝑛2 ) 𝑂(1)
Insertion Sort Ω(𝑛) Θ(𝑛2 ) 𝑂(𝑛2 ) 𝑂(1)
Merge Sort Ω(𝑛 log 𝑛) Θ(𝑛 log 𝑛) 𝑂(𝑛 log 𝑛) 𝑂(𝑛)
Radix Sort Ω(𝑛𝑑) Θ(𝑛𝑑) 𝑂(𝑛𝑑) 𝑂(𝑛 + 𝑑)
Quicksort Ω(𝑛 log 𝑛) Θ(𝑛 log 𝑛) 𝑂(𝑛2 ) 𝑂(𝑛)
17