EECE 330 Chapter 2 Sorting, Summer 2014

H. Artail, EECE 330 Internal sorting Rearranging Records Each record contains a field called the key. – Linear order: comparison. Measures of cost: – Comparisons – Swaps H. Artail, EECE 330 Insertion Sort (1) Sorted sublists are NOT final lists. As smaller elements are found, they get “inserted”. Sorted Sublist H. Artail, EECE 330 Insertion Sort (2) template <class Elem, class Comp> void inssort(Elem A[], int n) { //Starting from second element for (int i=1; i<n; i++) //Compare adjacent elements starting from i and going //toward the top of the list: //break if A[j] > A[j-1]: adjacent elements in proper order for (int j=i; (j>0) && (Comp::lt(A[j], A[j-1])); j--) swap(A, j, j-1); } H. Artail, EECE 330 Bubble Sort (1) i is the pass number Compare adjacent elements starting from bottom of list If (A[j] < A[j-1]) swap. H. Artail, EECE 330 Bubble Sort (2) template <class Elem, class Comp> void bubsort(Elem A[], int n) { //Two nested for loops //Let the smallest element “bubble” to the top. for (int i=0; i<n-1; i++) for (int j=n-1; j>i; j--) if (Comp::lt(A[j], A[j-1])) swap(A, j, j-1); } H. Artail, EECE 330 Selection Sort (1) Start from bottom: - look for smallest element - Store its index - @ End, swap with top element H. Artail, EECE 330 Selection Sort (2) template <class Elem, class Comp> void selsort(Elem A[], int n) { // Go through all the elements for (int i=0; i<n-1; i++) { int lowindex = i; // Remember its index // Search through the remaining elements for (int j=n-1; j>i; j--) if (Comp::lt(A[j], A[lowindex])) lowindex = j; // Save index of smallest swap(A, i, lowindex); // Put it in place } } H. Artail, EECE 330 Summary Insertion Bubble Selection Comparisons: Best Case (n) (n2) (n2) Average Case (n2) (n2) (n2) Worst Case (n2) (n2) (n2) Swaps Best Case 0 0 (n) Average Case (n2) (n2) (n) Worst Case (n2) (n2) (n) H. Artail, EECE 330 Shellsort 59 20 17 13 28 14 23 83 36 98 11 70 65 41 42 15 36 20 11 13 28 14 23 15 59 98 17 70 65 41 42 83 28 14 11 13 36 20 17 15 59 41 23 70 65 98 42 83 11 13 17 14 23 15 28 20 36 41 42 70 59 83 65 98 11 13 14 15 17 20 23 28 36 41 42 59 65 70 83 98 H. Artail, EECE 330 Shellsort // Modified version of Insertion Sort template <class Elem, class Comp> void inssort2(Elem A[], int n, int incr) { for (int i=incr; i<n; i+=incr) for (int j=i; (j>=incr)&&(Comp::lt(A[j], A[j-incr])); j-=incr) swap(A, j, j-incr); } template <class Elem, class Comp> void shellsort(Elem A[], int n) { // Shellsort for (int i=n/2; i>2; i/=2) // For each incr for (int j=0; j<i; j++) // Sort sublists inssort2<Elem,Comp>(&A[j], n-j, i); inssort2<Elem,Comp>(A, n, 1); } H. Artail, EECE 330 Quicksort- Example 72 6 57 88 60 42 83 73 48 85 1 Select an arbitrary element as the Pivot: Select middle one 72 6 57 88 60 42 83 73 48 85 l 2 Move pivot to end of list 72 6 57 88 42 83 73 48 85 60 r 1. Move l right while A[l] < pivot 2. Move r left while A[r] > pivot 3. Swap A[l] and A[r] 4. Repeat 1-3 until l and r meet 5. Position of l becomes new position for pivot 85 88 83 72 Single Element: Pivot is in its final position 85 83 83 48 6 57 42 Sublist 6 42 57 48 Repeat above process to position pivot 88 83 73 72 85 42 48 48 83 85 85 83 88 42 48 57 42 48 Chose pivot and find its final position 72 73 85 88 83 48 6 57 42 60 88 83 73 72 85 Permanent position for this element 3 42 57 48 H. Artail, EECE 330 Quicksort template <class Elem, class Comp> void qsort(Elem A[], int i, int j) { // For the original array, i=0 and j=n-1 if (j <= i) return; // List is one element: too small // Find pivot int pivotindex = findpivot(A, i, j); swap(A, pivotindex, j); // Put pivot temporarily at end // Make two partitions; k will be position of the pivot int k = partition<Elem,Comp>(A, i-1, j, A[j]); // Put pivot in permanent place swap(A, k, j); // Repeat above process for both partitions, excluding pivot qsort<Elem,Comp>(A, i, k-1); qsort<Elem,Comp>(A, k+1, j); } template <class Elem> int findpivot(Elem A[], int i, int j) { return (i+j)/2; } H. Artail, EECE 330 Quicksort Partition template <class Elem, class Comp> int partition(Elem A[], int l, int r, Elem& pivot) { do { // Move the bounds inward until they meet while (Comp::lt(A[++l], pivot)); // Move l right while ((r != 0) && Comp::gt(A[--r], pivot)); // Move r left swap(A, l, r); // Swap out-of-place values } while (l < r); // Stop when they cross swap(A, l, r); // Reverse last swap return l; // Return first pos on right } The cost for partition is (n). H. Artail, EECE 330 Partition Example do { // Increment l and then check if A[l]<pivot while (Comp::lt(A[++l], pivot)); // Decrement l and then check if A[r]>pivot while ((r != 0) && Comp::gt(A[--r], pivot)); // Swap out-of-place values swap(A, l, r); // after this swap, A[l]≤pivot and A[r]≥pivot } while (l < r); // Stop when they cross swap(A, l, r); // Reverse last swap H. Artail, EECE 330 Cost of Quicksort Best case: Always partition in half. Worst case: Bad partition. Average case: T(n) = n + 1 + 1/(n-1) (T(k) + T(n-k)) Optimizations for Quicksort: – Better Pivot – Better algorithm for small sublists – Eliminate recursion k=1 n-1 H. Artail, EECE 330 Mergesort- Example Replace Replace sort 20 36 4 13 17 20 36 sort 6 36 20 17 13 28 14 23 15 14 15 23 28 sort Replace Replace 5 20 36 13 17 17 13 Replace Replace 13 17 sort 17 13 7 13 17 20 36 14 15 23 28 8 13 14 15 17 20 23 28 36 sort 1 36 20 17 13 Split in two halves 2 36 20 Split 36 20 3 Split H. Artail, EECE 330 Mergesort Implementation template <class Elem, class Comp> void mergesort(Elem A[], Elem temp[], int left, int right) { int mid = (left+right)/2; if (left == right) return; // We have one element // Recursive calls on the two halves mergesort<Elem,Comp>(A, temp, left, mid); mergesort<Elem,Comp>(A, temp, mid+1, right); for (int i=left; i<=right; i++) // Copy to a temporary temp[i] = A[i]; // below, we sort the two merged sorted sublists int i1 = left; int i2 = mid + 1; for (int curr=left; curr<=right; curr++) { if (i1 == mid+1) // Left exhausted A[curr] = temp[i2++]; else if (i2 > right) // Right exhausted A[curr] = temp[i1++]; else if (Comp::lt(temp[i1], temp[i2])) A[curr] = temp[i1++]; else A[curr] = temp[i2++]; } } H. Artail, EECE 330 Mergesort Cost Mergesort cost: n Arrays of size 1 are merged n/2 arrays of size 2 are merged ….. log(n) levels of recursion: (n) work is done. Total Cost = (nlog(n)) Holds true for best, average, and worst cases. Mergsort is typical for sorting linked lists: Does not required random access. H. Artail, EECE 330 Heapsort - Example 57 83 60 6 48 85 88 42 73 72 73 6 57 88 60 42 83 72 48 85 Original Numbers 83 57 73 85 48 60 72 42 88 6 88 85 83 72 73 42 57 6 48 60 Build Heap 83 57 60 73 72 42 85 48 6 85 73 83 72 60 42 57 6 48 88 Remove 88 83 73 57 72 60 42 48 6 85 88 Remove 85 57 48 60 73 72 42 83 6 H. Artail, EECE 330 Heapsort Example (continued) 57 48 60 72 6 42 73 73 72 57 6 60 42 48 83 85 88 Remove 83 57 48 60 6 42 72 72 60 57 6 42 48 73 83 85 88 Remove 73 57 48 6 42 60 60 6 57 42 48 72 73 83 85 88 Remove 72 48 6 42 57 57 6 48 42 60 72 73 83 85 88 Remove 60 42 6 48 48 6 42 57 60 72 73 83 85 88 Remove 57 6 42 42 6 48 57 60 72 73 83 85 88 Remove 48 6 6 42 48 57 60 72 73 83 85 88 Remove 42 H. Artail, EECE 330 Heapsort template <class Elem, class Comp> void heapsort(Elem A[], int n) { Elem mval; // Use max-heap constructor (it calls the function buildheap) maxheap<Elem,Comp> H(A, n, n); // call the member function removemax (see chapter 5) for (int i=0; i<n; i++) H.removemax(mval);// Put max at end } Use a max-heap, so that elements end up sorted within the array. Cost of heapsort: Cost of finding K largest elements: H. Artail, EECE 330 Binsort for (i=0; i<n; i++) B[A[i]] = A[i]; //puts m in the (m+1)th position A simple, efficient sort Good for permutations of size n Ways to generalize: – Make each bin the head of a list. • To accommodate duplicate keys (values) – Allow more keys than records. H. Artail, EECE 330 Binsort template <class Elem> void binsort(Elem A[], int n) { //if MaxKeyValue is very large, we create a very large array!!! List<Elem> B[MaxKeyValue]; //array of lists Elem item; for (i=0; i<n; i++) B[A[i]].append(A[i]);//puts duplicates in same list //Now, we retrieve the records sequentially //by going through each list for (i=0; i<MaxKeyValue; i++) for (B[i].setStart(); B[i].getValue(item); B[i].next()) output(item); //display, write to a file, etc. } H. Artail, EECE 330 Radix Sort - Example Pick from list Generated after First pass H. Artail, EECE 330 Radix Sort–Example: Implementation cumulative index array No element with a right digit = 0 Position according to right digit Position according to next digit Two elements with next (left) digit = 0 cumulative index array This is 05 Bin: Simulates nodes of a linked list H. Artail, EECE 330 Radix Sort template <class Elem, class Comp> void radix(Elem A[], Elem B[], int n, int k, int r, int cnt[]) {//A[ ]=records array, B[ ]=temporary array, n= # records, //k= # digits, r=radix, cnt[ ]=count array for (int i=0, rtok=1; i<k; i++, rtok*=r) { // initialize the count array for (int j=0; j<r; j++) cnt[j] = 0; // count the number of records for each bin on this pass for(j=0; j<n; j++) cnt[(A[j]/rtok)%r]++; // make cnt[ ] cumulative (to use later as indices for array) for (j=1; j<r; j++) cnt[j] = cnt[j-1] + cnt[j]; // put records into bins, working from bottom of each bin // bins fill from bottom => j counts backward for (j=n-1; j>=0; j--) // decrement to convert from counts to indices B[--cnt[(A[j]/rtok)%r]] = A[j]; for (j=0; j<n; j++) A[j] = B[j]; // put back in A[ ] } } H. Artail, EECE 330 0.001 0.01 0.1 1 10 100 1000 10000 shell quick merge heap radix/8 10 100 1K 10K 100K 1M Number of records (integer values) time (milliseconds) logarithmic scale Experiments were run on a 450MHz, PIII Running Linux using arrays of data quick insertion bubble selection shell merge radix/4 radix/8 heap 0 0.01 0.02 0.03 0.04 0.05 time (milliseconds) Trend is generally true for sizes in the range [10, 100] Comparison Using Empirical Data