30.18. Sorting Part 2¶
30.18.1. Sorting Part 2¶
30.18.1.1. Shellsort¶
30.18.1.2. Shellsort (2)¶
void shellsort(Comparable[] A) { for (int i=A.length/2; i>2; i/=2) // For each increment for (int j=0; j<i; j++) // Sort each sublist inssort2(A, j, i); inssort2(A, 0, 1); // Could call regular inssort here } /** Modified Insertion Sort for varying increments */ void inssort2(Comparable[] A, int start, int incr) { for (int i=start+incr; i<A.length; i+=incr) for (int j=i; (j>=incr) && (A[j].compareTo(A[j-incr]) < 0); j-=incr) swap(A, j, j-incr); }void shellsort(Comparable* A[], int n) { for (int i = n/2; i > 2; i /= 2) //For each increment for (int j = 0; j < i; j++) //Sort each sublist inssort2(A, j, i, n); inssort2(A, 0, 1, n); } // Modified Insertion Sort for varying increments void inssort2(Comparable* A[], int start, int incr, int n) { for (int i = start+incr; i < n; i += incr) for (int j = i; ((j >= incr) && (*A[j] < *A[j-incr])); j -= incr) swap(A, j, j-incr); }
30.18.1.3. Mergesort¶
30.18.1.4. Mergesort cost¶
- Mergesort cost:
- Mergsort is also good for sorting linked lists.
- Mergesort requires twice the space.
30.18.1.5. Quicksort¶
void quicksort(Comparable[] A, int i, int j) { // Quicksort int pivotindex = findpivot(A, i, j); // Pick a pivot swap(A, pivotindex, j); // Stick pivot at end // k will be the first position in the right subarray int k = partition(A, i, j-1, A[j]); swap(A, k, j); // Put pivot in place if ((k-i) > 1) quicksort(A, i, k-1); // Sort left partition if ((j-k) > 1) quicksort(A, k+1, j); // Sort right partition }void quicksort(Comparable* A[], int i, int j) { int pivotindex = findpivot(i, j); swap(A, pivotindex, j); // Stick pivot at end // k will be the first position in the right subarray int k = partition(A, i, j-1,A[j]); swap(A, k, j); // Put pivot in place if ((k-i) > 1) quicksort(A, i, k-1); // Sort left partition if ((j-k) > 1) quicksort(A, k+1, j); // Sort right partition }int findpivot(Comparable[] A, int i, int j) { return (i+j)/2; }int findpivot(int i, int j) { return (i+j)/2; }
30.18.1.8. Quicksort Summary¶
30.18.1.10. .¶
.
30.18.1.12. .¶
.
30.18.1.14. Optimizations for Quicksort¶
- Better Pivot
- Inline instead of function calls
- Eliminate recursion
- Better algorithm for small sublists: Insertion sort
- Best: Don't sort small lists at all, do a final Insertion Sort to clean up.
30.18.1.17. Binsort¶
for (i=0; i<A.length; i++) B[A[i]] = A[i];for (i=0; i<A.length; i++) B[A[i]] = A[i];for (i=0; i<A.length; i++) B[A[i]] = A[i];for (i=0; i<A.length; i++) B[A[i]] = A[i];
30.18.1.18. Radix Sort: Linked List¶
30.18.1.19. .¶
.
30.18.1.20. Radix Sort: Array¶
30.18.1.21. Radix Sort Implementation¶
static void radix(Integer[] A, int k, int r) { Integer[] B = new Integer[A.length]; int[] count = new int[r]; // Count[i] stores number of records with digit value i int i, j, rtok; for (i=0, rtok=1; i<k; i++, rtok*=r) { // For k digits for (j=0; j<r; j++) count[j] = 0; // Initialize count // Count the number of records for each bin on this pass for (j=0; j<A.length; j++) count[(A[j]/rtok)%r]++; // count[j] will be index in B for last slot of bin j. // First, reduce count[0] because indexing starts at 0, not 1 count[0] = count[0] - 1; for (j=1; j<r; j++) count[j] = count[j-1] + count[j]; // Put records into bins, working from bottom of bin // Since bins fill from bottom, j counts downwards for (j=A.length-1; j>=0; j--) { B[count[(A[j]/rtok)%r]] = A[j]; count[(A[j]/rtok)%r] = count[(A[j]/rtok)%r] - 1; } for (j=0; j<A.length; j++) A[j] = B[j]; // Copy B back } }static void radixsort(int A[], int k, int r, int n) { int B[n]; int count[r]; int i, j, rtok; for (i = 0, rtok = 1; i < k; i++, rtok *= r) { // For k digits for (j = 0; j < r; j++) count[j] = 0; // Initialize count // Count the number of records for each bin on this pass for (j = 0; j < n; j++) count[(A[j]/rtok)%r]++; // count[j] will be index in B for last slot of bin j. // First, reduce count[0] because indexing starts at 0, not 1 count[0] = count[0] - 1; for (j = 1; j < r; j++) count[j] = count[j-1] + count[j]; // Put records into bins, working from bottom of bin // Since bins fill from bottom, j counts downwards for (j = n-1; j >= 0; j--) { B[count[(A[j]/rtok)%r]] = A[j]; count[(A[j]/rtok)%r] = count[(A[j]/rtok)%r] - 1; } for (j = 0; j < n; j++) A[j] = B[j]; // Copy B back } }
30.18.1.22. .¶
.
30.18.1.24. Empirical Analysis¶
\[\begin{split}\begin{array}{l|rrrrrrrr} \hline \textbf{Sort} & \textbf{10}& \textbf{100} & \textbf{1K}& \textbf{10K} & \textbf{100K}& \textbf{1M}& \textbf{Up} & \textbf{Down}\\ \hline \textrm{Insertion} & .00023 & .007 & 0.66 & 64.98 & 7381.0 & 674420 & 0.04 & 129.05\\ \textrm{Bubble} & .00035 & .020 & 2.25 & 277.94 & 27691.0 & 2820680 & 70.64 & 108.69\\ \textrm{Selection} & .00039 & .012 & 0.69 & 72.47 & 7356.0 & 780000 & 69.76 & 69.58\\ \textrm{Shell} & .00034 & .008 & 0.14 & 1.99 & 30.2 & 554 & 0.44 & 0.79\\ \textrm{Shell/O} & .00034 & .008 & 0.12 & 1.91 & 29.0 & 530 & 0.36 & 0.64\\ \textrm{Merge} & .00050 & .010 & 0.12 & 1.61 & 19.3 & 219 & 0.83 & 0.79\\ \textrm{Merge/O} & .00024 & .007 & 0.10 & 1.31 & 17.2 & 197 & 0.47 & 0.66\\ \textrm{Quick} & .00048 & .008 & 0.11 & 1.37 & 15.7 & 162 & 0.37 & 0.40\\ \textrm{Quick/O} & .00031 & .006 & 0.09 & 1.14 & 13.6 & 143 & 0.32 & 0.36\\ \textrm{Heap} & .00050 & .011 & 0.16 & 2.08 & 26.7 & 391 & 1.57 & 1.56\\ \textrm{Heap/O} & .00033 & .007 & 0.11 & 1.61 & 20.8 & 334 & 1.01 & 1.04\\ \textrm{Radix/4} & .00838 & .081 & 0.79 & 7.99 & 79.9 & 808 & 7.97 & 7.97\\ \textrm{Radix/8} & .00799 & .044 & 0.40 & 3.99 & 40.0 & 404 & 4.00 & 3.99\\ \hline \end{array}\end{split}\]
30.18.1.25. Sorting Lower Bound (1)¶
- We would like to know a lower bound for the problem of sorting
- Sorting is \(O(n \log n)\) (average, worst cases) because we know of algorithms with this upper bound.
- Sorting I/O takes \(\Omega(n)\) time. You have to look at all records to tell if the list is sorted.
- We will now prove \(\Omega(n log n)\) lower bound for sorting.
