6.3. Sorting: Faster Sorts¶
6.3.1. Faster Sorts¶
6.3.1.1. Shellsort¶
6.3.1.2. Shellsort (2)¶
static void shellsort(int[] 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 */ static void inssort2(int[] A, int start, int incr) { for (int i=start+incr; i<A.length; i+=incr) for (int j=i; (j>=incr) && (A[j] < A[j-incr]); j-=incr) Swap.swap(A, j, j-incr); }
6.3.1.3. Mergesort¶
6.3.1.4. .¶
.
6.3.1.5. Mergesort cost¶
Mergesort cost:
Mergesort is also good for sorting linked lists.
Mergesort requires twice the space.
6.3.1.6. Quicksort¶
static void quicksort(Comparable[] A, int i, int j) { // Quicksort int pivotindex = findpivot(A, i, j); // Pick a pivot Swap.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.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 }static int findpivot(Comparable[] A, int i, int j) { return (i+j)/2; }
6.3.1.9. Quicksort Summary¶
6.3.1.11. .¶
.
6.3.1.13. .¶
.
6.3.1.15. 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.
