ds04efficientsorting.pdf

CS121 Data Structures C Efficient Sorting Monika Stepanyan [email protected] Fall 2024 Sorting in N-Log-N And Linear Time Sorting problem: start with an unordered array of elements and rearrange them into nondecreasing order I Merge Sort I Quick Sort I B...

CS121 Data Structures C Efficient Sorting Monika Stepanyan [email protected] Fall 2024 Sorting in N-Log-N And Linear Time Sorting problem: start with an unordered array of elements and rearrange them into nondecreasing order I Merge Sort I Quick Sort I Bucket Sort I Radix Sort Heap Sort will be introduced later when we discuss heaps. Divide and Conquer Divide and conquer is an algorithmic design pattern that consists of the following three steps: 1. Divide: divide the input data S into two or more disjoint subsets S1 , S2 ,... 2. Conquer: solve the subproblems recursively 3. Combine: combine the solutions for S1 , S2 ,... , into a solution for S The base case for the recursion are subproblems of constant size Examples we have seen? Merge Sort To sort a sequence S with n elements, merge sort does: 1. Divide: If |S| ≤ 1, return S. Otherwise, partition S into S1 with b n2 c elements, and S2 with d n2 e elements. 2. Conquer: Recursively sort sequences S1 and S2. 3. Combine: Merge the sorted sequences S1 and S2 into a unique sorted sequence. Reminder: b3.14c = 3 and d3.14e = 4. Merge Sort Tree An execution of merge sort is depicted by a binary tree I each node represents a recursive call of merge sort and stores I unsorted sequence before the execution and its partition I sorted sequence at the end of the execution I the root is the initial call I the leaves are calls on subsequences of size 0 or 1 7 29 4 2 4 7 9 72 2 7 94 4 9 77 22 99 44 The merge sort tree associated with an execution of merge sort on a sequence of size n has height dlog ne Merge Sort: Illustration I Partition 7 2 9 43 8 6 1 1 2 3 4 6 7 8 9 7 2 9 4 2 4 7 9 3 8 6 1 1 3 8 6 7 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6 77 22 99 44 33 88 66 11 Merge Sort: Illustration II Recursive call, partition 7 2 9 43 8 6 1 1 2 3 4 6 7 8 9 7 29 4 2 4 7 9 3 8 6 1 1 3 8 6 7 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6 77 22 99 44 33 88 66 11 Merge Sort: Illustration III Recursive call, partition 7 2 9 43 8 6 1 1 2 3 4 6 7 8 9 7 29 4 2 4 7 9 3 8 6 1 1 3 8 6 722 7 9 4 4 9 3 8 3 8 6 1 1 6 77 22 99 44 33 88 66 11 Merge Sort: Illustration IV Recursive call, base case 7 2 9 43 8 6 1 1 2 3 4 6 7 8 9 7 29 4 2 4 7 9 3 8 6 1 1 3 8 6 722 7 9 4 4 9 3 8 3 8 6 1 1 6 77 22 99 44 33 88 66 11 Merge Sort: Illustration V Recursive call, base case 7 2 9 43 8 6 1 1 2 3 4 6 7 8 9 7 29 4 2 4 7 9 3 8 6 1 1 3 8 6 722 7 9 4 4 9 3 8 3 8 6 1 1 6 77 22 99 44 33 88 66 11 Merge Sort: Illustration VI Merge 7 2 9 43 8 6 1 1 2 3 4 6 7 8 9 7 29 4 2 4 7 9 3 8 6 1 1 3 8 6 722 7 9 4 4 9 3 8 3 8 6 1 1 6 77 22 99 44 33 88 66 11 Merge Sort: Illustration VII Recursive call, …, base case, merge 7 2 9 43 8 6 1 1 2 3 4 6 7 8 9 7 29 4 2 4 7 9 3 8 6 1 1 3 8 6 722 7 9 4 4 9 3 8 3 8 6 1 1 6 77 22 99 44 33 88 66 11 Merge Sort: Illustration VIII Merge 7 2 9 43 8 6 1 1 2 3 4 6 7 8 9 7 29 4 2 4 7 9 3 8 6 1 1 3 8 6 722 7 9 4 4 9 3 8 3 8 6 1 1 6 77 22 99 44 33 88 66 11 Merge Sort: Illustration IX Recursive call, …, merge, merge 7 2 9 43 8 6 1 1 2 3 4 6 7 8 9 7 29 4 2 4 7 9 3 8 6 1 1 3 6 8 722 7 9 4 4 9 3 8 3 8 6 1 1 6 77 22 99 44 33 88 66 11 Merge Sort: Illustration X Merge 7 2 9 43 8 6 1 1 2 3 4 6 7 8 9 7 29 4 2 4 7 9 3 8 6 1 1 3 6 8 722 7 9 4 4 9 3 8 3 8 6 1 1 6 77 22 99 44 33 88 66 11 Merge Sort: An Implementation 1 2 public static void mergeSort(int[ ] S) { 3 int n = S.length; 4 if (n < 2) return; // array is trivially sorted 5 // divide 6 int mid = n/2; 7 int[ ] S1 = Arrays.copyOfRange(S, 0, mid); // copy of first half 8 int[ ] S2 = Arrays.copyOfRange(S, mid, n); // copy of second half 9 // conquer (with recursion) 10 mergeSort(S1); // sort copy of first half 11 mergeSort(S2); // sort copy of second half 12 // merge results 13 merge(S1, S2, S); // merge sorted halves back into original 14 } 15 16 public static void merge(int[ ] S1, int[ ] S2, int[ ] S) { 17 int i = 0, j = 0; 18 while (i + j < S.length) { 19 if (j == S2.length || (i < S1.length && S1[i] < S2[j])) 20 S[i+j] = S1[i++]; // copy ith element of S1 and increment i 21 else 22 S[i+j] = S2[j++]; // copy jth element of S2 and increment j 23 } 24 } Running Time of Merge Sort The method merge runs in O(n1 + n2 ), where n1 is the length of S1 and n2 is the length of S2. I O(1) for each pass of the while loop I number of iterations is n1 + n2 The height h of the merge sort tree is O(log n). I at each recursive call we divide in half the sequence The overall amount of work done at the nodes of depth i is O(n). I we partition and merge 2i sequences of size n/2i Thus, the total running time of merge-sort is O(n log n) depth #seqs size 0 1 n 1 2 n/2 i 2i n/2i … … … Quick Sort To sort a sequence S with n elements, quick sort does: x 1. Divide: If |S| ≤ 1, return S. Otherwise, select element x (called pivot, commonly the last element in S) and partition S into x I L elements less than x I E elements equal to x I G elements greater than x L E G 2. Conquer: Recursively sort sequences L and G 3. Combine: Join L, E and G x Quick Sort Tree An execution of quick sort is depicted by a binary tree I each node represents a recursive call of quick sort and stores I unsorted sequence before the execution and its pivot I sorted sequence at the end of the execution I the root is the initial call I the leaves are calls on subsequences of size 0 or 1 7 4 9 6 2 2 4 6 7 9 4 2 2 4 7 9 7 9 22 99 Quick Sort: Illustration I Pivot selection 7 2 9 4 3 7 6 1 1 2 3 4 6 7 8 9 7 2 9 4 2 4 7 9 3 8 6 1 1 3 8 6 22 9 4 4 9 33 88 99 44 Quick Sort: Illustration II Partition, recursive call, pivot selection 7 2 9 4 3 7 6 1 1 2 3 4 6 7 8 9 2 4 3 1 2 4 7 9 3 8 6 1 1 3 8 6 22 9 4 4 9 33 88 99 44 Quick Sort: Illustration III Partition, recursive call, base case 7 2 9 4 3 7 6 1 1 2 3 4 6 7 8 9 2 4 3 1 2 4 7 3 8 6 1 1 3 8 6 11 9 4 4 9 33 88 99 44 Quick Sort: Illustration IV Recursive call, …, base case, join 7 2 9 4 3 7 6 1 1 2 3 4 6 7 8 9 2 4 3 1 1 2 3 4 3 8 6 1 1 3 8 6 11 4 3 3 4 33 88 99 44 Quick Sort: Illustration V Recursive call, pivot selection 7 2 9 4 3 7 6 1 1 2 3 4 6 7 8 9 2 4 3 1 1 2 3 4 7 9 7 1 1 3 8 6 11 4 3 3 4 88 99 99 44 Quick Sort: Illustration VI Partition, …, recursive call, base case 7 2 9 4 3 7 6 1 1 2 3 4 6 7 8 9 2 4 3 1 1 2 3 4 7 9 7 1 1 3 8 6 11 4 3 3 4 88 99 99 44 Quick Sort: Illustration VII Join, join 7 2 9 4 3 7 6 1 1 2 3 4 6 7 7 9 2 4 3 1 1 2 3 4 7 9 7 17 7 9 11 4 3 3 4 88 99 99 44 Quick Sort: An Implementation 1 2 public static void quickSort(int[ ] S) { 3 int n = S.length; 4 if (n < 2) return; // array is trivially sorted 5 // divide 6 int pivot = S[n-1]; // using last as arbitrary pivot 7 int m = 0, k = n; 8 int[ ] temp = new int[n]; 9 for (int i = 0; i < n - 1; i++) // divide original into L, E, and G 10 if (S[i] < pivot) // element is less than pivot 11 temp[m++] = S[i]; 12 else if (S[i] > pivot) // element is greater than pivot 13 temp[--k] = S[i]; 14 int[ ] L = Arrays.copyOfRange(temp, 0, m); 15 int[ ] E = new int[k - m]; 16 Arrays.fill(E, pivot); 17 int[ ] G = Arrays.copyOfRange(temp, k, n); 18 // conquer (with recursion) 19 quickSort(L); // sort elements less than pivot 20 quickSort(G); // sort elements greater than pivot 21 // concatenate results 22 System.arraycopy(L, 0, S, 0, m); 23 System.arraycopy(E, 0, S, m, k - m); 24 System.arraycopy(G, 0, S, k, n - k); 25 } Worst-Case Running Time of Quick Sort The worst case for quick sort occurs when the pivot is the unique minimum or maximum element One of L and G has size n − 1 and the other has size 0 The running time is proportional to the sum n + (n − 1) + · · · + 2 + 1 Thus, the worst-case running time of quick sort is O(n2 ) depth time 0 n 1 n−1 … … … n−1 1 Expected Running Time of Quick Sort The best case for quick sort occurs when subsequences L and G have roughly the same size In that case, the tree has height O(log n) and therefore quick sort runs in O(n log n) A variation of quick sort, called randomized quick sort picks pivots at random. The expected running time of randomized quick sort on a sequence S of size n is O(n log n) In-Place Quick Sort An algorithm is in-place if it uses only a small amount of memory in addition to that needed for the original input Quick sort can be adapted to be in-place Perform the partition using two indices to split S into two subarrays Repeat until j and k cross: I Scan j to the right until finding an element ≥ x. I Scan k to the left until finding an element ≤ x. I Swap elements at indices j and k In-Place Quick Sort: An Implementation 1 2 public static void quickSortInPlace(int[ ] S, int a, int b) { 3 if (a >= b) return; // subarray is trivially sorted 4 int left = a; 5 int right = b - 1; 6 int pivot = S[b]; // using last as arbitrary pivot 7 int temp; // temp object used for swapping 8 while (left