Sorting Tested code in 3 languages

Selection Sort, Visualized Step by Step

Scan the unsorted part for its smallest value, swap it to the front, repeat. Press play to watch every comparison and swap, next to the exact line of code that runs.

Crio.Do · Last updated 19 November 2026

Interactive selection sort

Sort indices 0–7 (8 values): on each pass, find the smallest value that is left and swap it to the front of the unsorted part.

0Comparisons
0Swaps
1/–Step
def selection_sort(a):    n = len(a)    for i in range(n - 1):        m = i        for j in range(i + 1, n):            if a[j] < a[m]:                m = j        if m != i:            a[i], a[m] = a[m], a[i]

The highlighted line is the one the animation is running. This is the exact code we test.

Tip: use the arrow keys to step when the visualizer has focus. Try duplicates, a sorted list or your own numbers.

On this page
  1. How it works
  2. Worked example
  3. Complexity
  4. When to use it
  5. Common mistakes
  6. Interview questions
  7. FAQ
  8. Sources

How selection sort works

Selection sort splits the array into a sorted part on the left and an unsorted part on the right. On each pass it selects the smallest value in the unsorted part and swaps it to the front of that part. The sorted part grows by one, and the values in it never move again.

Think of picking a team by height: look along the whole line for the shortest person, send them to the front, then look along the rest of the line for the next shortest. You compare everyone each time, but each person moves at most once.

The code keeps m, the index of the smallest value seen so far in this pass. Every comparison is between a[j] and a[m]; when a[j] is smaller, m moves to j. In the animation, the dashed line marks the smallest value so far, so a bar that dips below it becomes the new minimum.

Two numbers define selection sort. It always makes exactly n(n − 1)/2 comparisons, whatever the input, because it cannot know a value is the smallest without looking at all the others. And it makes at most n − 1 swaps, fewer than insertion or bubble sort on almost any input. The long-distance swap is also why it is not stable.

The algorithm in 5 steps

  1. 1 For each position i from the left, except the last:
  2. 2 Set m = i: assume the first unsorted value is the smallest.
  3. 3 Compare every later value a[j] with a[m]; if it is smaller, set m = j.
  4. 4 If m is not i, swap a[i] and a[m]. Index i is now final.
  5. 5 When only one value is left, it is the largest, so it is already in place.

Worked example

Here is the full run on a fixed array, generated by the same code as the visualizer. Each row is the end of one pass: the swap that put the smallest remaining value in place. The comparisons in between are counted in the total but not listed.

Input: [29, 10, 14, 37, 13]

  1. Step 8 Swap 10 into index 0 (and 29 to index 1). Index 0 is final. 1029143713
  2. Step 15 Swap 13 into index 1 (and 29 to index 4). Index 1 is final. 1013143729
  3. Step 19 The smallest value, 14, is already at index 2: no swap needed. Index 2 is final. 1013143729
  4. Step 23 Swap 29 into index 3 (and 37 to index 4). Index 3 is final. That leaves 37 at index 4, also final. 1013142937

Total for this run: 10 comparisons and 3 swaps, in 24 animation steps. Result: 10, 13, 14, 29, 37.

Time and space complexity

Best

O(n²)

Even on sorted input every pass scans the whole unsorted part: n(n − 1)/2 comparisons, though no swaps.

Average

O(n²)

The comparisons never change with the data. Only the number of swaps does, and it is at most n − 1.

Worst

O(n²)

n(n − 1)/2 comparisons, the same as every other input, and up to n − 1 swaps.

Space

O(1)

Only the indices i, j and m. No extra array, no recursion.

Stable:
No
In place:
Yes
Adaptive:
No
Swaps:
At most n − 1

Six sorts, same 8 numbers

Comparison counts from running each algorithm on the visualizer's array, then on the same numbers already sorted and in reverse order. Computed from the code on these pages, not typed in.

AlgorithmComparisonsMovesSorted inputReversed input
Insertion sort 1713 shifts728
Selection sort 285 swaps2828
Bubble sort 2513 swaps728
Merge sort 1624 writes1212
Quick sort 385 swaps3132
Heap sort 2619 swaps2724

The last two columns are comparisons too. Exact counts depend on the input and the variant (this page's selection sort skips a swap when the smallest value is already in place), which is why complexity is stated as growth, not exact numbers.

When to use it, and when not to

Good fit

  • Writes are much more expensive than reads, for example on flash memory with limited write cycles, or when each "swap" physically moves something. Selection sort does at most n − 1 swaps.
  • Tiny arrays where code size matters more than speed, such as small embedded programs: the loop is short and uses no extra memory.
  • Teaching the idea of "find the minimum, then shrink the problem", which leads straight to heap sort: selection sort with a heap to find the minimum in O(log n).
  • You only need the k smallest values: k passes give them in order in O(n·k), with no need to sort the rest.

Pick something else when

  • Large arrays: n(n − 1)/2 comparisons on every input, so 100,000 values always take about 5 billion comparisons.
  • Nearly sorted data: unlike insertion or bubble sort, selection sort gets no faster when the input is almost in order.
  • You need a stable sort: use insertion sort, merge sort or your language's built-in stable sort.

Common mistakes and bugs

  1. 1.Swapping every time a smaller value is found

    Swapping inside the inner loop, instead of remembering the index m and swapping once at the end of the pass, still sorts but can make O(n²) swaps. It throws away the one advantage selection sort has.

  2. 2.Remembering the value instead of the index

    If you track min_value rather than m, you no longer know where that value sits, so you cannot swap it into place. Keep the index; read the value as a[m].

  3. 3.Starting the inner loop at 0 or at i

    Starting at 0 rescans the sorted part and can pick an already-placed value. Starting at i just wastes one comparison of a[i] with itself. The inner loop starts at i + 1.

  4. 4.Assuming it is stable

    The swap jumps across other values. In [5, 5, 2], the first pass swaps the first 5 with the 2, so the two 5s end up in reverse order. Sorting records by a second key after a first will scramble the first order.

  5. 5.Using <= in the comparison

    a[j] <= a[m] picks the last of several equal minimums instead of the first. It is still correct, but it can make extra, useless swaps on data with duplicates.

Interview questions

Try answering before you open the model answer.

Q1 How many swaps does selection sort make, and why does that matter?

Model answer: At most n − 1: one per pass, and none when the smallest value is already in place. Insertion and bubble sort make one move per inversion, up to n(n − 1)/2. When writing is expensive, such as on flash memory, that difference matters more than the comparisons.

Q2 Why is selection sort not stable? Can you make it stable?

Model answer: The swap moves a[i] to wherever the minimum was, jumping over equal values. In [5, 5, 2] the first 5 ends up behind the second. To make it stable, insert the minimum at position i by shifting the values in between right, instead of swapping. That keeps order but costs up to O(n²) moves.

Q3 Compare selection sort and insertion sort.

Model answer: Both are O(n²) and in place. Selection sort always makes n(n − 1)/2 comparisons and at most n − 1 swaps, and it is not stable. Insertion sort adapts, from n − 1 comparisons on sorted input up to n(n − 1)/2, is stable, and is usually faster overall. Choose selection sort only when writes dominate the cost.

Q4 Find the k smallest values of an array.

Model answer: Running k passes of selection sort gives them in order in O(n·k), fine for very small k. For larger k use a max-heap of size k, O(n log k), or quickselect to find the k-th smallest and partition around it, O(n) on average, then sort those k values if order matters.

Q5 How is heap sort related to selection sort?

Model answer: Heap sort is selection sort with a better way to find the extreme value. Instead of scanning the unsorted part in O(n), it keeps that part as a binary heap, so each extraction costs O(log n). The selection idea stays the same, but the total drops from O(n²) to O(n log n).

Frequently asked questions

What is the time complexity of selection sort?

O(n²) in the best, average and worst case. Every pass scans the whole unsorted part to find its minimum, so it always makes n(n − 1)/2 comparisons, even on sorted input. Only the number of swaps depends on the data, and it is at most n − 1. Extra space is O(1).

Is selection sort stable?

No. Swapping the minimum into place can jump it over a value equal to the one it swaps with. In [5, 5, 2], the first pass swaps the first 5 with the 2, so the two 5s change order. A variant that shifts values instead of swapping is stable, but it does far more writes.

Why is selection sort used if it is always O(n²)?

Because it makes at most n − 1 swaps. When each write is costly, such as on flash memory with limited write cycles or when physically moving items, a sort with few moves can be the better trade even with many comparisons. It is also short, in place and easy to get right.

Does selection sort get faster on sorted input?

No, and that is its main weakness. It cannot know a value is the smallest without comparing it with every remaining value, so sorted input still costs n(n − 1)/2 comparisons. The only saving is that no swaps are needed. Insertion sort and bubble sort with an early exit finish sorted input in n − 1 comparisons.

What is the difference between selection sort and bubble sort?

Both build the sorted part one value per pass. Bubble sort carries the largest value to the end by swapping neighbours, possibly many times per pass. Selection sort finds the smallest value first and swaps once per pass. Bubble sort is stable and can stop early on sorted data; selection sort makes far fewer swaps.

Crio Software Development

Go from watching algorithms to using them

Crio's Software Development Fellowship has you practise data structures and algorithms by building real projects, the way they come up at work and in interviews. Start with a free trial session.

Explore the program

Free trial · No credit card required

Sources

  1. Sedgewick and Wayne, Algorithms (4th ed., Addison-Wesley, 2011)
    Section 2.1, Elementary sorts: selection sort uses about n²/2 compares and n exchanges.
  2. Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed., 1998)
    Section 5.2.3, Sorting by selection, including heapsort.
  3. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (3rd ed., MIT Press, 2009)
    Exercise 2.2-2 (selection sort) and Chapter 6, Heapsort.

The animation, the worked example and the step counts are all generated by one implementation of selection sort, which is unit-tested against an independent version on edge cases and hundreds of random inputs. The Python, Java and JavaScript code is the exact code shown above, run on the same cases.

Last updated:

More algorithms, visualized

Every page runs real, tested code and lets you step through it with your own input.

All algorithms