Selection Sort — VisualAlgorithms Docs

How it works

Selection Sort scans the unsorted region for the minimum element and swaps it into the next sorted position. It repeats, growing the sorted prefix by one element per pass.

It always performs the same number of comparisons regardless of input order, and at most n-1 swaps total.

Implementation

      
 function selectionSort(arr, stats) {
  const n = arr.length;
  const sorted = new Set();
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      compare(minIdx, j, {
        sorted
      });
      if (arr[j] < arr[minIdx]) minIdx = j;
    }
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
      swap(i, minIdx, {
        sorted
      });
    }
    markSorted(i);
    checkpoint(i, n - 1);
  }
  markSorted(n - 1);
}
 from types import SimpleNamespace

def selectionSort(arr, stats):
    sorted = set()
    for i in range((n - 1)):
        minIdx = i
        for j in range((i + 1), n):
            compare(minIdx, j, SimpleNamespace(sorted=sorted))
            if (arr[j] < arr[minIdx]):
                minIdx = j
        if (minIdx != i):
            arr[i], arr[minIdx] = arr[minIdx], arr[i]
            swap(i, minIdx, SimpleNamespace(sorted=sorted))
        markSorted(i)
        checkpoint(i, (n - 1))
    markSorted((n - 1))
 #include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    int sorted = 0;
    for(int i=0; i<(n - 1); i++) {
        int minIdx = i;
        for(int j=(i + 1); j<n; j++) {
            compare(minIdx, j, {sorted: sorted});
            if((arr[j] < arr[minIdx])) {
                minIdx = j;
            }
        }
        if((minIdx != i)) {
            std::swap(arr[i], arr[minIdx]);
            swap(i, minIdx, {sorted: sorted});
        }
        markSorted(i);
        checkpoint(i, (n - 1));
    }
    markSorted((n - 1));
} public void Sort(int[] arr, int n, dynamic stats) {
    int sorted = 0;
    for(int i=0; i<(n - 1); i++) {
        int minIdx = i;
        for(int j=(i + 1); j<n; j++) {
            compare(minIdx, j, {sorted: sorted});
            if((arr[j] < arr[minIdx])) {
                minIdx = j;
            }
        }
        if((minIdx != i)) {
            { int _t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = _t; }
            swap(i, minIdx, {sorted: sorted});
        }
        markSorted(i);
        checkpoint(i, (n - 1));
    }
    markSorted((n - 1));
} #include <stdio.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    int sorted = 0;
    for(int i=0; i<(n - 1); i++) {
        int minIdx = i;
        for(int j=(i + 1); j<n; j++) {
            compare(minIdx, j, {sorted: sorted});
            if((arr[j] < arr[minIdx])) {
                minIdx = j;
            }
        }
        if((minIdx != i)) {
            { int _t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = _t; }
            swap(i, minIdx, {sorted: sorted});
        }
        markSorted(i);
        checkpoint(i, (n - 1));
    }
    markSorted((n - 1));
} 

Advantages

Minimal number of writes (at most n-1 swaps) — useful when writes are expensive.
Simple and in-place.

Disadvantages

Always O(n^2) comparisons, even on sorted input — not adaptive.
Not stable in its classic form.

When to use it

Use it only when the cost of writing/moving elements dominates and the array is small.