vizlearn
Home / Algorithms

Selection Sort

Algorithms & Data StructuresBy Updated

An in-place comparison sort that divides the list into a sorted and an unsorted part, repeatedly picking the smallest element from the unsorted part.

Parameters

15

Visualization

Step: 0
Click Randomize or Step to begin sorting.

Algorithm Insight

Selection Sort builds the sorted array by repeatedly finding the minimum element from the unsorted part.

  • 1. Set the first unsorted position as the current Minimum.
  • 2. Scan the rest of the unsorted part for a smaller value.
  • 3. If found, update the Minimum index.
  • 4. Swap the found minimum with the first unsorted element.

Complexity

Average Case O(N²)
Space Complexity O(1)

Overview

Divide the array into a sorted prefix and an unsorted suffix. Scan the suffix for its minimum, swap that value with the first suffix position, and extend the prefix by one. After each pass, the prefix contains the smallest values in sorted order.

Find the next minimum

For [7, 3, 5, 2], the first scan finds 2 and swaps it with 7: [2, 3, 5, 7]. The next scan begins after 2 and finds 3 already in place. Continue until one value remains. Set Array Size, press Randomize Array, and use Next Step to see each scan and swap.

Cost and properties

Selection sort makes about (n(n-1)/2) comparisons regardless of input order. Even a sorted array still requires scanning each remaining suffix to confirm its minimum. Its running time is therefore quadratic in the best, average, and worst cases.

The standard version is in-place and performs at most (n-1) swaps. That low number of writes can be useful when writes are unusually expensive, but selection sort is not stable by default: swapping a distant minimum can move equal values past each other. In most ordinary uses, insertion sort is preferable for small or nearly sorted inputs, and a faster general-purpose sort is preferable for large inputs.

Common mistakes with Selection Sort

  • Stopping early because the prefix looks sorted: the remaining suffix must still be checked.
  • Assuming it adapts to sorted input: it performs the same number of comparisons either way.
  • Calling the basic algorithm stable: an early swap can change the order of equal values.
  • Confusing few swaps with low total work: it still scans quadratically many elements.

Sources and next steps

Run it in Python

Selection sort's defining trait is that it makes exactly n − 1 swaps no matter what you feed it. The program counts both comparisons and swaps so you can see one stay fixed while the other does not.

selection_sort.pyPython 3
Output
How the code works
  1. smallest = iAssume the first unsorted item is the minimum, then try to disprove it. Tracking the index rather than the value is what lets the swap at the end be a single operation.
  2. for j in range(i + 1, n):The scan always covers the entire unsorted tail, with no early exit available — you cannot know something is the minimum without looking at everything. Hence n(n−1)/2 comparisons, always.
  3. if smallest != i:Skips the swap when the item is already where it belongs. It saves a write, not a comparison, so it does not change the complexity.
  4. swapsAt most n − 1 swaps for any input. Where a write is expensive — flash memory, or records far larger than the key — that is a real advantage over bubble or insertion sort.
Change one thing
  • Feed it an already sorted list. The comparison count is identical to the reversed case: selection sort cannot detect that it has no work to do.
  • Track the largest instead of the smallest and fill from the right. Same algorithm, mirrored — and a good check that you have followed it.
  • Sort [2, 2, 1] and follow the two 2s. Their order flips, which is why selection sort is not stable while insertion sort is.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: set Array Size to its maximum (30). Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. How many comparisons does selection sort make on an already sorted list of n items?
  2. What selection sort is genuinely good at:
  3. Sorting [2, 2, 1] with this implementation:





 Cheat sheet
Selection Sort
Scan for the smallest remaining value and swap it into place, one position at a time, until the whole array is sorted.
ALGORITHMS · vizlearn.in/dsa/selection_sort.html
More in Algorithms
AlgorithmsInsertion SortAlgorithmsRecursion and the Call StackAlgorithmsDivide and ConquerAlgorithmsMerge Sort
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact