## Steps

- Loop through the array
- Find the smallest element in the unsorted portion of the array
- Swap the smallest element with the first element in the unsorted portion of the array

*The sorted portion of the array is on the left side while the unsorted portion is on the right. In the diagrams below, the blue boxes represent the sorted elements of the array, while the white boxes represent the unsorted elements. Elements that are going to be swapped are shown in green boxes.*

On every iteration, an element from the unsorted portion is added to the sorted portion. For example, if we start with this array:

At this stage, the unsorted array is the *entire array*. The smallest element found is `1`

, so swap that with the *first element of the unsorted array*.

So after the first iteration, only the first element is sorted:

Now loop through the *unsorted array* (the items after the first element, which is now sorted). In the unsorted array, swap the smallest item with the first item

After the second iteration, the first two elements are sorted, as another element from the unsorted portion is added to the sorted portion:

This continues `n - 1`

times, where `n`

is the length of the list.

Third iteration:

Fourth iteration:

Fifth iteration:

Note that it runs `n - 1`

times, since the last element is already sorted.

## Pseudocode

```
function selection_sort(list):
n = list.length
for i from 0 to n-1:
# Initialize smallest element to first one
smallest_index = 1
# Traverse through the unsorted list to find the
# smallest element
for j from i to n:
if collection[j] < collection[smallest_index]:
smallest_index = j
# Swap smallest element with first element of
# unsorted list
swap(collection[smallest_index], collection[i])
return collection
```

## Python

While the pseudocode will produce expected results, there is a simple optimization we can make.

`smallest_index`

is already given an initial value of`i`

, so there is no need to start at`i`

in the inner for loop. Even if`i`

happens to be the smallest value,`smallest_index`

is already set to`i`

.- We only need to swap
`collection[smallest_index]`

and`collection[i]`

if`i`

is not equal to`smallest_index`

.

```
def selection_sort(collection):
length = len(collection)
for i in range(length - 1):
smallest_index = i
for j in range(i + 1, length):
if collection[j] < collection[smallest_index]:
smallest_index = j
if smallest_index != i:
collection[smallest_index], collection[i] = (
collection[i],
collection[smallest_index],
)
return collection
```

To debug, I am going to run the following and print the list at every iteration:

`selection_sort([3, 5, 2, 1, 9, 6])`

The output is

```
[3, 5, 2, 1, 9, 6]
[1, 5, 2, 3, 9, 6]
[1, 2, 5, 3, 9, 6]
[1, 2, 3, 5, 9, 6]
[1, 2, 3, 5, 9, 6]
[1, 2, 3, 5, 6, 9]
[1, 2, 3, 5, 6, 9]
```

## Time complexity

The worst-case scenario is $O(n^2)$ since there is a nested loop.

The first iteration has `n`

swaps, the second has `n - 1`

, the third has `n - 2`

, and so on, so

$n + (n - 1) + (n - 2) + (n - 3) + ... + 1 = \cfrac{n^2}{2} + \cfrac{n}{2}$

Since $n^2$ is the highest magnitude, the time complexity is $O(n^2)$.

The best case scenario is also $\Omega{(n^2)}$ since selection sort will **not** exit if the list is already sorted.