Sorting algorithms
Sorting algorithms are of great interest because of their obvious applications in computer programs, but also because of their mathematical properties. One question in particular: what is the minimum number of comparisons necessary to sort a list of values? For lists of n elements, most straightforward algorithms use O(n^2) comparisons, but this can be improved. The optimal number is O(n log n) comparisons, and no correct algorithm can work faster in general. Check this Wikipedia section for the idea of the proof.
While sorting is a very basic task, there are various algorithms useful in various situations. Some algorithms excel when the input list to sort is already presorted to some degree, by taking advantage of this existing order; those are called adaptive. Other algorithms maintain the relative order of records with equal keys; those are stable. Also the memory usage can be significant.
This website presents visualizations of various sorting algorithms.
BitonicSort focuses on converting a list into a bitonic sequence: one that monotonically increases, then decreases.
BubbleSort repeatedly compares each pair of adjacent items and swaps them if they are in the wrong order, until the whole list is sorted.
CocktailSort is a slight variation of BubbleSort and passes alternately from bottom to top and then from top to bottom.
CombSort checks items on some gap distance away, swapping them if necessary, and repeatedly lessening the gap until the whole list is ordered.
CycleSort is based on the idea that the sequence to be sorted can be factored into cycles, which can individually be rotated.
GnomeSort repeatedly finds the first place where two adjacent elements are in the wrong order, and swaps them.
HeapSort iteratively shrinks the unsorted region of a list by moving its largest element into the sorted region, using a binary heap data structure.
InsertionSort repeatedly removes one element from the input list and inserts it into the correct location within the sorted list.
MergeSort divides a list into two halves, then sorts the two halves recursively, and finally merges the results.
OddEvenSort alternatingly compares all odd/even and even/odd indexed pairs of adjacent elements, swapping them if necessary.
QuickSort works by partitioning the list into two parts according to some pivot element, then sorting the parts recursively.
RadixSort sorts data with integer keys by grouping them by the individual digits sharing the same significant position and value.
SelectionSort repeatedly selects the smallest element in the unsorted region and appends it to the sorted region.
ShellSort sorts pairs of elements far apart from each other and progressively reduces the gap between elements to be compared.
SmoothSort is a variation of HeapSort but uses a custom heap structure.
StoogeSort recursively sorts the initial 2/3 of the input list, the final 2/3, and again the initial 2/3.
TimSort takes advantage of existing structure, by marching over the list once, alternately identifying the next “run” and merging it intelligently.
