Sorting

Bubble Sort

Repeatedly walk the array, swapping adjacent out-of-order pairs. After each pass the largest unsorted element bubbles to its final position; stop once n - 1 passes have run.

Algorithm

Canonical input arr=(5 1 4 2 8) finishes after four outer passes and yields [1, 2, 4, 5, 8].

Basic Implementation

basic.sql 
.mode list
.headers off
WITH RECURSIVE bubble(p, j, vals) AS (
  SELECT 0, 0, json_array(5, 1, 4, 2, 8)
  UNION ALL
  SELECT
    CASE WHEN j + 1 = 4 THEN p + 1 ELSE p END,
    CASE WHEN j + 1 = 4 THEN 0 ELSE j + 1 END,
    CASE WHEN CAST(json_extract(vals, '$[' || j || ']') AS INTEGER)
            > CAST(json_extract(vals, '$[' || (j + 1) || ']') AS INTEGER)
         THEN json_set(
                json_set(vals, '$[' || j || ']',
                         json_extract(vals, '$[' || (j + 1) || ']')),
                '$[' || (j + 1) || ']',
                json_extract(vals, '$[' || j || ']'))
         ELSE vals
    END
  FROM bubble
  WHERE p < 4
)
SELECT '[' || GROUP_CONCAT(value, ', ') || ']'
FROM json_each((SELECT vals FROM bubble ORDER BY p DESC, j 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 encoded as a JSON1 json_array(5, 1, 4, 2, 8) so json_set / json_extract can express the swap declaratively. A WITH RECURSIVE bubble(p, j, vals) CTE advances j from 0..3 inside each pass and increments p when j wraps; each step rewrites vals to swap the pair when the left element is greater.
  • Native SQLite tables have no in-place row exchange, so the JSON array is the closest beginner-readable substitute for an imperative arr[j], arr[j+1] = arr[j+1], arr[j]. JSON1 is built into SQLite 3.45.1 and needs no .load.
  • The final SELECT '[' || GROUP_CONCAT(value, ', ') || ']' FROM json_each(...) expands the final array snapshot into the canonical bracketed output [1, 2, 4, 5, 8] so the printed result matches every other DSA book in the cohort.
adjacent swaps A single pass compares each adjacent pair `arr[j], arr[j+1]` and swaps when out of order.
fixed-pass loop SQLite's `WITH RECURSIVE` cannot consult prior arm rows for a "swapped?" flag, so the simulation runs `n - 1` passes unconditionally. The early-termination optimization is a real-language flourish; the small fixed input still settles after three swaps.