2. Sorting Part 2
2.1. Shellsort
2.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);
}
2.3. Mergesort
2.4. Mergesort cost
Mergesort cost:
Mergesort is also good for sorting linked lists.
Mergesort requires twice the space.
2.5. 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; }
2.6. Quicksort Partition
2.7. Quicksort Partition Cost
2.8. Quicksort Summary
2.9. Quicksort Worst Case
2.10. Quicksort Best Case
2.11. Quicksort Average Case
2.12. 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.