CS计算机代考程序代写 algorithm COMP 250

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 falsedo 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 truemove 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 truemove 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 falsedo 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 truemove 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 truemove 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 truemove 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 trueelement 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 falsedo 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: iplaceAndDivide(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
wallleftIndex -1

placeAndDivide – PSEUDO CODE
placeAndDivide(list, leftIndex, rightIndex) {
// pick the right most element
pivot  list.get(rigthIndex) // place the wall to the left
wallleftIndex -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 wallleftIndex -1 // go through all elements and compare them to the pivot for(int i=leftIndex; i< rigthIndex; i++) { if(list.get(i)