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
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:
- Average Case Sort:
- Worst Case Sort:
- Worst Case: