Picture a row of numbered cards lying face up on a table, and you want them in order from smallest to largest. The most natural move is to scan for the lowest card, pull it to the front, then do the same with whatever’s left. Keep going until there’s nothing left to scan, and congratulations: you’ve just run selection sort.
It’s one of the easiest sorting algorithms to learn, and it teaches a lesson I wish someone had pointed out to me earlier. An algorithm can be simple and predictable and still not be fast. In this guide, we’ll walk through how the selection sort algorithm works, write it in Python, and see how it compares with bubble sort and insertion sort.
What Is Selection Sort?
Selection sort is a comparison-based sorting algorithm. It repeatedly finds the smallest value in the unsorted part of a list and places it at the beginning of that section.
Think of the list as having two parts:
- Sorted section: The values on the left that are already in their correct positions.
- Unsorted section: The values on the right that still need to be checked.
At the start, the sorted section is empty. On each pass, selection sort finds the smallest value in the unsorted section and swaps it into the first unsorted position. The sorted section grows by one element each time.
How Does Selection Sort Work? A Step-by-Step Example
Let’s sort this list in ascending order:
[29, 10, 14, 37, 13]
Watch Selection Sort in Action
Follow the algorithm as it finds the smallest value in the unsorted section and moves it into place.
Array: [29, 10, 14, 37, 13]
Pass 1
- Start with the first value,
29, as the current minimum. - Scan the remaining values. The smallest value is
10. - Swap
10with the first value,29.
The list is now [10, 29, 14, 37, 13]. The first position is sorted.
Pass 2
- Ignore the sorted
10and scan the remaining values:[29, 14, 37, 13]. - The smallest value is
13. - Swap it with
29, the first value in the unsorted section.
The list becomes [10, 13, 14, 37, 29]. The first two positions are now sorted.
Pass 3
In the remaining section, [14, 37, 29], the smallest value is already 14. No swap is needed. The list stays [10, 13, 14, 37, 29].
Pass 4
Compare the final two unsorted values, 37 and 29. The smaller value is 29, so swap them. The result is [10, 13, 14, 29, 37].
And that's it. The list is sorted. For a list of five values, the algorithm needs four passes; in general, it needs at most n - 1 passes.
Selection Sort in Python
Once you understand the passes, the code is quite straightforward. The outer loop chooses the next position to fill, while the inner loop searches for the smallest value in the remaining unsorted section.
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
# Swap only when a smaller value was found elsewhere
if min_index != i:
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
numbers = [29, 10, 14, 37, 13]
print(selection_sort(numbers))
# Output: [10, 13, 14, 29, 37]A couple of details are worth noticing:
min_indexremembers the position of the smallest value found so far.- The inner loop starts at
i + 1, because everything beforeiis already sorted. - The swap happens after the scan is complete, not every time a smaller value is found.
- The
min_index != icheck avoids an unnecessary self-swap when the current value is already the smallest.
The function sorts the list in place, so it changes the original list and returns that same list for convenience.
Selection Sort Time and Space Complexity
Selection sort's main drawback becomes clear when we look at how many comparisons it makes.
On the first pass, it checks n - 1 values. On the next, it checks n - 2, then n - 3, and so on until one value remains. The total number of comparisons is:
(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2
That grows quadratically as the input gets larger, so the time complexity is:
| Case | Time complexity | Why? |
|---|---|---|
| Best | O(n²) | It still scans the unsorted section on every pass, even if the list is already sorted. |
| Average | O(n²) | The number of comparisons does not depend on the initial order. |
| Worst | O(n²) | It performs the same pattern of scans for any input order. |
Space complexity: O(1). Selection sort works in place and uses only a small, fixed amount of extra memory for variables such as i, j, and min_index.
Why Selection Sort Makes Fewer Swaps
There is one useful advantage hidden behind all those comparisons: selection sort performs at most n - 1 swaps. It scans the unsorted section first, then moves the selected minimum into place with a single swap (unless it is already there).
That is fewer swaps than bubble sort can make, which may matter in situations where writes are relatively expensive. The trade-off is that selection sort still performs quadratic-time comparisons, even when the input is already sorted.
Is Selection Sort Stable?
No. The standard swap-based version of selection sort is not stable.
A stable sorting algorithm preserves the original relative order of items that have equal keys. Selection sort can change that order because a swap may move an element across other equal elements.
For example, imagine two equal values labelled 5a and 5b:
[5a, 5b, 2]The smallest value is 2, so the first and last elements are swapped:
[2, 5b, 5a]The two equal values have changed their relative order. That is why the standard version is unstable. A stable variant is possible by shifting elements instead of swapping, but that changes the algorithm's write behaviour.
Selection Sort vs. Bubble Sort vs. Insertion Sort
These three algorithms are often taught together. They all have O(n²) worst-case time complexity, but they behave differently:
| Feature | Selection sort | Bubble sort* | Insertion sort |
|---|---|---|---|
| Best-case time | O(n²) | O(n) | O(n) |
| Worst-case time | O(n²) | O(n²) | O(n²) |
| Stable? | No | Yes | Yes |
| Extra space | O(1) | O(1) | O(1) |
| Main strength | Few swaps | Simple to visualize | Works well on small or nearly sorted data |
*Bubble sort's best-case O(n) assumes the optimized version uses an early-exit check.
For many small or nearly sorted lists, insertion sort is usually the more practical choice. Selection sort is interesting when keeping the number of swaps low is important, while bubble sort is often used mainly to introduce the idea of sorting through repeated comparisons.
Advantages and Disadvantages of Selection Sort
Advantages
- Easy to understand and implement.
- Sorts in place using
O(1)extra space. - Performs at most
n - 1swaps. - Its comparison count is predictable, regardless of the input order.
Disadvantages
O(n²)time makes it inefficient for large datasets.- It does not become faster when the input is already sorted.
- The standard swap-based version is not stable.
When Should You Use Selection Sort?
For most real-world applications, selection sort is not the right choice for sorting large collections. Standard library sorting functions are generally much more efficient and have been carefully optimized.
Still, selection sort is worth understanding:
- Learning the basics. It is a clear way to practise loops, comparisons, arrays and swapping.
- Very small lists. With only a few values, its simplicity may be enough.
- Write-sensitive situations. Its low number of swaps can be useful when writes are more costly than comparisons, although the overall context matters.
- Technical interviews. It is useful to know how it works and how it compares with other basic sorting algorithms.
Common Mistakes to Avoid
- Swapping too early. First scan the entire unsorted section to find the minimum. Swap only after the scan is complete.
- Starting the inner loop at the wrong index. It should start at
i + 1, because positioniis the current minimum candidate. - Sorting the wrong section. Each pass should search only the unsorted part, not the entire list again.
- Assuming it is stable. The usual swap-based implementation can change the order of equal elements.
- Expecting an already sorted list to be faster. Selection sort still performs the same number of comparisons.
Try It Yourself
Reading the steps is a good start, but try implementing the algorithm yourself to make the idea stick:
- Modify the Python function to sort the list in descending order.
- Add a counter to track how many comparisons the algorithm makes.
- Try an already sorted list and check whether the number of comparisons changes.
- Change the implementation to select the largest value and place it at the end of the unsorted section.
Quick Recap
Selection sort repeatedly finds the smallest value in the unsorted part of a list and moves it into its correct position. It is easy to follow, sorts in place, and makes at most n - 1 swaps. The downside is that it always makes O(n²) comparisons, even when the list is already sorted.
Once you are comfortable with selection sort, compare it with insertion sort and then move on to merge sort or quicksort. Seeing how those algorithms reduce the amount of work is a great way to build your intuition for algorithm efficiency.
Frequently Asked Questions
What is selection sort in simple words?
It repeatedly finds the smallest value in the unsorted part of a list and moves it to the front of that section until the list is sorted.
What is the time complexity of selection sort?
Its best, average and worst-case time complexity are all O(n²), because it scans the remaining unsorted values on every pass.
How many swaps does selection sort make?
At most n - 1 swaps for a list of n elements. An implementation can skip a swap when the minimum is already in the correct position.
Is selection sort stable?
No. The standard swap-based version can change the relative order of equal elements.
Is selection sort an in-place algorithm?
Yes. It rearranges the original list and uses only O(1) extra space.
Is selection sort better than bubble sort?
It usually performs fewer swaps, but both have O(n²) average and worst-case time complexity. Optimized bubble sort can achieve O(n) best-case time on an already sorted list, while selection sort cannot.
Is selection sort used in real applications?
It is uncommon for general-purpose sorting because of its quadratic running time. It is mainly useful for learning, very small inputs, or special situations where minimizing swaps is important.
Found this helpful? Try implementing selection sort in your favourite language, then compare the number of comparisons and swaps with bubble sort. A little experimentation makes the differences much easier to remember.
