Sorting II - Advanced
1
Learning Objectives
● Understand the basic principles and algorithms behind merge sort and quicksort.
● Compare and contrast the time complexity of merge sort, quick sort, bucket sort,
and cyclic sort, including best-case, worst-case, and average-case scenarios.
● Identify the strengths and weaknesses of each sorting algorithm in terms of stability,
adaptability to different data distributions, and ease of implementation.
● Explore potential optimizations and variations of merge sort, quick sort, bucket sort,
and cyclic sort, such as parallelization, hybrid algorithms, and memory
management techniques.
2
Lecture Flow
1) Pre-requisites
2) Revision
3) Part I
● Merge Sort
● Bucket Sort
4) Part II
● Quick Sort
● Cyclic Sort
5) Practice Questions
6) Resources
7) Quote of the Day
3
Pre-requisites
● Sorting - Basics
● Asymptotic Analysis
● Arrays
● Willingness to learn
4
Revision
5
Bubble Sort
6
Time & Space Complexity
Time complexity ? ____________
Space complexity ?____________
7
Time & Space Complexity
Time complexity: O(n²)
Space complexity: O(1)
8
Selection Sort
9
Time & Space Complexity
Time complexity ? ____________
Space complexity ?____________
10
Time & Space Complexity
Time complexity: O(n²)
Space complexity: O(1)
11
Insertion Sort
12
Time & Space Complexity
Worst case ? ____________
Best case ? ____________
Average case ? ____________
13
Time & Space Complexity
Time complexity: O(n²)
Space complexity: O(1)
Worst case __O(n²)___
Best case __O(n)___
Average case __O(n²)___
14
Counting Sort
15
Time complexity
Worst case ? ___________
Best case ? ___________
Average case ? ___________
16
Time complexity
The time complexity of counting sort
Worst case __O(n+k)___
algorithm is O(n+k) where n is the
Best case __O(n+k)___
number of elements in the array and k
Average case __O(n+k)___
is the range of the elements.
Note: Counting sort is most efficient if the range of input values is not greater
than the number of values to be sorted.
Time to get efficient !
18
Part I
19
Merge Sort
20
Merge Sort
A sorting algorithm that
works by dividing an array
into smaller subarrays,
sorting each subarray, and
then merging the sorted
subarrays back together to
form the final sorted array.
visualization from: VisuAlgo
21
Merge Sort
● Divide the array into two halves,
● Sort each half, and then
● Merge the sorted halves back
together.
22
Q: Can you guess the next set of moves in the following dance ?
23
Divide
● Divide the array into two
Conquer
Divide and Conquer
● Sort both halves with merge
sort
● Base case?
Combine
● Merge the two sorted halves
24
Practice
25
Can you implement the function merge ?
Implement Here
26
Q: Is Merge Sort a Stable Sorting Algorithm ?
?
27
Q: What do you think is the time complexity for the aforementioned
sorting Algorithm?
?
28
Time & Space Complexity
Worst case ________
Best case ________
Average case ________
29
Time & Space Complexity
Time complexity: O(nlogn)
Space complexity: O(n)
Worst case __O(nlogn)___
Best case __O(nlogn)___
Average case __O(nlogn)___
Stable YES
In-place NO
30
Pair Programming
Question 1
31
Bucket Sort
32
Bucket Sort
A sorting algorithm that works by
distributing the elements of an
array into a number of buckets,
and then sorting each bucket
individually. It is an efficient
algorithm for sorting elements
that are evenly distributed across
a range of values.
33
Bucket Sort
Here's how it works:
1. Determine the range of values in the array to be sorted.
2. Divide the range into a set of buckets.
3. For each element in the array, determine which bucket it belongs to and insert it
into that bucket.
4. Sort each bucket individually using another sorting algorithm (usually insertion sort).
5. Concatenate the sorted buckets to obtain the final sorted array.
34
Bucket Sort
Problem:
Sort a large set of floating point numbers which are in range from 0.0 to 1.0
and are uniformly distributed across the range. How do we sort the numbers
efficiently?
35
Bucket Sort
Approach:
bucket_sort(arr[], n)
1) Create n empty buckets (Or lists).
2) Do the following for every array element arr[i].
a) Insert arr[i] into bucket [n*array[i]]
3) Sort individual buckets using insertion sort.
4) Concatenate all sorted buckets.
36
Bucket Sort
37
Visualization Link
38
Can you implement the function bucket_sort ?
Implement Here
39
Time & Space Complexity
Worst case ? ____________
Best case ? ____________
Average case ? ____________
40
Time & Space Complexity
Time complexity: O(n²)
Space complexity: O(n + k)
Worst case __ O(n²)__
Best case __ O(n)___
Average case _O(n + k)
41
Pair Programming
Question 2
42
Practice Problems
Sort List
Masha and Beautiful Tree
Count of Smaller Numbers After Self
Number of Pairs Satisfying Inequality
Create Sorted Array through Instructions
43
Quote of the Day
"The first step in crafting a life you want is to get
rid of everything you don't."
- Joshua Becker
44
