package main
import (
"fmt"
"testing"
"algo/metrics"
)
type sorter struct {
name string
fn func([]Item, *metrics.Counter, *metrics.Counter)
}
func allSorters() []sorter {
return []sorter{
{"bubble", BubbleSort},
{"selection", SelectionSort},
{"insertion", InsertionSort},
}
}
func shuffledLib(n int) []Item {
s := make([]Item, n)
for i := range s {
// A deterministic scramble: no rand, so every run is identical.
s[i] = Item{ID: i + 1, Title: fmt.Sprintf("%05d", (i*7919)%n)}
}
return s
}
func TestSortsProduceSortedOutput(t *testing.T) {
for _, s := range allSorters() {
t.Run(s.name, func(t *testing.T) {
for _, n := range []int{0, 1, 2, 3, 10, 257} {
data := shuffledLib(n)
var c, w metrics.Counter
s.fn(data, &c, &w)
for i := 1; i < len(data); i++ {
if data[i-1].Title > data[i].Title {
t.Fatalf("n=%d: not sorted at %d", n, i)
}
}
}
})
}
}
// STABILITY, and the fact that ONE OF THE THREE DOES NOT HAVE IT.
//
// A stable sort keeps equal Titles in their original relative order — visible
// only by watching the IDs. Bubble and insertion are stable: they only ever
// swap NEIGHBOURS, so two equal items can never cross.
//
// Selection sort is not, and cannot be made so without giving up the thing it
// is good at. It swaps across arbitrary distances, and that long-range swap can
// throw an equal item over another. That is the trade: the fewest swaps of the
// three, paid for with the order of equal keys.
func TestBubbleAndInsertionAreStable(t *testing.T) {
build := func() []Item {
return []Item{
{ID: 1, Title: "b"}, {ID: 2, Title: "a"}, {ID: 3, Title: "b"},
{ID: 4, Title: "a"}, {ID: 5, Title: "b"},
}
}
want := []int{2, 4, 1, 3, 5} // the a's in order 2,4; then the b's in order 1,3,5
for _, s := range []sorter{{"bubble", BubbleSort}, {"insertion", InsertionSort}} {
t.Run(s.name, func(t *testing.T) {
data := build()
var c, w metrics.Counter
s.fn(data, &c, &w)
for i, id := range want {
if data[i].ID != id {
t.Fatalf("position %d has ID %d, want %d — not stable (got %v)",
i, data[i].ID, id, ids(data))
}
}
})
}
}
// This one asserts the DEFECT, so it stays visible. If you ever make selection
// sort stable, this test tells you — and you should then check what it cost.
func TestSelectionSortIsNotStable(t *testing.T) {
data := []Item{
{ID: 1, Title: "b"}, {ID: 2, Title: "a"}, {ID: 3, Title: "b"},
{ID: 4, Title: "a"}, {ID: 5, Title: "b"},
}
var c, w metrics.Counter
SelectionSort(data, &c, &w)
stable := []int{2, 4, 1, 3, 5}
same := true
for i, id := range stable {
if data[i].ID != id {
same = false
}
}
if same {
t.Fatalf("selection sort came out stable (%v) — surprising; check what it cost in swaps", ids(data))
}
t.Logf("selection sort is NOT stable: got %v, a stable sort would give %v", ids(data), stable)
}
func ids(items []Item) []int {
out := make([]int, len(items))
for i, it := range items {
out[i] = it.ID
}
return out
}
// THE COUNTS ARE THE SPECIFICATION. These are not approximate: each algorithm
// has an exact comparison count on sorted input, and no algorithm may exceed
// the quadratic ceiling on any input.
func TestComparisonCountsAreExact(t *testing.T) {
const n = 100
ceiling := int64(n * (n - 1) / 2)
sortedLib := func() []Item {
s := make([]Item, n)
for i := range s {
s[i] = Item{ID: i + 1, Title: fmt.Sprintf("%05d", i)}
}
return s
}
t.Run("insertion on sorted input does exactly n-1", func(t *testing.T) {
var c, w metrics.Counter
InsertionSort(sortedLib(), &c, &w)
if c.N() != n-1 {
t.Errorf("comparisons = %d, want %d", c.N(), n-1)
}
if w.N() != 0 {
t.Errorf("swaps = %d, want 0 — sorted input needs no movement", w.N())
}
})
t.Run("selection always does exactly n(n-1)/2", func(t *testing.T) {
var c, w metrics.Counter
SelectionSort(sortedLib(), &c, &w)
if c.N() != ceiling {
t.Errorf("comparisons on SORTED input = %d, want %d — selection sort has no best case", c.N(), ceiling)
}
})
t.Run("selection does at most n-1 swaps", func(t *testing.T) {
var c, w metrics.Counter
SelectionSort(shuffledLib(n), &c, &w)
if w.N() > n-1 {
t.Errorf("swaps = %d, want at most %d", w.N(), n-1)
}
})
t.Run("nobody exceeds the quadratic ceiling", func(t *testing.T) {
for _, s := range allSorters() {
var c, w metrics.Counter
s.fn(shuffledLib(n), &c, &w)
if c.N() > ceiling {
t.Errorf("%s: %d comparisons, ceiling is %d", s.name, c.N(), ceiling)
}
}
})
}
