Selection Sort Algorithm

The selection sort algorithm sorts a list by repeatedly finding the smallest remaining number and swapping it into place at the front. It is simple, uses no extra memory and makes very few swaps, but it always does O(n²) comparisons. Step through it below, then read how it works and when to use it.

What is Selection Sort?

Selection Sort splits the list into a sorted part (left) and an unsorted part (right). On every pass it selects the smallest element of the unsorted part and swaps it into the first position of the unsorted part.

Key insight: Selection Sort never makes more than n - 1 swaps. That makes it useful when writing to memory is expensive, even though the number of comparisons is always about n²/2.

Selection Sort Time Complexity

Measure	Value
Best case	O(n²)
Average case	O(n²)
Worst case	O(n²)
Space	O(1)
Stable	No

For a formal definition and complexity analysis, see the NIST Dictionary of Algorithms and Data Structures entry for selection sort.

Algorithm Steps

1. Treat the whole list as unsorted.
2. Scan the unsorted part to find the smallest element.
3. Swap that element with the first element of the unsorted part.
4. Grow the sorted part by one position.
5. Repeat until only one element is left unsorted.

Advantages and Disadvantages

Advantages

• Simple to understand and implement
• Sorts in place with O(1) extra memory
• Makes at most n - 1 swaps, the fewest of the basic sorts
• Performance does not depend on the input order, which is predictable

Disadvantages

• Always O(n²) comparisons, even on a sorted list
• Not stable: swapping can change the order of equal elements
• Much slower than O(n log n) algorithms on large lists

Real-World Applications

• Systems where memory writes or swaps are costly (for example flash memory)
• Small lists where simplicity is more important than speed
• Teaching the idea of an invariant: the left part is always sorted and final

When to Use Selection Sort

Choose it when swaps are expensive and the list is small. For general use, prefer Insertion Sort for small lists or Merge/Quick Sort for large ones.

Selection Sort Implementation

Python

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        m = i                          # index of the smallest so far
        for j in range(i + 1, n):
            if arr[j] < arr[m]:
                m = j
        if m != i:
            arr[i], arr[m] = arr[m], arr[i]
    return arr

JavaScript

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let m = i;                         // index of the smallest so far
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[m]) m = j;
    }
    if (m !== i) [arr[i], arr[m]] = [arr[m], arr[i]];
  }
  return arr;
}

FAQ

Is selection sort stable?

No. The swap that moves the minimum to the front can jump an element past an equal one. For example, sorting [4a, 4b, 1] swaps 4a with 1 and gives [1, 4b, 4a], so the two 4s change order.

Why is selection sort O(n²) even on a sorted list?

Each pass must scan the whole unsorted part to be sure it has found the minimum, and it has no early-exit check. That is about n²/2 comparisons whatever the input order.

Selection sort vs bubble sort: which is better?

Both are O(n²), but selection sort makes at most n − 1 swaps, while Bubble Sort can make up to n(n − 1)/2. When writes are expensive, selection sort wins; on nearly sorted data, bubble sort with early exit (or better, Insertion Sort) is faster.

---

More Sorting Algorithms

• Bubble Sort
• Insertion Sort
• Heap Sort
• Merge Sort