Selection Sort

Introduction

Selection sort is a simple comparison-based sorting algorithm that works by repeatedly finding the minimum element from the unsorted portion of the array and placing it at the beginning of the unsorted portion. The algorithm maintains two subarrays: the sorted subarray on the left, which is built up one element at a time, and the remaining unsorted subarray on the right.

Unlike bubble sort and insertion sort, selection sort performs the minimum number of swaps possible -- exactly n - 1 swaps for an array of n elements. This makes it advantageous in situations where the cost of swapping elements is high, such as when sorting large records where only a key field is compared but the entire record must be moved.

The algorithm has a consistent O(n^2) time complexity regardless of the initial ordering of the data, which means it performs the same number of comparisons whether the input is already sorted, reverse sorted, or randomly arranged. This predictability can be either an advantage or a disadvantage depending on the application.

"Selection sort is notable for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited." -- Robert Sedgewick, Algorithms

How It Works

Basic Approach

The algorithm divides the array into a sorted region and an unsorted region. In each iteration, it selects the smallest element from the unsorted region and swaps it with the first unsorted element.

1. Set the first unsorted position as the current position (starting at index 0).
2. Scan the unsorted portion to find the element with the minimum value.
3. Swap the minimum element with the element at the current position.
4. Move the boundary between sorted and unsorted one position to the right.
5. Repeat until the entire array is sorted (n - 1 iterations total).

Key Insight

Each iteration places exactly one element in its final sorted position. After k iterations, the first k elements of the array are the k smallest elements in their final sorted order. This is a stronger guarantee than insertion sort provides, where the first k elements are sorted among themselves but may not be in their final positions.

Algorithm and Pseudocode

procedure selectionSort(A : array of sortable items) n := length(A) for i := 0 to n - 2 do // Find the index of the minimum element in A[i..n-1] minIndex := i for j := i + 1 to n - 1 do if A[j] < A[minIndex] then minIndex := j end if end for // Swap the minimum element with A[i] if minIndex != i then swap(A[i], A[minIndex]) end if end forend procedure

The outer loop runs n - 1 times. In each iteration, the inner loop scans the unsorted portion to find the minimum. A single swap at the end of each outer iteration places the minimum into its correct position. The check minIndex != i avoids unnecessary self-swaps.

Time and Space Complexity

Space Complexity: O(1). Selection sort is an in-place algorithm, requiring only a constant amount of extra memory for the loop variables and the temporary swap variable.

Stability: The standard implementation of selection sort is not stable. When two elements have equal keys, a swap can change their relative order. For example, consider [3a, 2, 3b]. After the first pass, 2 is swapped with 3a, producing [2, 3a, 3b] -- but if the minimum were at a different position, the order of equal elements could change. A stable variant exists but requires additional logic or linked-list-based implementation.

Non-adaptive: Selection sort always performs exactly n(n - 1) / 2 comparisons regardless of input order. It does not take advantage of existing order in the data.

Worked Example

Sort the array [29, 10, 14, 37, 13] in ascending order using selection sort.

After 4 passes (n - 1 = 5 - 1), the array is fully sorted: [10, 13, 14, 29, 37]. Note that only 3 actual swaps were performed. The bold portion indicates the sorted region after each pass.

Advantages and Disadvantages

Advantages

• Minimal swaps: Performs at most n - 1 swaps, making it efficient when write operations are expensive (e.g., writing to flash memory or EEPROM).
• Simple to implement: Easy to understand and code correctly.
• In-place: Requires only O(1) additional memory.
• Predictable performance: Always performs the same number of comparisons, making execution time predictable.
• No overhead for nearly sorted data: While it does not benefit from sorted input, it also does not suffer from any pathological worst case beyond O(n^2).

Disadvantages

• Always O(n^2): Does not adapt to input order. Even a fully sorted array requires n(n - 1) / 2 comparisons.
• Not stable: The standard implementation does not preserve the relative order of equal elements.
• Slower than insertion sort on average for most inputs, especially nearly sorted data.
• Not competitive with advanced algorithms: For large datasets, O(n log n) algorithms like merge sort and quicksort are vastly superior.

Comparison with Other Algorithms

Selection Sort vs. Insertion Sort: Insertion sort is generally preferred because it is adaptive (O(n) on sorted data), stable, and performs fewer operations on average. Selection sort's only advantage is fewer swaps, which matters when data movement is costly.

Selection Sort vs. Heap Sort: Heap sort can be viewed as an optimized version of selection sort. Both select the extreme element and place it, but heap sort uses a heap data structure to find the minimum in O(log n) time rather than O(n), resulting in O(n log n) overall.

Implementation Notes

Double Selection Sort

A variant that finds both the minimum and maximum in each pass, placing the minimum at the beginning and the maximum at the end. This reduces the number of passes by half but does not change the overall O(n^2) complexity.

procedure doubleSelectionSort(A : array) left := 0 right := length(A) - 1 while left < right do minIndex := left maxIndex := left for i := left to right do if A[i] < A[minIndex] then minIndex := i if A[i] > A[maxIndex] then maxIndex := i end for swap(A[left], A[minIndex]) // Adjust maxIndex if it was at the left position if maxIndex == left then maxIndex := minIndex swap(A[right], A[maxIndex]) left := left + 1 right := right - 1 end whileend procedure

Stable Selection Sort

To make selection sort stable, instead of swapping the minimum element with the first unsorted element, shift all elements between the insertion point and the minimum's position one place to the right, then insert the minimum. This increases the number of data movements but preserves relative order of equal elements.

Heap Sort Connection

Heap sort is essentially selection sort with a more efficient method for finding the minimum (or maximum) element. By organizing the unsorted portion as a binary heap, the selection step takes O(log n) time instead of O(n), yielding O(n log n) overall complexity.

Applications

• Memory-write-limited environments: Flash memory and EEPROM have limited write cycles. Selection sort's minimal number of swaps makes it suitable for sorting data stored in such media.
• Small datasets: For arrays with fewer than 10-20 elements, its simplicity and low overhead make it a reasonable choice.
• Educational purposes: Selection sort is commonly used to teach algorithm design, loop invariants, and complexity analysis.
• Finding the k smallest or largest elements: A partial selection sort that runs only k iterations efficiently finds the k smallest elements in O(kn) time.
• Sorting with expensive swaps: When the cost of comparing is negligible but the cost of moving data is high, selection sort's guarantee of at most n - 1 swaps is valuable.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms, 4th Edition. MIT Press, 2022. Problem 2-2.
• Knuth, D. E. The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd Edition. Addison-Wesley, 1998. Section 5.2.3: Sorting by Selection.
• Sedgewick, R. and Wayne, K. Algorithms, 4th Edition. Addison-Wesley, 2011. Section 2.1: Elementary Sorts.
• Skiena, S. S. The Algorithm Design Manual, 3rd Edition. Springer, 2020.