COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 10-1 : Recursion 3 (Mergesort and Quicksort)
Giulia Alberini, Fall 2020
WHAT ARE WE GOING TO DO IN THIS VIDEO?
Merge sort Quick sort
TIME COMPLEXITY
𝑂 𝑙𝑜𝑔𝑛
convert to binary binary search ……
𝑂𝑛
List operations: findMax, remove
grade school addition
…..
𝑂 𝑛2
insertion/selectio n/bubble sort
grade school multiplication
……
MERGE SORT
MERGE SORT
Merge Sort is a divide and conquer algorithm.
GOAL: Sort an list.
IDEA:
Partition the list into two halves.
Sort each half recursively
Merge the sorted half maintaining the order.
IDEA
8 10 3 11 6 1
mergesort
1 3 6 8 10 11
8 10 3 11 6 1 7 16 2 5 4 13
1 2 3 4 5 6 7 8 10 11 13 16
partition
merge
7 16 2 5 4 13
mergesort
2 4 5 7 13 16
IMPLEMENTATION
mergesort(list){
if (list.size() == 1)
return list
else {
} }
mid = (list.size() – 1) / 2
list1 = list.getElements(0,mid)
list2 = list.getElements(mid+1, list.size()-1) list1 = mergesort(list1)
list2 = mergesort(list2)
return merge(list1, list2)
IMPLEMENTATION
mergesort(list){
else {
if (list.size() == 1)
return list
mid = (list.size() – 1) / 2
list1 = list.getElements(0,mid)
list2 = list.getElements(mid+1, list.size()-1)
list1 = mergesort(list1) list2 = mergesort(list2)
return merge(list1, list2)
} }
Base case
Partition
Recursive sort
Merge
MERGING PRESERVING ORDER
8 10 3 11 6 1
mergesort
1 3 6 8 10 11
8 10 3 11 6 1 7 16 2 5 4 13
1 2 3 4 5 6 7 8 10 11 13 16
partition
merge
7 16 2 5 4 13
mergesort
2 4 5 7 13 16
MERGING PRESERVING ORDER
Iterate through the elements of the two sorted list.
Depending on how they compare decide which element comes first in the merged list.
merge
1 3 6 8 10 11
2 4 5 7 13 16
MERGING PRESERVING ORDER
1 3 6 8 10 11
merge
2 4 5 7 13 16
MERGING PRESERVING ORDER
1
3 6 8 10 11
1
merge
2 4 5 7 13 16
MERGING PRESERVING ORDER
1
3 6 8 10 11
1 2
merge
2
4 5 7 13 16
MERGING PRESERVING ORDER
1 3 6 8 10 11
1 2 3
merge
2
4 5 7 13 16
MERGING PRESERVING ORDER
1 3 6 8 10 11
1 2 3 4
merge
2 4 5 7 13 16
MERGING PRESERVING ORDER
1 3 6 8 10 11
1 2 3 4 5
merge
2 4 5 7 13 16
MERGING PRESERVING ORDER
1 3 6 8 10 11
1 2 3 4 5 6
merge
2 4 5 7 13 16
MERGING PRESERVING ORDER
1 3 6 8 10 11
1 2 3 4 5 6 7
merge
2 4 5 7 13 16
MERGING PRESERVING ORDER
And so on until one list is empty!
1 3 6 8 10 11
1 2 3 4 5 6 7 8 10 11
merge
2 4 5 7 13 16
MERGING PRESERVING ORDER
Then copy the remaining elements!
1 3 6 8 10 11
1 2 3 4 5 6 7 8 10 11 13 16
merge
2 4 5 7 13 16
IMPLEMENTATION OF MERGE
merge(list1, list2){
list = …initialize with empty list…
while (!list1.isEmpty() && !list2.isEmpty()){
if (list1.get(0) < list2.get(0)) list.addlast(list1.removeFirst())
else
list.addlast(list2.removeFirst())
}
while (!list1.isEmpty())
list.addlast(list1.removeFirst()) while (!list2.isEmpty())
list.addlast( list2.removeFirst()) return list
}
IMPLEMENTATION OF MERGE
merge(list1, list2){
list = ...initialize with empty list...
while (!list1.isEmpty() && !list2.isEmpty()){
if (list1.get(0) < list2.get(0)) list.addlast(list1.removeFirst())
else
list.addlast(list2.removeFirst())
}
while (!list1.isEmpty())
list.addlast(list1.removeFirst()) while (!list2.isEmpty())
list.addlast( list2.removeFirst()) return list
}
Pick elements to add until one of the two lists is empty
Then add the remaining elements
1) Partitions into list and call mergesort until base case is reached.
EXAMPLE OF EXECUTION
mergesort(list){
if (list.size() == 1)
return list
else {
} }
mid = (list.size() - 1) / 2
list1 = list.getElements(0,mid)
list2 = list.getElements(mid+1, list.size()-1) list1 = mergesort(list1)
list2 = mergesort(list2)
return merge(list1, list2)
8 10 3 11 6 1 7 16 2 5 4 13
1) Partitions into list and call mergesort until base case is reached.
EXAMPLE OF EXECUTION
8 10 3 11 6 1 7 16 2 5 4 13
8 10 3 11 6 1
list1
7 16 2 5 4 13
list2
1) Partitions into list and call mergesort until base case is reached.
EXAMPLE OF EXECUTION
list1
list2
8 10 3 11 6 1 7 16 2 5 4 13
8 10 3
8 10 3 11 6 1
11 6 1
7 16 2 5 4 13
1) Partitions into list and call mergesort until base case is reached.
EXAMPLE OF EXECUTION
list1 list2
8 10
3
8 10 3
8 10 3 11 6 1
8 10 3 11 6 1 7 16 2 5 4 13
11 6 1
7 16 2 5 4 13
EXAMPLE OF EXECUTION
1) Partitions into list and call mergesort until base case is reached.
8 10
3
8 10 3 11 6 1 7 16 2 5 4 13
8
list1 list2
8 10 3
8 10 3 11 6 1
10
11 6 1
7 16 2 5 4 13
EXAMPLE OF EXECUTION
list2
list1
Then start to merge!
8 10
3
8 10 3 11 6 1 7 16 2 5 4 13
8
8 10
8 10 3
8 10 3 11 6 1
10
11 6 1
7 16 2 5 4 13
EXAMPLE OF EXECUTION
Then start to merge!
8
8 10
3
8 10
3
8 10
8 10 3
8 10 3 11 6 1
8 10 3 11 6 1 7 16 2 5 4 13
10
list1
11 6 1
list2
7 16 2 5 4 13
EXAMPLE OF EXECUTION
Then start to merge!
8 10
3
11 6
1
8 10 3 11 6 1 7 16 2 5 4 13
8 10 3 11 6 1
8 10 3
8
8 10
3
8 10
10
list1
list2
11
6
6 11
11 6 1
1
6 11
7 16 2 5 4 13
EXAMPLE OF EXECUTION
Then start to merge!
8
8 10
3
11 6
1
8 10
3
8 10
8 10 3
8 10 3 11 6 1 7 16 2 5 4 13
8 10 3 11 6 1
1 3 6 8 10 11
10
list1
11
6
6 11
11 6 1
1
6 11
7 16 2 5 4 13
list2
EXAMPLE OF EXECUTION
Then start to merge!
5
4 13
8 10
3
11 6
1
7 16
2
8
6
8 10
3
8 10
8 10 3
8 10 3 11 6 1 7 16 2 5 4 13
8 10 3 11 6 1
11
1 3 6 8 10 11
10
list1
6 11
11 6 1
1
6 11
7
7 16
7 16 2 5 4 13
2
7 16
7 16 2
2 4 5 7 13 16
16
list2
5 4
13
5
4 5
4
5 13
4
EXAMPLE OF EXECUTION
Then start to merge!
8
8 10
3
8 10
8 10 3
8 10 3 11 6 1
1 3 6 8 10 11
8 10 3 11 6 1 7 16 2 5 4 13
1 2 3 4 5 6 7 8 10 11 13 16
10
11
6 11
11 6 1
1
6 11
5
4 13
8 10
3
11 6
1
7 16
2
6
7
7 16
7 16 2 5 4 13
2
7 16
7 16 2
2 4 5 7 13 16
16
5 4
13
5
4 5
4
5 13
4
Q: How many operations are required to mergesort a list of size 𝑛 ?
A: 𝑂(𝑛𝑙𝑜𝑔2𝑛)
This will become more clear in the next video when we discuss recurrences.
𝑛
𝑛
𝑙𝑜𝑔2 𝑛
𝑙𝑜𝑔2 𝑛
COMPLEXITY
𝑛 𝑙𝑜𝑔2 𝑛 is much closer to 𝑛 than to 𝑛2
𝑙𝑜𝑔2 𝑛
𝑛
𝒏 𝒍𝒐𝒈𝟐 𝒏
𝑛2
10 20 30
210 ≈ 103 220 ≈ 106 230 ≈ 109
𝟏𝟎𝟒
~𝟏𝟎𝟕 ~𝟏𝟎𝟏𝟎
106 1012 1018
COMPLEXITY
𝑛 𝑙𝑜𝑔2 𝑛 is much closer to 𝑛 than to 𝑛2
𝑙𝑜𝑔2 𝑛
𝑛
𝒏 𝒍𝒐𝒈𝟐 𝒏
𝑛2
10 20 30
210 ≈ 103 220 ≈ 106 230 ≈ 109
𝟏𝟎𝟒
~𝟏𝟎𝟕 ~𝟏𝟎𝟏𝟎
106 1012 1018
milliseconds seconds minutes/hours centuries
QUICK SORT
QUICK SORT
Quick Sort is a divide and conquer algorithm.
GOAL: Sort a list.
IDEA:
Pick an element of the array (the pivot).
Partition the list moving the pivot to its correct position making sure that all the lower elements are on its left and all the larger elements are on its right.
Sort the left part AND the right part of the list recursively. Keep doing it until there’s nothing left to sort.
IDEA
IDEA:
Pick an element of the array (the pivot).
Move the pivot to its correct position making sure that all the smaller elements are on its left and all the larger elements are on its right.
Sort the left part AND the right part
Keep doing it until there’s nothing left to sort.
This is the crucial process of the algorithm!
Recursive Step
Base case
IDEA
3 6 1 7 2 5 4 8 10 11 16 13
quicksort
1 2 3 4 5 6 7 8 10 11 13 16
10 3 11 6 1 7 16 2 5 4 13 8
partition
quicksort
pivot
THE PIVOT
Different versions of Quick Sort pick the pivot in different ways: Always pick the first element as the pivot
Always pick the last element as the pivot
Pick a random element
Pick the median as pivot
THE PIVOT
Different versions of Quick Sort pick the pivot in different ways: Always pick the first element as the pivot
Always pick the last element as the pivot
Pick a random element
Pick the median as pivot
QUICK SORT EXAMPLE
5
1
4
2
3
QUICK SORT EXAMPLE
1. Pick the pivot.
5
1
4
2
3
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
5
1
4
2
3
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
5
1
4
2
3
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
5
1
4
2
3
compare:
5<3 falsedo nothing!
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
5
1
4
2
3
compare: 1<3 true
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
5
1
4
2
3
compare:
1<3 truemove the wall
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
swap
1
5
4
2
3
compare:
1<3 truemove the element
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
1
5
4
2
3
compare:
4<3 falsedo nothing
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
1
5
4
2
3
compare: 2<3 true
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
1
5
4
2
3
compare:
2<3 truemove wall
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
swap
1
2
4
5
3
compare:
2<3 truemove element
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
1
2
3
5
4
4.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
Move the pivot next to the wall.
swap
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
left part
right part
1
2
3
5
4
4. 5.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
Move the pivot next to the wall.
Use Quick sort on left part and then on the right part
QUICK SORT EXAMPLE
1. Pick the pivot.
1
2
354
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
1
2
354
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
1
2
354
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
1
2
354
compare: 1<2 true
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
1
2
354
compare:
1<2 truemove wall
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
1
2
354
compare:
1<2 trueelement already in position.
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
1
2
354
4. 5.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
Move the pivot next to the wall.
Use Quick Sort on left part and then on the right part.
QUICK SORT EXAMPLE
In this case the left part and the right part are base cases. The left part has 1 element already sorted!
The right part is empty sorted!
1
2
354
QUICK SORT EXAMPLE
It is left to sort the part of the list to the right of the first pivot.
right part
1
2
3
5
4
QUICK SORT EXAMPLE
1. Pick the pivot.
123
5
4
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
123
5
4
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
compare:
5<4 falsedo nothing!
123
5
4
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
Otherwise, do nothing.
4. Move the pivot next to the wall.
swap
123
4
5
QUICK SORT EXAMPLE
1. Pick the pivot.
2. Set the wall on the left
3. Go through all the elements of the list that are not the pivot.
If the element is smaller than the
pivot, move the wall right by 1, and place the element just behind the wall.
123
Otherwise, do nothing.
4. Move the pivot next to the wall.
5. Use Quick Sort on left part and then on the right part.
4
5
QUICK SORT EXAMPLE
Once again, both the left part and the right part are base cases.
123
4
5
QUICK SORT EXAMPLE
Once again, both the left part and the right part are base cases. The array is sorted
123
4
5
QUICK SORT EXAMPLE
Once again, both the left part and the right part are base cases. The array is sorted
The original array is sorted!
1
2
3
4
5
QUICK SORT – IMPLEMENTATION
What do we need to implement this algorithm? A method that swaps two elements
A way to refer to parts of the list
A method that places the pivot in its correct position and moves the elements around so that all the lower elements are on the left, and all the larger elements are on the right. Call it placeAndDivide
A method that implements the Quick Sort, that is: Pick a pivot
placeAndDivide
quickSort left part
quickSort right part
PARTS OF THE LIST
What can we use to denote a part of the list?
We can use the same idea used from binary search keep track of the left and right index denoting where the part begins and ends.
Consider for example the list {5,3,6,1,2}. Then:
The indices 0 and 4 denote the entire list.
The indices 0 and 2 denote the part of the list with the 3 left most elements.
The indices 1 and 3 denote the part of the list with the 3 middle elements.
quickSort – PSEUDO CODE
quickSort(list, leftIndex, rightIndex) {
// Base case:
if(leftIndex >= rigthIndex) {
return; // done!
}
}
quickSort – PSEUDO CODE
quickSort(list, leftIndex, rightIndex) {
// Base case:
if(leftIndex >= rigthIndex) {
return; // done!
} else { // recursive step: iplaceAndDivide(list, leftIndex, rightIndex) // i = index where the pivot is placed quickSort(list, leftIndex, i-1)
quickSort(list, i+1, rightIndex)
} }
placeAndDivide – PSEUDO CODE
placeAndDivide(list, leftIndex, rightIndex) {
// pick the right most element
pivot list.get(rigthIndex)
}
placeAndDivide – PSEUDO CODE
placeAndDivide(list, leftIndex, rightIndex) {
}
// pick the right most element
pivot list.get(rigthIndex)
// place the wall to the left
wallleftIndex -1
placeAndDivide – PSEUDO CODE
placeAndDivide(list, leftIndex, rightIndex) {
// pick the right most element
pivot list.get(rigthIndex) // place the wall to the left
wallleftIndex -1
// go through all elements and compare them to the pivot
for(int i=leftIndex; i< rigthIndex; i++) {
}
}
placeAndDivide – PSEUDO CODE
placeAndDivide(list, leftIndex, rightIndex) {
// pick the right most element
pivot list.get(rigthIndex) // place the wall to the left
wallleftIndex -1
// go through all elements and compare them to the pivot
for(int i=leftIndex; i< rigthIndex; i++) {
if(list.get(i)