Selection Sort

Idea

Selection Sort repeatedly picks the minimum (or maximum) from the unsorted part and places it at the end of the sorted part until done.

Algorithm

1. In each pass, find the minimum in the unsorted part and swap with its first element.
2. Repeat $n-1$ passes until fully sorted.

Pseudo-code:

for i = 0 to n-2:
    min = i
    for j = i+1 to n-1:
        if A[j] < A[min]:
            min = j
    if min != i:
        swap(A[i], A[min])

Complexity

• Best/worst/avg: $O(n^2)$
• Space: $O(1)$
• Stability: unstable

Exercises

Exercise 1

Run selection sort on $A = [64, 25, 12, 22, 11]$ and show each pass.

Exercise 2

What are the time and space complexities of selection sort?