# Sorting

Still under **HEAVY** construction

Search algorithms work better with ordered (sorted) set (with the exception of sequential search )

#### Selection

As selection sort runs, the subarray at the beginning of the array is sorted, but the subarray at the end is not. Selection sort scans the unsorted subarray for the next element to include in the sorted subarray.

Lowest value is selected each time and put (traversing each tie the remaining of the set) loop till end of items - keep potion of first element loop till end of - move cursor to next item - save cursor position if value is lower - move cursor to

#### Insertion sorting

#### QuickSort

Yes, QuickSort is great for generalized sorting, if …

1) you don’t worry about worst-case input sets (i.e. order is generally random), 2) you need it to operate in-place (and the entire data set fits in memory), 3) you don’t need it to adapt to already- or mostly-sorted inputs, and 4) you don’t need it to be stable (for use in progressive multi-key sorts).

If the data is mostly-sorted, then Insertion or Shell can be great.

If you really must eliminate the possibility of that worst-case, you could use Heap (or at least Quick3) which are NlogN and in-place. On average, Quick is faster than both of these, but they radically improve any guarantee you can give.

Merge is a great stable NlogN sort without Quick’s “potentially pathological performance” (but it’s a memory hog). It’s also the only reasonable choice if the data set is too big to fit into memory.

And of course the best trivia question of all: if for some reason Writes are incredibly expensive relative to Reads, then you might actually want Selection (or even better, Cycle).

For short arrays, there is less initial overhead with Insertion, too.

#### Links

https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

https://www.hackerearth.com/practice/notes/sorting-code-monk/

##### Demos

http://panthema.net/2013/sound-of-sorting/

https://www.toptal.com/developers/sorting-algorithms/