Two years ago I tried to arrange my bookshelf by height, shortest on the left. I had no plan. I just picked up the shortest book I could find in the whole pile and placed it at the start. Then I looked at the remaining pile, found the next shortest, and placed it right after. I repeated this until the pile was gone.
That is selection sort. No fancy math needed to understand it. You already ran the algorithm once, on real books.
How Selection Sort Actually Works
Selection sort splits a list into two sections: a sorted section at the front and an unsorted section behind it. On every pass, it scans the entire unsorted section, finds the smallest value, and swaps it into the first open spot of the sorted section.
Here is the pass-by-pass version with the array [29, 10, 14, 37, 13]:
- Pass 1: scan the whole array, find 10, swap it with 29. Array becomes [10, 29, 14, 37, 13].
- Pass 2: scan from index 1 onward, find 13, swap it with 29. Array becomes [10, 13, 14, 37, 29].
- Pass 3: scan from index 2 onward, 14 is already the smallest, no swap needed.
- Pass 4: scan from index 3 onward, find 29, swap it with 37. Array becomes [10, 13, 14, 29, 37].
Five books, four passes, done. For n items, selection sort always runs n-1 passes.
The Code
Here is a plain Python version:
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
if min_index != i:
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
print(selection_sort([29, 10, 14, 37, 13]))
# [10, 13, 14, 29, 37]
The outer loop picks the position to fill. The inner loop hunts for the smallest remaining value. One swap closes out each pass.
Why It Never Gets Faster, No Matter the Input
This is the part most explanations skip. With bubble sort, an already sorted list finishes fast because the algorithm can detect nothing needs swapping. Selection sort has no such shortcut.
Even if your bookshelf pile was already sorted shortest to tallest, selection sort still scans the full remaining pile on every single pass to confirm it found the smallest one. According to GeeksforGeeks, selection sort's best, average, and worst case time complexity all land at O(n²), and the reason is structural: the algorithm cannot know an item is the minimum without checking every other unsorted item first.
The number of comparisons is fixed at n(n-1)/2 no matter the starting order. A 10,000 item list takes roughly 50 million comparisons regardless of whether it started sorted, reversed, or shuffled.
Where Selection Sort Actually Wins
Selection sort loses on speed, but it wins on writes. It performs at most n-1 swaps total, always, because it only swaps once per pass. Bubble sort and insertion sort can trigger far more swaps on the same data.
This matters in places where writing data costs more than reading it. Flash memory has limited write cycles, and embedded systems often run on tight memory budgets. In those environments, a predictable, low-swap algorithm like selection sort can be a reasonable choice even with its slow comparison count.
Outside of that narrow case, selection sort mainly shows up in classrooms and coding interviews, as a way to build intuition before moving to faster algorithms like merge sort or quicksort.
The Stability Problem
A sorting algorithm is stable if two equal items keep their original relative order after sorting. Selection sort does not guarantee this, because its swap can jump an equal item out of place.
Take [4a, 4b, 3], where 4a and 4b are equal but track their original position. Selection sort finds 3 as the smallest, and swaps it with 4a. The array becomes [3, 4b, 4a]. Notice 4b now comes before 4a, the opposite of their starting order.
If you are sorting a list where order among ties matters, like students with matching scores, skip selection sort and reach for merge sort or insertion sort instead.
Selection Sort vs Its Closest Relatives
| Algorithm | Time (all cases) | Space | Swaps | Stable |
|---|---|---|---|---|
| Selection sort | O(n²) | O(1) | at most n-1 | No |
| Bubble sort | O(n²) worst, O(n) best | O(1) | can be high | Yes |
| Insertion sort | O(n²) worst, O(n) best | O(1) | moderate | Yes |
Insertion sort beats selection sort on nearly sorted data because it adapts to existing order. Selection sort never adapts. That single difference is why interviewers often ask you to explain both back to back.
The One Thing to Remember
Selection sort finds the smallest remaining item and puts it where it belongs, over and over, with no shortcuts. That simplicity is exactly why it is slow on large data and exactly why it is still the first sorting algorithm most people learn. Once you can trace it by hand on five numbers, every other comparison based sort gets easier to follow.
FAQs:
Q: What is selection sort in simple terms?
A: It is a sorting method that repeatedly finds the smallest remaining item and moves it to the front of the list, one item at a time.
Q: What is the time complexity of selection sort?
A: O(n²) in the best, average, and worst case, because it always scans the full unsorted section on every pass.
Q: Is selection sort stable?
A: No. Swapping can push equal elements out of their original relative order.
Q: Is selection sort in-place?
A: Yes. It sorts within the original array and uses only O(1) extra space.
Q: How many swaps does selection sort perform?
A: At most n-1 swaps, which is fewer than bubble sort or insertion sort typically make on the same data.
Q: When should I actually use selection sort?
A: For small datasets, teaching purposes, interview practice, or environments like flash memory where writes are expensive and swaps need to stay low.
Top comments (0)