Selection Sort Step-by-Step Visual Guide
Walk through Selection Sort step by step. Find the minimum element, place it at the front, and repeat. Understand why it always performs O(n squared) comparisons.
Detailed Explanation
How Selection Sort Works
Selection Sort divides the array into a sorted portion (left) and an unsorted portion (right). In each iteration, it finds the minimum element from the unsorted portion and moves it to the end of the sorted portion.
The Algorithm
for i = 0 to n-2:
minIndex = i
for j = i+1 to n-1:
if arr[j] < arr[minIndex]:
minIndex = j
swap(arr[i], arr[minIndex])
Step-by-Step Example
Starting with [64, 25, 12, 22, 11]:
- Find minimum in
[64, 25, 12, 22, 11]→ 11 at index 4 → swap with index 0 →[11, 25, 12, 22, 64] - Find minimum in
[25, 12, 22, 64]→ 12 at index 2 → swap with index 1 →[11, 12, 25, 22, 64] - Find minimum in
[25, 22, 64]→ 22 at index 3 → swap with index 2 →[11, 12, 22, 25, 64] - Find minimum in
[25, 64]→ 25 at index 3 → no swap needed →[11, 12, 22, 25, 64]
Key Characteristics
- Always O(n²) comparisons: Unlike Bubble Sort, Selection Sort cannot terminate early. It always scans the entire unsorted portion to find the minimum, regardless of input order.
- Minimum swaps: Selection Sort performs at most n-1 swaps, which is optimal. This makes it useful when swap operations are expensive (e.g., writing to flash memory).
- Not stable: The swap operation can change the relative order of equal elements.
Comparison Count
The number of comparisons is always n(n-1)/2, which is exactly n²/2 - n/2. For an array of 100 elements, that is 4,950 comparisons regardless of input order.
Use Case
Selection Sort is useful in embedded systems or scenarios where memory writes are expensive (such as EEPROM or flash memory), because it performs the minimum number of swaps. It is also a good teaching algorithm for understanding the concept of finding minimum values and maintaining sorted and unsorted partitions.