It is a simple sorting algorithm, the logic behind it as follows:

- Start with element at index (i) => i = 0
- Find the smallest element on the right of an element at index (i)
- Swap the two elements
- Increment the index, move to the right
- Repeat untill the end

### The Invariants

- Elements to the left of the index are never changed, they are in ascending order
- No element to the right of the index is smaller than any element to the left of it

### Sample Code

```
for(int i=0;i<array.length()){
int min = i;
for(int j=i+1;j<array.length()){
if (less(arr[j],arr[min])){
min = j;
};
}
swap(arr[i],arr[min]);
}
```

### Mathematical Analysis

- Proposition: Selection sort uses
**N^2/2**compares and**N**exchanges - Selection sort runs in quadratic time, even if input is sorted
- Data movement is minimal - Linear number of exchanges