Back to Study Material Data Structures and Algorithms

Selection Sort

Selection sort takes a different approach from bubble sort. Instead of repeatedly swapping adjacent elements, it divides the array into a sorted left porti...

Selection Sort

Finding the Minimum Repeatedly

Selection sort takes a different approach from bubble sort. Instead of repeatedly swapping adjacent elements, it divides the array into a sorted left portion and an unsorted right portion. In each pass, it finds the minimum element in the unsorted portion and swaps it into the next position of the sorted portion. After n minus 1 passes, the entire array is sorted.

Consider the array 64, 25, 12, 22, 11. In the first pass, scan the entire array and find the minimum element 11 at index 4. Swap it with the element at index 0 to get 11, 25, 12, 22, 64. In the second pass, scan indices 1 through 4 and find the minimum 12 at index 2. Swap it with index 1 to get 11, 12, 25, 22, 64. Continue until the array is sorted: 11, 12, 22, 25, 64.

Pseudocode: for i from 0 to n-2, set min_index to i. For j from i+1 to n-1, if array at j is less than array at min_index, set min_index to j. Swap array at i with array at min_index.

Time complexity is O(n squared) in all cases: best, average, and worst. Unlike bubble sort, selection sort cannot terminate early even if the array is already sorted, because it does not have information about whether the unsorted portion is already ordered. Space complexity is O(1).

A notable property of selection sort is that it makes at most n minus 1 swaps, exactly one per pass. This is the minimum number of swaps needed in the worst case. Bubble sort, by contrast, can make O(n squared) swaps. This makes selection sort preferable when the cost of writing to memory is high, such as in flash memory with limited write cycles.

Interview tip: when asked about selection sort, always highlight the O(n) swap count property. It is the key insight that separates selection sort from other O(n squared) algorithms and the main reason it has practical uses.

Stability and the Swap Problem

Selection sort as typically taught is not a stable sorting algorithm, and this is a subtle point that trips up many students. Stability means that elements with equal keys preserve their original relative order. Selection sort violates this because its swap operation can move an element past other elements with the same key.

A concrete example demonstrates the instability. Consider the array of pairs: (3, A), (3, B), (1, C) where the first component is the sort key. The algorithm finds the minimum key of 1 at index 2 and swaps it with index 0 to get (1, C), (3, B), (3, A). The two elements with key 3 are now in reversed order: B before A has become B after A relative to the sorted portion. A stable sort would produce (1, C), (3, A), (3, B).

Selection sort can be made stable by replacing the swap operation with a shift operation. Instead of swapping the minimum to its correct position, shift all elements between the current position and the minimum one position to the right and insert the minimum at the current position. This is exactly what insertion sort does, which is why insertion sort is stable. However, making selection sort stable this way increases the number of writes to O(n squared), eliminating its main advantage.

A worked example from a real application: sorting a table of database records by a secondary key while preserving the primary key order requires a stable sort. Using standard selection sort here would corrupt the primary ordering, causing subtle bugs.

Time complexity remains O(n squared) with or without the stability modification. Space complexity remains O(1).

Interview tip: if asked whether selection sort is stable, say no and immediately explain why with a concrete counterexample. Then describe how to make it stable and what the trade-off is. This three-part answer demonstrates a thorough understanding of the algorithm.

Selection Sort vs Other Quadratic Sorts

Selection sort, bubble sort, and insertion sort all run in O(n squared) time on average and in the worst case. Choosing among them requires understanding their constant factors and their behavior on specific input distributions.

Selection sort always makes exactly floor of n times (n minus 1) divided by 2 comparisons, regardless of the input. This is because the inner loop always runs to the end of the unsorted portion. No early termination is possible. In contrast, insertion sort makes only O(n) comparisons on nearly sorted input and bubble sort with early termination also approaches O(n) on nearly sorted data. For random input, all three make roughly n squared divided by 2 comparisons.

The distinguishing feature of selection sort is its minimal write count. It performs at most n minus 1 write operations (one swap per outer loop iteration, and a swap involves three assignments, giving at most 3n minus 3 writes). Bubble sort performs O(n squared) writes in the worst case. Insertion sort performs O(n squared) writes as well, though each write is a shift rather than a swap.

In applications where writes are expensive and reads are cheap, such as sorting EEPROM data in embedded systems or sorting records on write-once media, selection sort outperforms the alternatives despite equal asymptotic time complexity.

A worked example: a medical device logs sensor readings to flash memory. Each flash write costs 50 times as much as a read. Sorting 100 readings with selection sort requires at most 99 write operations. Bubble sort on the same data might require up to 4,950 write operations. Selection sort extends the lifetime of the flash memory by a factor of 50 in this scenario.

Time complexity: O(n squared) best, average, and worst. Space complexity: O(1). Stable: no (in standard form).

Interview tip: frame selection sort as the sort of choice when writes are expensive, not when comparisons are the bottleneck. This shows you think about hardware and system-level concerns, not just algorithmic theory.