# Selection sort

## Algorithm

```
def selection(a)
"""
Implements the selection sort algorithm
"""
for i in range(0,len(a)):
min_index = i
min_element = a[i]
# Find minimum value
for j in range(i, len(a)):
if a[j] < min_element:
min_index = j
min_element = a[j]
# Exchange current and minimum values
temp = a[i]
a[i] = min_element
a[min_index] = temp
return a
```

## Key concepts

- In each step, find the minimum element.
- Exchange the minimum element with the current element.

## Step by step

```
array = [1,0,3,4,2,5]
i = 0
min_index = 0
min_element = 1
j = 1
a[1] < min_element | 0 < 1 | True
min_index = 1
min_element = 0
j = 2
a[2] < min_element | 3 < 0 | False
j = 3
a[3] < min_element | 4 < 0 | False
j = 4
a[4] < min_element | 2 < 0 | False
j = 5
a[5] < min_element | 5 < 0 | False
temp = a[0] | temp = 1
a[0] = min_element | a[0] = 0
a[min_index] = temp | a[1] = 1
array = [0,1,3,4,2,5]
i = 1
min_index = 1
min_element = 1
j = 2
a[2] < min_element | 3 < 1 | False
j = 3
a[3] < min_element | 4 < 1 | False
j = 4
a[4] < min_element | 2 < 2 | False
j = 5
a[5] < min_element | 5 < 1 | False
temp = a[1] | temp = 1
a[1] = min_element | a[1] = 1
a[min_index] = temp | a[1] = 1
array = [0,1,3,4,2,5]
i = 2
min_index = 2
min_element = 3
j = 3
a[3] < min_element | 4 < 3 | False
j = 4
a[4] < min_element | 2 < 3 | True
min_index = 4
min_element = 2
j = 5
a[5] < min_element | 5 < 3 | False
temp = a[2] | temp = 3
a[2] = min_element | a[2] = 2
a[min_index] = temp | a[4] = 3
array = [0,1,2,4,3,5]
```

## Complexity analysis

### Time

For each element of the array, we compare it with the remaining elements of the array. For each element of the array, we exchange it with the minimum element of the array.

```
i = 0
5 comparisons ; 1 exchange
i = 1
4 comparisons ; 1 exchange
i = 2
3 comparisons ; 1 exchange
i = 3
2 comparisons ; 1 exchange
i = 4
1 comparisons ; 1 exchange
i = 5
0 comparisons ; 1 exchange
```

Comparisons: (N-1) + (N-2) + … 1 -> 1 + 2 + … + (N-1) = N(N-1) / 2 ≈ N²/2 Exchanges: 1 + 1 + … + 1 = N

O(N) = (N²/2) + N ≈ (N²/2)

### Space

We use the same array that is passed as an argument and a few more variables, so O(N) = N + O(i) + O(j) + O(min_index) + O(min_element) + O(temp) = N + 5·O(1) = N + 5

O(N) = N + 5 ≈ N.