CSCI 4041
Discussion Section Notes
mo000007@umn.edu
QuickSort
Divide and Conquer algorithm – same as MergeSort
● Select an element as a pivot element
● Divide/partition the array on the basis of pivot
○ Partition into 2 subarrays s.t A[1…q-1] < A[q] < A[q+1...len(A)]
○ A[q] - pivot element
● Recursively call QuickSort on Left and Right Partition
● Since the subarrays are already sorted, no work is needed to combine them
2
page: 171
3
QuickSort
The example shows how Partition works using the
last element as pivot.
Exercise: Show the Partition operations for [5, 13, 2, 25, 7, 17, 20, 8, 4]
4
5
13
2
25
7
17
20
8
4
2
13
5
25
7
17
20
8
4
i
QuickSort
Exercise: Show the Partition operations for [5, 13, 2, 25, 7, 17, 20, 8, 4]
j pivoti j
5
13
2
25
7
17
20
8
4
2
13
5
25
7
17
20
8
4
ijij
ijij
ijij
5
13
2
25
7
17
20
8
4
2
13
5
25
7
17
20
8
4
2
13
5
25
7
17
20
8
4
2
13
5
25
7
17
20
8
4
2
13
5
25
7
17
20
8
4
2
4
5
25
7
17
20
8
13
ij
5
QuickSort
Step-by-step operation of QuickSort:
2
4
5
25
7
17
20
8
13
5
25
7
17
20
8
13
2
6
How to pick pivot?
Exercise: Write code for QuickSort (page 171) and observe the operation of
Partition for the following arrays:
[5, 8, 4, 7, 1, 3, 2, 6]
[1, 2, 3, 4, 5, 7, 8, 6]
What are the runtime costs for the 2 scenarios?
7
QuickSort in Python
arr = [5, 8, 4, 7, 1, 3, 2, 6] quicksort(arr, 0, len(arr)-1)
arr = [1, 2, 3, 4, 5, 7, 8, 6] quicksort(arr, 0, len(arr)-1)
8
Runtime of QuickSort
The runtime depends on the partitioning. Why? Worst-case (unbalanced partitioning):
Best-case (balanced partitioning):
9
Counting Sort
input range: [0, 5]
eg. ‘3’ should be at index 7
index of B: C[A[i]]
original array:
index of C: A[i]
auxiliary array:
ending index of each element in sorted array
2+0 2+2 4+3 7+0 7+1
decrease the value in C
output array:
10
Counting Sort
𝚯(n+k)≃O(n) page: 195
11
Counting Sort Exercise:
Write code for Counting-Sort (page 195). [Hint: remember to adjust for arrays A and B if the indices start at 0]
Change auxiliary array C so that it contains starting indices instead of ending
indices.
012345
starting index of each element in sorted array
0
2
2
4
7
7
ending index of each element in sorted array
12
Counting Sort: Exercise
ending index of each element in sorted array
starting index of each element in sorted array
13
Bucket Sort
Counting sort - assumes that the input consists of
integers in a small range
Bucket sort - assumes that the input is generated by a random process that distributes elements uniformly and independently over the interval [0, 1)
Bucket sort breaks the data into n equal-sized subintervals, or buckets, and then distributes the n input numbers into the buckets.
14
Bucket Sort
page: 201
15
Bucket Sort
Exercise:
Explain why the worst-case running time for bucket sort is 𝚯(n2).
What simple change to the algorithm preserves its linear average-case running time and makes its worst-case running time O(n lg n).
16
Bucket Sort Exercise:
Explain why the worst-case running time for bucket sort is 𝚯(n2).
If all elements is in the same bucket, the runtime is the same as Insertion sort because we have to sort a single bucket with all elements in it.
What simple change to the algorithm preserves its linear average-case running
time and makes its worst-case running time O(n lg n).
We can use MergeSort instead of Insertion sort so that the worst-case running time will be O(n lg n).
17
Radix Sort
● Sort numbers on their most significant digit
● Sort each of the resulting bins and repeat for next significant digit
red: current unsorted column gray: sorted
18
Radix Sort Exercise:
Illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.
Which of the following sorting algorithms are stable: insertion sort, merge sort, heapsort, and quicksort?
19
Radix Sort Exercise:
Illustrate the operation of RADIX-SORT on the following list of English words:
COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA,
NOW, FOX.
1st iter: SEA, TEA, MOB, TAB, DOG, RUG, DIG, BIG, BAR, EAR, TAR, COW, ROW, NOW, BOX, FOX 2nd iter: TAB, BAR, EAR, TAR, SEA, TEA, DIG, BIG, MOB, DOG, COW, ROW, NOW, BOX, FOX, RUG 3rd iter: BAR, BIG, BOX, COW, DIG, DOG, EAR, FOX, MOB, NOW, ROW, RUG, SEA, TAB, TAR, TEA
Which of the following sorting algorithms are stable: insertion sort, merge sort,
heapsort, and quicksort?
Insertion sort, merge sort - stable Quicksort, heapsort - unstable
20
Reference
Introduction to Algorithms, Third Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein.
21