package main
import (
"fmt"
"math"
"testing"
"algo/metrics"
)
func sortedLibN(n int) []Item {
s := make([]Item, n)
for i := range s {
s[i] = Item{ID: i + 1, Title: fmt.Sprintf("%06d", i)}
}
return s
}
func reverseLibN(n int) []Item {
s := make([]Item, n)
for i := range s {
s[i] = Item{ID: i + 1, Title: fmt.Sprintf("%06d", n-i)}
}
return s
}
func TestDivideAndConquerSorts(t *testing.T) {
for _, n := range []int{0, 1, 2, 3, 10, 257} {
t.Run(fmt.Sprintf("merge n=%d", n), func(t *testing.T) {
in := shuffledLib(n)
var c, m metrics.Counter
out := MergeSort(in, &c, &m)
if len(out) != n {
t.Fatalf("returned %d items, want %d", len(out), n)
}
if !isSortedByTitle(out) {
t.Fatal("not sorted")
}
// MergeSort must NOT modify its input.
if n > 2 && isSortedByTitle(in) {
t.Error("the input was modified — MergeSort must return a new slice")
}
})
for _, q := range []struct {
name string
fn func([]Item, *metrics.Counter, *metrics.Counter)
}{{"naive", QuickSortNaive}, {"median3", QuickSortMedian3}, {"random", QuickSortRandom}} {
t.Run(fmt.Sprintf("quick-%s n=%d", q.name, n), func(t *testing.T) {
data := shuffledLib(n)
var c, m metrics.Counter
q.fn(data, &c, &m)
if !isSortedByTitle(data) {
t.Fatal("not sorted")
}
})
}
}
}
// Merge sort is STABLE. Bubble and insertion were too (lesson 7); merge is the
// first O(n log n) sort that keeps the property.
func TestMergeSortIsStable(t *testing.T) {
in := []Item{
{ID: 1, Title: "b"}, {ID: 2, Title: "a"}, {ID: 3, Title: "b"},
{ID: 4, Title: "a"}, {ID: 5, Title: "b"},
}
var c, m metrics.Counter
out := MergeSort(in, &c, &m)
want := []int{2, 4, 1, 3, 5}
for i, id := range want {
if out[i].ID != id {
t.Fatalf("position %d has ID %d, want %d — not stable (got %v)", i, out[i].ID, id, ids(out))
}
}
}
// Quicksort is NOT stable, and this asserts the defect so it stays visible —
// the same shape as lesson 7's selection-sort test.
func TestQuickSortIsNotStable(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"}, {ID: 6, Title: "a"},
}
var c, m metrics.Counter
QuickSortMedian3(data, &c, &m)
if !isSortedByTitle(data) {
t.Fatal("not sorted")
}
stable := []int{2, 4, 6, 1, 3, 5}
same := true
for i, id := range stable {
if data[i].ID != id {
same = false
}
}
if same {
t.Fatalf("quicksort came out stable (%v) — surprising; check what it cost", ids(data))
}
t.Logf("quicksort is NOT stable: got %v, a stable sort would give %v", ids(data), stable)
}
// MERGE SORT'S CEILING. n*ceil(log2 n) is the bound; a correct merge sort is
// comfortably under it on every input, INCLUDING the sorted and reverse cases
// that destroy a naive quicksort.
func TestMergeSortIsNLogNOnEveryInput(t *testing.T) {
const n = 1024
ceiling := int64(float64(n) * math.Ceil(math.Log2(n)))
for _, tc := range []struct {
name string
in []Item
}{
{"shuffled", shuffledLib(n)},
{"sorted", sortedLibN(n)},
{"reverse", reverseLibN(n)},
} {
t.Run(tc.name, func(t *testing.T) {
var c, m metrics.Counter
MergeSort(tc.in, &c, &m)
if c.N() > ceiling {
t.Errorf("%d comparisons, ceiling n*ceil(log2 n) = %d", c.N(), ceiling)
}
})
}
}
// THE BLOW-UP, ASSERTED. A first-element pivot on sorted input is not "a bit
// slower" — it is exactly the quadratic count, the same n(n-1)/2 as lesson 7's
// elementary sorts. This test exists so the failure mode cannot be forgotten.
func TestNaivePivotIsQuadraticOnSortedInput(t *testing.T) {
const n = 512
want := int64(n * (n - 1) / 2)
var c, m metrics.Counter
QuickSortNaive(sortedLibN(n), &c, &m)
if c.N() != want {
t.Errorf("comparisons on sorted input = %d, want exactly %d (the quadratic count)", c.N(), want)
}
}
// And the fix, asserted for the case it actually fixes.
func TestMedian3RescuesSortedInput(t *testing.T) {
const n = 512
quadratic := int64(n * (n - 1) / 2)
var c, m metrics.Counter
QuickSortMedian3(sortedLibN(n), &c, &m)
if c.N() > quadratic/10 {
t.Errorf("median-of-three on sorted input used %d comparisons; expected far below %d", c.N(), quadratic/10)
}
}
