Selection Sort
Selection Sort is a sorting algorithm based on repeatedly selecting the smallest element from the unsorted portion of the array and placing it in its correct position.
On each pass, the algorithm scans the remaining elements, finds the minimum, and swaps it with the current position. This produces at most one swap per pass, which is far fewer writes than bubble sort performs on the same input.
Loading simulation...
Although it is not efficient for large datasets, Selection Sort illustrates the trade-off between comparisons and swaps clearly, which makes it useful for understanding how sorting algorithms differ.
This chapter covers how Selection Sort works, how to implement it across multiple languages, and where it fits among other sorting algorithms.
What Is Selection Sort?
Selection sort is a comparison-based algorithm. At any point during the sort, the array is divided into two regions:
- Sorted region (left side): contains elements that are already in their final sorted positions.
- Unsorted region (right side): contains elements that still need to be processed.
In each pass, the algorithm selects the smallest element from the unsorted region and swaps it with the first element of the unsorted region. This grows the sorted region by one element and shrinks the unsorted region by one.
How It Differs from Bubble Sort
Selection sort and bubble sort take different approaches to moving elements into position.
Bubble sort repeatedly compares adjacent elements and swaps them if they are out of order. It performs many swaps per pass, bubbling the largest element to the end.
Selection sort scans the entire unsorted portion to find the minimum, then performs exactly one swap per pass. Selection sort always does fewer swaps than bubble sort for the same input. Selection sort performs at most n-1 swaps for an array of n elements, while bubble sort can perform as many as O(n^2) swaps.
| Property | Bubble Sort | Selection Sort |
|---|---|---|
| Swaps per pass | Up to n-1 | Exactly 1 |
| Total swaps (worst case) | O(n^2) | O(n) |
| Comparison count | O(n^2) (O(n) best case with early termination) | O(n^2) |
| Early termination | Yes (if no swaps) | No |
| Stable | Yes | No |
This difference matters when swaps are expensive. Sorting large objects where moving data is costly favors selection sort because of its minimal number of swaps.
How It Works
The algorithm has five steps:
- Start with the first position (index 0) as the current position.
- Scan the entire unsorted region (from the current position to the end) to find the index of the minimum element.
- Swap the minimum element with the element at the current position.
- Move the current position one step to the right (the sorted region grows by one).
- Repeat steps 2-4 until the current position reaches the second-to-last element.
After n-1 passes, every element is in its correct sorted position. The algorithm needs only n-1 passes because once n-1 elements are placed correctly, the last element is already in the right spot.
The inner loop's only job is to find the index of the minimum element. It does not perform any swaps. The single swap happens once, after the inner loop finishes, which keeps the write count low.
Code Implementation
Loading animation...
The implementation uses only basic array operations: comparisons, index tracking, and a single swap per pass.
Complexity Analysis
Selection sort has a straightforward complexity profile. Its performance does not change based on the input.
| Case | Time Complexity | Explanation |
|---|---|---|
| Best | O(n^2) | Even on an already sorted array, the algorithm still scans the unsorted region to find the minimum on every pass. There is no early termination. |
| Average | O(n^2) | The number of comparisons is always the same regardless of element ordering. |
| Worst | O(n^2) | Same number of comparisons as the best case. The only difference is whether swaps move elements. |
Exact comparison count: Pass 1 makes n-1 comparisons. Pass 2 makes n-2. And so on. The total is:
(n-1) + (n-2) + ... + 1 = n(n-1)/2
This count is the same for every input.
| Metric | Value | Notes |
|---|---|---|
| Space complexity | O(1) | Only uses a few extra variables (minIndex, temp). Sorts in place. |
| Number of swaps | O(n) | At most n-1 swaps (one per pass), which is near-optimal for in-place comparison sorting. |
| Stable | No | The single long-distance swap per pass can leap an equal element over its earlier duplicate. |
| Adaptive | No | Does not benefit from partially sorted input. Always does the same number of comparisons. |
The lack of adaptiveness is a notable drawback. Bubble sort can terminate early if no swaps occur in a pass. Insertion sort runs in O(n) on nearly sorted arrays. Selection sort always does the full O(n^2) comparisons regardless of input.
Stability
Selection sort is not stable. The single swap per pass can move an element over equal elements that lie between its current position and the position of the minimum, which breaks the original relative order.
Consider the array [5a, 3, 5b, 1], where 5a and 5b are two records with the same key. The first pass finds the minimum (1 at index 3) and swaps it with arr[0], producing [1, 3, 5b, 5a]. The original 5a, 5b ordering is reversed.
A linked-list variant that detaches and reinserts nodes (rather than swapping array slots) can preserve stability, but the standard array implementation cannot.
When to Use Selection Sort
Good Situations
- When swaps are expensive. Sorting records where each swap involves moving large chunks of memory (for example, sorting structs or objects without using pointers) favors selection sort because it minimizes write operations. With at most n-1 swaps, it does far fewer writes than bubble sort or insertion sort.
- When memory is tightly constrained. Selection sort uses O(1) auxiliary space and allocates no extra arrays or buffers, which matters in embedded systems with strict memory budgets.
- Small arrays (n < 20). For tiny arrays, the overhead of more sophisticated algorithms like quicksort or merge sort is not worth it. Selection sort's simplicity keeps constant factors low.
- When predictability matters. Selection sort always does the same amount of work regardless of input, which gives it consistent timing across inputs.
Bad Situations
- Large datasets. O(n^2) time becomes impractical quickly. Sorting 10,000 elements requires roughly 50 million comparisons. For anything beyond a few hundred elements, use O(n log n) algorithms like merge sort or quicksort.
- When stability is required. Selection sort is not stable. Use insertion sort or merge sort when equal elements must preserve their original relative order.
- Nearly sorted arrays. Selection sort does not benefit from existing order in the array. Insertion sort, by contrast, runs in nearly O(n) time on almost-sorted data. Selection sort underperforms on partially sorted inputs.
- When average-case efficiency matters. Even among O(n^2) algorithms, insertion sort tends to outperform selection sort on average because it does fewer comparisons on random data and adapts to partial order.
Quiz
Selection Sort Quiz
10 quizzes