Selection Sort
Description
"First, find the smallest item in the array and exchange it with the first entry... Then, find the next smallest item and exchange it with the second entry. Continues in this way until the entire array is sorted." [1]
"Each exchange puts an item into its final position, so the number of exchanges is N."
Efficiency
Uses ~ (N^2)/2 compares (imagine an NxN table of compares; only half of the cells would indicate a comparison) and N exchanges.
Notes
Running time is insensitive to input. "It takes about as long to run selection sort for an array that is already in order ... as it does for a randomly-ordered array!"
Sample Code
// Exchange a[i] with smallest entry in a[i+1]...N
for (int i = 0 ; i < a.length ; i++) {
int min = i;
for (int j = i+1 ; j < a.length ; j++) {
if (less(a[j]), a[min])) min = j
exch(a, i, min); // exchange elements elements i and j of a[]
}
Insertion Sort
Description
"The algorithm that people often use to sort bridge hands is to consider the cards one at a time, inserting each into its proper place among those already considered.
Notes: if the "entries are already in order (or nearly order), then insertion sort is much, much faster".
"Slow for large unordered arrays because the only exchange it does involve adjacent entries, so items can move through he array only one place at a time"
Efficiency
Uses ~ ((N^2)/4) exchanges and ~((N^2)/4) compares on average
((N^2)/2) exchanges and ~((N^2)/2) worst case
N-1 compares and 0 exchanges best case.
Sample Code
// insert a[i] among a[i-1], a[i-2], a[i-3], ...
for (int i = 1 ; i < a.length ; i++) {
for (int j = i ; j > 0 && less(a[j], a[j-1]); j--)
exch(a, j, j-1);
}
Shellsort
Description
A "simple extension to insertion sort that gains speed by allowing exchanges of array entries that are far apart to produce partially sorted arrays that can be efficiently sorted, eventually by insertion sort".
"Rearrange the array to give it the property that every hth entry (starting anywhere) yields a sorted subsequence. Such an array is said to be h-sorted."
Example: take an array, 7-sort it, 3-sort it then finally 1-sort it.
"The code is the same as the insertion sort except that we go backward through the array we skip by h instead of just by 1... Once you 1-sort that an insertion sort so you always got an ordered result." [2]
Efficiency
Depends on the step length. "The worst-case number of compares used by shellsort with 3x+1 increments is O(N^(3/2))
Notes
"A g-sorted array remains g-sorted after h-sorting it."
"Fast unless the array is huge. Tiny, fixed footprint for code (used in embedded systems)." [2]
Sample Code
int h = 1
while (h < a.length/3 ) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, 1093 ...
while (h >= 1) { // h-sort the array
for (int i = h ; i < a.length ; i++) {
// insert a[i] among a[i-h], a[i-2*h], a[i-3*h], ...
for (int j = i ; j >= h && less(a[j], a[j-h]) ; j -= h)
exch(a, j, j-h);
}
h = h/3;
}
Mergesort
Description
"To sort an array, divide it into two halves, sort the two halves (recursively), and then merge the results."
It is a recursive, divide-and-conquer algorithm.
Efficiency
Sorts any array of N items in ~ N log N
Notes
Disadvantage: uses extra space ~ N as merging requires an auxiliary array.
Used in Arrays.sort()
Stability: "this sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort." - Collections.sort().
Sample Code
void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo)/2;
sort(a, lo, mid);
sort(a, mid+1, hi);
merge(a, lo, mid, hi);
}
The merge method looks like the following (where aux is a copy or array a):
int i = lo, j = mid + 1;
for (int k = lo ; k <= hi ; k++) {
if (i > mid) a[k] = aux[j++]; // no more lower
else if (j > hi) a[k] = aux[i++]; // no more higher
else if (less(aux[j], aux[i])) a[k] = aux[j++]; // higher first
else a[k] = aux[i++]; // lower first
}
[1] Algorithms, Sedgewick and Wayne
[2] Sedgwick, Coursera.
No comments:
Post a Comment