__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