Selection Sort

Selection Sort works by finding the smallest element from the unsorted portion and swapping it with the first element of that portion. This repeats until everything is sorted.

Algorithm

1. Find the smallest element in the array.
2. Swap it with the first element.
3. Find the smallest element in the remaining array.
4. Swap it with the second element.
5. Repeat until finished.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Example

data = [64, 25, 12, 22, 11]
print(selection_sort(data))  # [11, 12, 22, 25, 64]

Visualization

[64, 25, 12, 22, 11]

i=0: min=11 (index 4), swap with 64
[11, 25, 12, 22, 64]

i=1: min=12 (index 2), swap with 25
[11, 12, 25, 22, 64]

i=2: min=22 (index 3), swap with 25
[11, 12, 22, 25, 64]

i=3: min=25 (index 3), no swap needed
[11, 12, 22, 25, 64]

i=4: done

Time Complexity

Always O(n²) because it must scan the entire remaining array on every iteration.

Space Complexity

O(1) - in-place.

Selection Sort vs Insertion Sort

Characteristics

• Not stable: Elements with equal values can change order.
• In-place: Yes.
• Not adaptive: Not faster when the data is already sorted.
• Minimum swaps: Only n-1 swaps, fewer than bubble sort.

When to Use It

• You want to minimize the number of swaps.
• The dataset is very small.
• You need a simple implementation.
• Writes are expensive (write-heavy memory).

# Selection sort minimizes swaps
data = [5, 3, 1, 4, 2]
# Swaps elements directly to their correct positions, far fewer swaps than bubble sort

Selection Sort is simple but slow. Binary Search is much faster for searching sorted data.