Selection Sort
Selection sort is a simple comparison-based sorting algorithm that divides the array into a sorted and an unsorted region. It repeatedly finds the minimum element from the unsorted region and places it at the beginning of the unsorted portion, growing the sorted region one element at a time. While not efficient for large datasets, its simplicity and minimal number of swaps make it easy to understand and useful in memory-constrained environments.
How Selection Sort Works
Selection sort works by maintaining two sub-arrays within the given array: a sorted sub-array at the front and an unsorted sub-array for the remaining elements. In each pass, it selects the smallest element from the unsorted sub-array and swaps it with the first unsorted element, effectively extending the sorted portion by one.
Step-by-step process:
- Start at position 0: Consider the entire array as unsorted. Set the current position to 0.
- Find the minimum: Scan through all elements from the current position to the end of the array to find the element with the smallest value.
- Swap into place: Swap the minimum element found with the element at the current position. This places the smallest unsorted element at the front of the unsorted region.
- Advance the boundary: Move the boundary between sorted and unsorted regions one position to the right. The element just placed is now part of the sorted sub-array.
- Repeat: Continue this process for each position from 0 to n-2. After n-1 passes, the entire array is sorted.
- No early exit: Unlike bubble sort, selection sort always performs O(n²) comparisons regardless of the initial order of elements. However, it makes at most O(n) swaps, which is optimal for situations where writes are expensive.
Selection sort is not stable because the swap operation can change the relative order of equal elements. For example, sorting [3a, 2, 3b] will swap 3a with 2 to get [2, 3a, 3b], but then on the next step 3a and 3b are already in place -- however in other configurations the long-distance swap can reorder equal elements. Despite this, selection sort is a great teaching tool and performs well when auxiliary memory is limited since it only requires O(1) extra space.
Interactive Visualization
Watch how selection sort finds the minimum element in the unsorted portion and swaps it into position. Yellow bars indicate the element currently being scanned, orange bars indicate the current minimum found so far (or a swap in progress), and green bars are in their final sorted position.
Code Implementation
Below is a standard selection sort implementation in three languages. The algorithm always performs n-1 passes regardless of the input, making its time complexity O(n²) in all cases. However, it performs at most n-1 swaps, which is significantly fewer than bubble sort or insertion sort in most scenarios.
def selection_sort(arr):
"""Selection sort: find minimum and swap into position."""
n = len(arr)
for i in range(n - 1):
# Find the index of the minimum element in arr[i:]
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# Swap the found minimum with the first unsorted element
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# Example usage
numbers = [64, 25, 12, 22, 11, 90, 34, 45]
print("Unsorted:", numbers)
print("Sorted: ", selection_sort(numbers))
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// Find the index of the minimum element in arr[i:]
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// Swap the found minimum with the first unsorted element
if (minIdx != i) {
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
}
public static void main(String[] args) {
int[] numbers = {64, 25, 12, 22, 11, 90, 34, 45};
System.out.print("Unsorted: ");
printArray(numbers);
selectionSort(numbers);
System.out.print("Sorted: ");
printArray(numbers);
}
private static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i < arr.length - 1) System.out.print(", ");
}
System.out.println();
}
}
#include <iostream>
#include <vector>
using namespace std;
void selectionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
// Find the index of the minimum element in arr[i:]
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// Swap the found minimum with the first unsorted element
if (minIdx != i) {
swap(arr[i], arr[minIdx]);
}
}
}
void printArray(const vector<int>& arr) {
for (int i = 0; i < arr.size(); i++) {
cout << arr[i];
if (i < arr.size() - 1) cout << ", ";
}
cout << endl;
}
int main() {
vector<int> numbers = {64, 25, 12, 22, 11, 90, 34, 45};
cout << "Unsorted: ";
printArray(numbers);
selectionSort(numbers);
cout << "Sorted: ";
printArray(numbers);
return 0;
}
Complexity Analysis
Selection sort always performs the same number of comparisons regardless of the initial order. In every case, it scans the unsorted portion to find the minimum, resulting in n(n-1)/2 comparisons. The number of swaps, however, is at most n-1, making it efficient when write operations are costly.
| Metric | Complexity | Notes |
|---|---|---|
| Best Case Time | O(n²) | Always scans entire unsorted portion, even if already sorted |
| Average Case Time | O(n²) | Elements are in random order |
| Worst Case Time | O(n²) | Array is sorted in reverse order |
| Space Complexity | O(1) | In-place sorting, only uses a temporary variable for swaps |
| Stable | No | Long-distance swaps can change the relative order of equal elements |
Quiz
Test your understanding of selection sort with these questions.
Q1. What is the best-case time complexity of selection sort?
Q2. How many swaps does selection sort perform in the worst case for an array of n elements?
Q3. Is selection sort a stable sorting algorithm?
Q4. After the first pass of selection sort on the array [29, 10, 14, 37, 13], what is the state of the array?
Q5. What is the primary advantage of selection sort over bubble sort?