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);
}
Mergesort
.
.
Mergesort cost
- Mergesort cost:
- Mergesort is also good for sorting linked lists.
- Mergesort requires twice the space.
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; }
Quicksort Partition
Quicksort Partition Cost
Quicksort Summary
Quicksort Worst Case
.
.
Quicksort Best Case
.
.
Quicksort Average Case
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.