# Selection Sort

This is the worst algorithm, but it is introduced in every class.

High Level Idea:

- Find the smallest element of array
- Swap with the first element of array
- Repeat with the rest of the array, looking for the second smallest element and swapping with the second element

### Selection Sort Pseudocode

A is the name of the array

```
for i in range(len(A)-1):
i_min = i
for j in range(i+1, len(A)): # 1. Find smallest element
if A[j] < A[i_min]:
i_min = j
A[i_min], A[i] = A[i], A[i_min] # 2. Swap
```

### Time Complexity

This algorithm is bad because no matter the case, even when the array is sorted, we need to go through every element twice.

- Best Case Sort: $O(n_{2})$
- Average Case Sort: $O(n_{2})$
- Worst Case Sort: $O(n_{2})$

### Space Complexity

- Worst Case: $O(1)$

Better algorithms: