Selection Sort
Selection Sort is a simple comparison-based sorting algorithm that divides the array into sorted and unsorted regions. It repeatedly selects the smallest (or largest) element from the unsorted region and moves it to the end of the sorted region. The algorithm performs the minimum number of swaps (n-1 at most), making it useful when memory writes are expensive operations.
Visualization
Interactive visualization for Selection Sort
Animation Speed: 400ms
🔴 Red: Minimum | 🔵 Blue: Comparing | 🟢 Green: Sorted
Interactive visualization with step-by-step execution
Implementation
1function selectionSort(arr: number[]): number[] {
2 const sorted = [...arr];
3 const n = sorted.length;
4
5 for (let i = 0; i < n - 1; i++) {
6 let minIdx = i;
7 for (let j = i + 1; j < n; j++) {
8 if (sorted[j] < sorted[minIdx]) minIdx = j;
9 }
10 if (minIdx !== i) {
11 [sorted[i], sorted[minIdx]] = [sorted[minIdx], sorted[i]];
12 }
13 }
14 return sorted;
15}Deep Dive
Theoretical Foundation
Selection Sort works by maintaining two subarrays: a sorted subarray on the left and an unsorted subarray on the right. In each iteration, the algorithm finds the minimum element from the unsorted portion and swaps it with the first element of the unsorted portion, effectively expanding the sorted region by one element. Unlike Insertion Sort, Selection Sort always performs O(n²) comparisons regardless of input, making it non-adaptive. However, it performs the fewest swaps of any sorting algorithm, making it efficient when the cost of swapping elements is high. The algorithm is not stable in its standard form but can be made stable with modifications.
Complexity
Time
O(n²)
O(n²)
O(n²)
Space
O(1)
Applications
Industry Use
Sorting when memory writes are expensive (flash memory, EEPROM)
Small embedded systems with limited resources
Situations where swap count minimization is critical
Educational purposes for teaching sorting concepts
Simple applications where code simplicity is paramount
Use Cases
Related Algorithms
Quicksort
A highly efficient, in-place sorting algorithm that uses divide-and-conquer strategy. Invented by Tony Hoare in 1959, it remains one of the most widely used sorting algorithms due to its excellent average-case performance and cache efficiency.
Merge Sort
A stable, divide-and-conquer sorting algorithm with guaranteed O(n log n) performance.
Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. This process is repeated until the entire array is sorted. Named for the way larger elements 'bubble' to the top (end) of the array.
Insertion Sort
Insertion Sort is a simple, intuitive sorting algorithm that builds the final sorted array one element at a time. It works similarly to how people sort playing cards in their hands - picking each card and inserting it into its correct position among the already sorted cards. Despite its O(n²) time complexity, Insertion Sort is efficient for small datasets and nearly sorted arrays, making it practical for real-world applications.