Sorting

More notes coming soon!

A sort is a permutation of a sequence of elements that brings them into order according to some total order. A total order $\preccurlyeq$ is
- Total: $x \preccurlyeq y$ or $y \preccurlyeq x$ for all $x, y$ .
- Reflexive: $x \preccurlyeq x$ .
- Antisymmetric: $x \preccurlyeq y$ and $y \preccurlyeq x$ iff $x = y$ .
- Transitive: $x \preccurlyeq y$ and $y \preccurlyeq z$ implies $x \preccurlyeq z$ .
Another way to define sorting is using inversions. An inversion is a pair of elements that are out of order.

For example, the array $[0, 1, 1, 2, 3, 4, 8, 6, 9, 5, 7 ]$ has 6 out of 55 possible inversions, specifically $(8, 6), (8, 5), (8, 7), (6, 5), (9, 5), (9, 7)$ .

The goal of sorting is to reduce the number of inversions to zero.
A sort is in-place if it uses a small, constant amount of additional memory.
A sort is stable if the order of equal items is preserved. This is desirable, for example, if we want to sort on two different properties of our objects. An application of this is sorting a rows in a spreadsheets first by column A (e.g. first name) and then by column B (e.g. last name).
We’ll be looking at six sorting algorithms: Bubble sort, Selection sort, Insertion sort, Heapsort, Merge sort and Quicksort.

results matching ""