排序

Selection Sort

Given an array $A$ of size $n$, the selection sort iterates through indices $0\le k<n$, at each step finding the minimum element of the sub-array $A[k,n)$ and swapping its position with $A[k]$. See the following example of the selection sort:

64 25 12 22 11 // this is the initial, starting state of the array

11 25 12 22 64 // sorted sublist = {11}

11 12 25 22 64 // sorted sublist = {11, 12}

11 12 22 25 64 // sorted sublist = {11, 12, 22}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25, 64}

This is $O(n^2)$ since in the worst case you will have to search $n+(n-1)+\dots+1=\frac{n(n+1)}2=O(n^2)$.

Insertion Sort

The insertion sort iteratively sorts the first $k$ elements of the array, by finding what position the next element should go. This is $O(n^2)$ because in the worst case, the array starts sorted in the opposite direction, so you need to make at most $1+2+\dots+n=\frac{n(n+1)}2=O(n^2)$ swaps.

Merge Sort

Merge sort is a recursive sort that splits an array in two halves and sorts each half, then merges the two sorted components together. Try proving that merge sort runs in $O(n\log n)$!

Beyond

Finally, here is a cute little video to show you some of the sorting algorithms.