Sorting II - Advanced
1
Part II
2
Quick Sort
3
Quick Sort
Similar to merge sort,
Quicksort follows the
divide-and-conquer
approach that was first
introduced.
visualization from: VisuAlgo
4
Quick Sort
if length of array is less than or equal to 1:
return array
else:
select an element from the array to use as a pivot
partition the elements of the array into two sub-arrays:
- elements less than or equal to pivot
- elements greater than pivot
quicksort the sub-array of elements less than or equal to pivot
quicksort the sub-array of elements greater than pivot
concatenate the sorted sub-arrays and return the result
5
Quick Sort
Example input
R
P: pivot
W: write index
R: read index
[4, 2, 6, 8, 1, 5, 9]
P W
6
Quick Sort
Example input
R
P: pivot
W: write index
R: read index
[4, 2, 6, 8, 1, 5, 9]
P W
7
Quick Sort
Example input
R
P: pivot
W: write index
R: read index
[4, 2, 6, 8, 1, 5, 9]
P W
8
Quick Sort
Example input
R
P: pivot
W: write index
R: read index
[4, 2, 6, 8, 1, 5, 9]
P W
9
Quick Sort
Example input
R
P: pivot
W: write index
R: read index
[4, 2, 1, 8, 6, 5, 9]
P W
10
Quick Sort
Example input
R
P: pivot
W: write index
R: read index
[4, 2, 1, 8, 6, 5, 9]
P W
11
Quick Sort
Example input
R
P: pivot
W: write index
R: read index
[4, 2, 1, 8, 6, 5, 9]
P W
12
Quick Sort
Example input
R
P: pivot
W: write index
R: read index
[4, 2, 1, 8, 6, 5, 9]
P W
13
Quick Sort
Example input
P: pivot
W: write index
R: read index
[1, 2, 4, 8, 6, 5, 9]
P W
14
Quick Sort
Example input
[1, 2, 4, 8, 6, 5, 9]
quicksort ([1, 2]) quicksort ([8, 6, 5, 9])
Combine the answer
15
Visualization Link
16
Can you implement the function partition ?
Implement Here
17
Implementation
def partition(nums, left, right) -> int:
"""
Picks the first element left as a pivot
and returns the index of pivot value in the sorted array
"""
pivot_val = nums[left]
store_index = left + 1
for j in range(store_index, right + 1):
if nums[j] < pivot_val:
nums[store_index], nums[j] = nums[j], nums[store_index]
store_index += 1
nums[store_index - 1], nums[left] = nums[left], nums[store_index - 1]
return store_index - 1
18
Implementation
def quick_sort(nums, left, right):
# if length of array is less than or equal to 1
if left >= right:
return
pivot_index = partition(nums, left, right)
quick_sort(nums, left, pivot_index - 1)
quick_sort(nums, pivot_index + 1, right)
19
Q: What do you think is the time complexity for the aforementioned
sorting Algorithm?
?
20
Time & Space Complexity
Worst case ? ____________
Best case ? ____________
Average case ? ____________
21
Q: what kind of input would result in the worst case?
?
22
What happens in the worst case?
Sorted
array [1, 2, 3, 4, 5]
[1] [2, 3, 4, 5] N: depth
[2] [3, 4, 5]
[3] [4, 5]
[4] [5]
23
Q: Can we do better ? How ?
?
24
How can we avoid the worst case?
● Pick pivot randomly
● Median value of arr[0], arr[len//2] and arr[len - 1]
25
Modified Implementation
def partition(nums, left, right) -> int:
# Select a random pivot_index and move the pivot in to the first
element
pivot_index = random.randint(left, right)
nums[pivot_index], nums[left] = nums[left], nums[pivot_index]
pivot_val = nums[left]
store_index = left + 1
for j in range(store_index, right + 1):
if nums[j] < pivot_val:
nums[store_index], nums[j] = nums[j], nums[store_index]
store_index += 1
nums[store_index - 1], nums[left] = nums[left], nums[store_index - 1]
return store_index - 1
26
Time & Space Complexity
Time complexity: O(n²)
Space complexity: O(1)
Worst case __O(n²)______
Best case __O(n log n)_
Average case __O(n log n)_
Stable NO
In-place YES
27
Cycle/ Cyclic Sort
28
Cycle Sort
It is known that all comparison-based sorting algorithms have a lower bound time
complexity of Ω(N log N).
However, we can achieve faster sorting algorithm — i.e., in O(N) — if
certain assumptions of the input array exist
29
Cycle Sort
Problem:
You are given an array of size n that only includes numbers in the range [1, n], sort
the array in a single pass in O(N) runtime.
0 1 2 3 4
[3, 5, 2, 1, 4]
30
Cycle Sort
Approach:
Let’s imagine the array was already sorted, what would be the relationship
between the values and the indices ?
0 1 2 3 4
[1, 2, 3, 4, 5]
31
Cycle Sort
Approach:
Index = value - 1
0 1 2 3 4
[1, 2, 3, 4, 5]
32
Cycle Sort
Approach:
This means, we can use the values to know where exactly in the array they should
be placed.
0 1 2 3 4
[3, 5, 2, 1, 4]
|
Where should 3 be placed at ?
33
Cycle Sort
This means, we can use the values to know where exactly in the array they should
be placed.
0 1 2 3 4
[3, 5, 2, 1, 4]
|
The value 3 should be placed at index 2. So we swap
34
Cycle Sort
This means, we can use the values to know where exactly in the array they should
be placed.
0 1 2 3 4
[2, 5, 3, 1, 4]
|
The value 2 is not in the correct place either, where should it be ?
35
Cycle Sort
This means, we can use the values to know where exactly in the array they should
be placed.
0 1 2 3 4
[2, 5, 3, 1, 4]
|
Swap
36
Cycle Sort
This means, we can use the values to know where exactly in the array they should
be placed.
0 1 2 3 4
[5, 2, 3, 1, 4]
|
Where should 5 be ?
37
Cycle Sort
This means, we can use the values to know where exactly in the array they should
be placed.
0 1 2 3 4
[5, 2, 3, 1, 4]
|
Swap
38
Cycle Sort
This means, we can use the values to know where exactly in the array they should
be placed.
0 1 2 3 4
[4, 2, 3, 1, 5]
|
Where should 4 be ?
39
Cycle Sort
This means, we can use the values to know where exactly in the array they should
be placed.
0 1 2 3 4
[4, 2, 3, 1, 5]
|
Swap
40
Cycle Sort
This means, we can use the values to know where exactly in the array they should
be placed.
0 1 2 3 4
[1, 2, 3, 4, 5]
|
Where should 1 be ?
41
Cycle Sort
This means, we can use the values to know where exactly in the array they should
be placed.
0 1 2 3 4
[1, 2, 3, 4, 5]
|
It is finally in its correct position, so we move our pointer
42
Cycle Sort
This means, we can use the values to know where exactly in the array they should
be placed.
0 1 2 3 4
[1, 2, 3, 4, 5]
|
Where should 2 be ?
43
Cycle Sort
This means, we can use the values to know where exactly in the array they should
be placed.
0 1 2 3 4
[1, 2, 3, 4, 5]
|
Where should 3 be ?
44
Cycle Sort
This means, we can use the values to know where exactly in the array they should
be placed.
0 1 2 3 4
[1, 2, 3, 4, 5]
|
Where should 4 be ?
45
Cycle Sort
This means, we can use the values to know where exactly in the array they should
be placed.
0 1 2 3 4
[1, 2, 3, 4, 5]
|
Where should 5 be ?
46
Cycle Sort
This means, we can use the values to know where exactly in the array they should
be placed.
0 1 2 3 4
[1, 2, 3, 4, 5]
|
Array is sorted.
47
Can you implement the function cycleSort ?
Implement Here
48
Cycle Sort
Implementation
def cycleSort(arr):
n = len(arr)
i = 0
while i < n:
correct_position = arr[i] - 1
if correct_position != i:
arr[correct_position], arr[i] = arr[i], arr[correct_position]
else:
i += 1
return arr
49
Q: What do you think is the time complexity for the aforementioned
sorting Algorithm?
?
50
Time & Space Complexity
Cycle Sort
Worst case ________
Best case ________
Average case ________
51
Time & Space Complexity
Cycle Sort
Worst case ___O(N)_____
Best case ___O(N)_____
Average case ___O(N)____
Only applies to a constrained range
of values
52
Further Reading
● There are also other popular sorting algorithms such as Radix Sort, Binary
Insertion Sort…
● Feel free to explore and share with your teammates.
53
Pair Programming
54
Practice Problems
Missing Number
Find All Numbers Disappeared in an Array
Find all duplicates in an array
Set Mismatch
Find the Duplicate Number
FIrst Missing Positive
Kth Largest Element in an Array
55
Resources
● Visualgo.com: is great for visualizing sorting algorithms in general
● Chatgpt: is great at re-writing and generating pseudocode
● Geeks for Geeks (GFG): has clear explanations
● A2SV Slides repo: good reference for which topics to cover and
good quotes.
● Leetcode learn card Recursion II: good reference for merge sort,
quick sort, and other recursion concepts
● Leetcode learn card Sorting: good reference for bucket sort, and
other sorting algorithms like radix sort.
56
Quote of the Day
"The first law of success is concentration — to bend all the
energies to one point, and to go directly to that point,
looking neither to the right nor to the left."
- William Matthews
57
