V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Selection Sort

Scan the unsorted suffix for its minimum and place exactly one value on every outer pass.

Core idea

For each output position, scan the entire remaining suffix and remember its minimum. One final swap places that minimum and grows the sorted prefix by exactly one.

Read the visualization

The scan pointer visits every candidate while a separate marker follows the best minimum seen so far. Only the pass-ending swap changes the array.

7
6
5
10
9
8
4
3
2
1

Begin a pass that will choose the minimum of the unsorted suffix.

1function selectionSort(a: number[]): number[] {
2 const n = a.length;
3 for (let i = 0; i < n - 1; i++) {
4 let minIdx = i;
5 for (let j = i + 1; j < n; j++) {
6 if (a[j] < a[minIdx]) {
7 minIdx = j;
8 }
9 }
10 if (minIdx !== i) {
11 [a[i], a[minIdx]] = [a[minIdx], a[i]];
12 }
13 }
14 return a;
15}
n10
i0
j0
minIdx0
a[j]7
a[minIdx]7
swapCount0
sortedUpTo0
1 / 131

Complexity and tradeoffs

Time: O(n^2). Space: O(1). It performs only O(n) swaps but is generally unstable and always makes quadratic comparisons.

Invariant: Before pass i, positions before i contain the globally smallest i values in final order.

Where it fits

Selection Sort is useful when writes are much more expensive than comparisons because it performs only a linear number of swaps. It is otherwise mostly a compact teaching algorithm.