Selection sort

Selection sort

Selection sort

Set up another array of same length. the sorted array.

Go through unsorted array and look for min (can use reduction algorithm).

Put minimum in sorted list to left.

Remove that element from unsorted.

+ if linked list can just remove (but we haven’t gotten to those yet) + if array, make new array?

keep going until sorted list exists.

Worst case same as bubble (\(O(n^2)\) for comparisons and swaps) but average is only \(O(n)\) swaps.

Intuitively because each element only gets moved once.