# CS计算机代考程序代写 algorithm python CSCI 4041

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