package main
import (
"fmt"
"testing"
"algo/metrics"
)
func ratedLib(n int) []Item {
s := make([]Item, n)
for i := range s {
s[i] = Item{
ID: i + 1,
Title: fmt.Sprintf("%06d", i),
Rating: MinRating + (i*37)%(MaxRating-MinRating+1),
Year: MinYear + (i*17)%(MaxYear-MinYear+1),
}
}
return s
}
func TestCountingSortOrders(t *testing.T) {
for _, n := range []int{0, 1, 2, 3, 1000} {
var c, m metrics.Counter
out := CountingSortByRating(ratedLib(n), &c, &m)
if len(out) != n {
t.Fatalf("n=%d: got %d items", n, len(out))
}
if !isSortedByRating(out) {
t.Fatalf("n=%d: not sorted by Rating", n)
}
}
}
// THE HEADLINE. Not "fewer comparisons" — none at all. If this number is ever
// non-zero, the implementation has stopped being a counting sort.
func TestCountingSortMakesZeroComparisons(t *testing.T) {
var c, m metrics.Counter
CountingSortByRating(ratedLib(10000), &c, &m)
if c.N() != 0 {
t.Errorf("comparisons = %d, want exactly 0", c.N())
}
// And exactly one move per item: each is placed once.
if m.N() != 10000 {
t.Errorf("moves = %d, want exactly %d (one per item)", m.N(), 10000)
}
}
// Counting sort must be STABLE — and radix depends on it, which the next test
// makes concrete.
func TestCountingSortIsStable(t *testing.T) {
in := []Item{
{ID: 1, Rating: 5}, {ID: 2, Rating: 3}, {ID: 3, Rating: 5},
{ID: 4, Rating: 3}, {ID: 5, Rating: 5},
}
var c, m metrics.Counter
out := CountingSortByRating(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))
}
}
}
func TestRadixSortOrders(t *testing.T) {
for _, n := range []int{0, 1, 2, 3, 5000} {
var c, m metrics.Counter
out := RadixSortByYear(ratedLib(n), &c, &m)
if !isSortedByYear(out) {
t.Fatalf("n=%d: not sorted by Year", n)
}
if c.N() != 0 {
t.Errorf("n=%d: comparisons = %d, want 0", n, c.N())
}
}
}
// STABILITY AS A CORRECTNESS PRECONDITION, asserted.
//
// Radix sort works by sorting on the least significant digit first and relying
// on every later pass to PRESERVE that order. Take the stability away and the
// algorithm does not get untidy — it produces the wrong answer, with exactly
// the same number of comparisons and moves.
func TestRadixIsWrongWithAnUnstableInnerPass(t *testing.T) {
in := ratedLib(1000)
var c1, m1 metrics.Counter
good := RadixSortByYear(in, &c1, &m1)
if !isSortedByYear(good) {
t.Fatal("the stable version must sort correctly")
}
var c2, m2 metrics.Counter
bad := RadixSortByYearUnstable(in, &c2, &m2)
if isSortedByYear(bad) {
t.Fatal("the unstable version came out sorted — the demonstration has stopped working")
}
// Same work, different answer. That is the whole point.
if m1.N() != m2.N() || c1.N() != c2.N() {
t.Errorf("the two runs did different amounts of work (%d/%d vs %d/%d); "+
"they should differ only in correctness", c1.N(), m1.N(), c2.N(), m2.N())
}
t.Logf("identical work — %d comparisons, %d moves — and only one is correct", c1.N(), m1.N())
}
