Sorting

Selection Sort

Repeatedly find the index of the smallest remaining element and swap it into the next "sorted prefix" slot. Unlike bubble sort, only one swap per pass.

Algorithm

Canonical input [5, 1, 4, 2, 8] sorts in two real swaps; the last two passes find minIdx == i and skip the swap.

Basic Implementation

basic.dart 
void main() {
  final arr = <int>[5, 1, 4, 2, 8];
  final n = arr.length;
  for (var i = 0; i < n - 1; i++) {
    var minIdx = i;
    for (var j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    if (minIdx != i) {
      final tmp = arr[i];
      arr[i] = arr[minIdx];
      arr[minIdx] = tmp;
    }
  }
  print(arr);
}

Complexity

  • Time: O(n^2) regardless of input order
  • Space: O(1)
  • Stable: no
  • Swaps: at most n-1

Implementation notes

  • Dart: skip the swap when minIdx == i to match the lesson spec's frame counts. Do not delegate to arr.sort().
  • The replay highlights j (scanning) versus minIdx (running minimum) distinctly, then animates the per-pass swap.
running minimum Track the index of the smallest value seen during a scan.