README.md

Elementary Sorts

Elementary Sorts rearranges N items into ascending order.

Selection Sort

Given N items, for each iteration i

• find index min of smallest remaining entry
• swap a[i] and a[min]
• increment i

SelectionSort Class

Operation	Description	Complexity
void sort(Comparable[] a)	Sort the items array	N2

Selection sort is too expensive as it takes N²/2 compares and N exchanges

Insertion Sort

Given N items, for each iteration i

• reset index j = i
• move index j from right to left while j > 0
• swap if a[j] > a[j-1]
• increment i

SelectionSort Class

Operation	Description	Complexity
void sort(Comparable[] a)	Sort the items array	N2

Insertion sort is too expensive as it takes N²/4 compares and N²/4 exchanges on average. However, insertion sort is linear for an items array that is mostly sorted (i.e. Best case scenario).

Shell Sort

Given N items

• move entries more than one position at a time by h-sorting the array

SelectionSort Class

Operation	Description	Complexity
void sort(Comparable[] a)	Sort the items array	N3/2

Shell sort can also be expensive as it takes N^3/2 for the worst case to sort the array. Useful for an array that is already mostly sorted.