theGnaN Tech Hub
Interactive Algorithm Engine · GVLL

Selection Sort

Repeatedly find the smallest element in the unsorted portion and place it in the next sorted position.

Best Time
O(n²)
Quadratic
Average Time
O(n²)
Always scans suffix
Worst Time
O(n²)
n(n-1)/2 checks
Aux Space
O(1)
Constant memory
Stable
No (Standard)
Long-distance swaps
In-Place
Yes
Mutates input array

Input Controls & Presets

Presets:

GVLL Array Execution Plane

7 Elements · Pass 1 of 6

Target (i) Current Min Compare (j) Swap Sorted
[0]
5
idx 0
[1]
2
idx 1
[2]
4
idx 2
[3]
7
idx 3
[4]
3
idx 4
[5]
8
idx 5
[6]
6
idx 6
Initialization
Line 2

Initialized Selection Sort for 7 elements.

Outer loop will execute 6 passes to place elements into their sorted positions.

Live State Variables

n7
Python Source Engine
Sync Active
1def selection_sorta:
2 n = lena)
3 for i in rangen - 1:
4 min_idx = i
5 for j in rangei + 1, n:
6 if aj < amin_idx:
7 min_idx = j
8 if min_idx != i:
9 ai, amin_idx = amin_idx, ai]
Live TelemetryLine 2 / 9
Algorithm Phase:init
Active Pass:Pass 1 of 1
Sorted Elements:0 / 7
Comprehensive Guide

How Selection Sort Operates

A deep mathematical and architectural breakdown of the algorithm's invariants, complexity derivations, and edge cases.

The Two-Subarray Invariant

At every iteration i, the array is conceptually partitioned into two distinct segments:

1. Sorted Prefix Subarray

Indices 0 to i - 1

Contains the smallest i elements of the entire array in permanently sorted, non-decreasing order. These elements are never revisited.

2. Unsorted Suffix Subarray

Indices i to n - 1

Contains the remaining elements. The inner loop systematically scans this suffix to locate its minimum element, which is then swapped into position i.

Mathematical Time Complexity Derivation

Regardless of the initial arrangement of elements — whether sorted, reverse-sorted, or completely random — Selection Sort executes a deterministic number of comparisons:

// Total Comparisons Formula
C(n) = (n - 1) + (n - 2) + (n - 3) + ... + 2 + 1
C(n) = n(n - 1) / 2 = O(n²)

Because the algorithm must inspect every element in the unsorted suffix to be sure it has found the true minimum, the best-case, average-case, and worst-case comparison counts are identical: exactly O(n²).

Why Standard Selection Sort is Unstable

A sorting algorithm is stable if elements with identical keys maintain their original relative order.

Standard Selection Sort is unstable because long-range swaps can jump an element over identical keys.

Initial: [4a, 5, 4b, 2]
Min is 2: swap 4a with 2
After: [2, 5, 4b, 4a] → 4b now precedes 4a!

The Primary Strength: Minimal Writes

While Selection Sort has quadratic comparisons, it performs at most n - 1 memory writes (swaps).

In comparison, Bubble Sort and Insertion Sort can perform up to O(n²) writes.

Practical Use Case: Ideal for systems where auxiliary memory write cycles are expensive or limited (e.g. Flash EEPROM, solid-state embedded sensors).