Sorting

Selection Sort

Repeatedly scan the unsorted suffix for its minimum element, then swap that minimum into the next position. After i passes, the prefix arr[0..i-1] is the sorted order statistics.

Algorithm

Canonical input arr=(5 1 4 2 8) finishes after four passes; the final array is [1, 2, 4, 5, 8].

Basic Implementation

basic.sql 
.mode list
.headers off
WITH RECURSIVE sel(p, vals) AS (
  SELECT 0, json_array(5, 1, 4, 2, 8)
  UNION ALL
  SELECT p + 1, json_set(
    json_set(vals,
      '$[' || p || ']',
      json_extract(vals, '$[' ||
        (SELECT key FROM json_each(sel.vals)
         WHERE key >= sel.p
         ORDER BY CAST(value AS INTEGER) ASC, key ASC LIMIT 1) || ']')),
    '$[' ||
      (SELECT key FROM json_each(sel.vals)
       WHERE key >= sel.p
       ORDER BY CAST(value AS INTEGER) ASC, key ASC LIMIT 1) || ']',
    json_extract(vals, '$[' || p || ']'))
  FROM sel WHERE p < 4
)
SELECT '[' || GROUP_CONCAT(value, ', ') || ']'
FROM json_each((SELECT vals FROM sel ORDER BY p DESC LIMIT 1));

Complexity

  • Time: O(n^2)
  • Space: O(n) for the per-step JSON snapshot in the recursive CTE

Implementation notes

  • SQL: the array is held as a JSON1 array and a WITH RECURSIVE sel(p, vals) CTE runs one pass per row. Inside each step a scalar subquery over json_each(sel.vals) finds the minimum index in [p..n-1], and a paired json_set swap moves that minimum into vals[p].
  • The ORDER BY CAST(value AS INTEGER) ASC, key ASC LIMIT 1 tie-breaker keeps the result deterministic when two slots tie on value; the canonical lesson input has no ties, so the rule fires but produces the same result either way.
  • Like sort-bubble, the final GROUP_CONCAT(value, ', ') over the last snapshot emits [1, 2, 4, 5, 8] so the printed output matches the language-neutral lesson spec exactly.
min pick Each pass scans `arr[i..n-1]` to find the index of the smallest element.
settled prefix After pass `i`, `arr[0..i]` is the sorted prefix and never moves again.