## Sorting Algorithms: Selection Sort

Select the smallest value and put it in place.

- Loop through the array and find the smallest value.
- Then swap that value with the first index which has not been swapped yet
- After looping through the array, the smallest value should have been selected and put in place
- Repeat the above steps until sorted

Efficiency notes:

- If the smallest value is already in place then there is no need to do a "swap".
- Pointer must never point at last value, since there are no values above it to compare with.

## Example

Let's sort an array of ints as an example: [ 5, 2, 1, 4, 3 ]

### Iteration 1:

pointer = 0 smallestValuesIndex = 0

- [ 5, 2, 1, 4, 3 ] smallestValuesIndex = 2 (val=1)
- Swap pointer(0) and smallestValuesIndex(2) [ 1, 2, 5, 4, 3 ]

### Iteration 2:

pointer = 1 smallestValuesIndex = 1

- [ 1, 2, 5, 4, 3 ] smallestValuesIndex = 1 (val=2)
- smallestValuesIndex already in place and dont have to swap [ 1, 2, 5, 4, 3 ]

### Iteration 3:

pointer = 2 smallestValuesIndex = 2

- [ 1, 2, 5, 4, 3 ] smallestValuesIndex = 4 (val=3)
- Swap pointer(2) and smallestValuesIndex(4) [ 1, 2, 3, 4, 5 ]

### Iteration 4:

pointer = 3 smallestValuesIndex = 3

- [ 1, 2, 3, 4, 5 ] smallestValuesIndex = 3 (val=4)
- smallestValuesIndex already in place and dont have to swap [ 1, 2, 3, 4, 5 ]

## About the selection sort algorithm

Big O notation: O(n^{2}) because the outer loop runs n times & the inner loop runs (n-1)/2 times (it reduces by 1 each iteraction)

Not data sensitive: will run the same regardless of the order of the data

Low data movement: only one swap per iteration

In-place sort: the sorted items occupy the same storage as the original ones

Unstable sort: When a swap happens it may change the order of the duplicates