diff options
Diffstat (limited to 'sort')
| -rw-r--r-- | sort/insertion.go | 2 | ||||
| -rw-r--r-- | sort/property_test.go | 110 | ||||
| -rw-r--r-- | sort/sort_test.go | 15 |
3 files changed, 123 insertions, 4 deletions
diff --git a/sort/insertion.go b/sort/insertion.go index a6b3c85..d869a7c 100644 --- a/sort/insertion.go +++ b/sort/insertion.go @@ -5,7 +5,7 @@ import ( ) func Insertion[V ds.Number](a ds.ArrayList[V]) ds.ArrayList[V] { - for i, _ := range a { + for i := range a { for j := i; j > 0; j-- { if a[j] > a[j-1] { break diff --git a/sort/property_test.go b/sort/property_test.go new file mode 100644 index 0000000..1f3dd88 --- /dev/null +++ b/sort/property_test.go @@ -0,0 +1,110 @@ +package sort + +import ( + "math/rand" + "testing" + quickcheck "testing/quick" // aliased: this package already has a quick() sort + + "codeberg.org/snonux/algorithms/ds" +) + +// This file provides property-based verification for every sort. Unlike the +// size-driven tests in sort_test.go, which only assert a.Sorted(), these tests +// also assert the *permutation* invariant: the output must contain exactly the +// same elements as the input. A buggy sort that drops or duplicates an element +// while still returning an ordered slice would pass a Sorted()-only check but +// fail here. Together, "ordered" + "permutation of the input" is the full +// functional-correctness postcondition proven on paper in docs/verification.md. + +// sortUnderTest is the shared signature of every sort in this package. An +// ds.ArrayList[int] shares []int's representation, so the property helpers +// convert between them for free. +type sortUnderTest func(ds.ArrayList[int]) ds.ArrayList[int] + +// allSorts lists every sort to verify, keyed by name for readable subtests. +func allSorts() map[string]sortUnderTest { + return map[string]sortUnderTest{ + "Selection": Selection[int], + "Insertion": Insertion[int], + "Shell": Shell[int], + "Merge": Merge[int], + "BottomUpMerge": BottomUpMerge[int], + "ParallelMerge": ParallelMerge[int], + "Quick": Quick[int], + "ParallelQuick": ParallelQuick[int], + "Quick3Way": Quick3Way[int], + } +} + +// sameMultiset reports whether b is a permutation of a: equal length and equal +// element multiplicities. This is the invariant the Sorted()-only tests miss. +func sameMultiset(a, b []int) bool { + if len(a) != len(b) { + return false + } + counts := make(map[int]int, len(a)) + for _, v := range a { + counts[v]++ + } + for _, v := range b { + counts[v]-- + if counts[v] < 0 { + return false // b has an element a doesn't have (enough of) + } + } + // Equal lengths plus no negative count implies the multisets match exactly. + return true +} + +// sortedPermutationOf runs sort on a copy of orig and checks both invariants: +// the result is ordered and is a permutation of orig. orig is not mutated. +func sortedPermutationOf(sort sortUnderTest, orig []int) bool { + work := make([]int, len(orig)) + copy(work, orig) + out := sort(ds.ArrayList[int](work)) + return out.Sorted() && sameMultiset(orig, out) +} + +// TestPropertyOrderedPermutation uses testing/quick to throw many randomly +// shaped small slices (arbitrary values, lengths up to ~50) at each sort, +// asserting the ordered-permutation property on every trial. +func TestPropertyOrderedPermutation(t *testing.T) { + cfg := &quickcheck.Config{MaxCount: 2000} + for name, sort := range allSorts() { + name, sort := name, sort + t.Run(name, func(t *testing.T) { + t.Parallel() + prop := func(in []int) bool { return sortedPermutationOf(sort, in) } + if err := quickcheck.Check(prop, cfg); err != nil { + t.Errorf("%s violated ordered-permutation property: %v", name, err) + } + }) + } +} + +// TestPropertySizes exercises input sizes that cross the algorithms' internal +// thresholds: the len<=10 insertion-sort cutoffs, the len<1000 sequential +// fallbacks in the parallel sorts, and the odd-length merge clamp. The largest +// sizes (which drive the real goroutine fan-out) run only outside -short. +func TestPropertySizes(t *testing.T) { + sizes := []int{0, 1, 2, 10, 11, 100, 999, 1000, 1001} + if !testing.Short() { + sizes = append(sizes, 5000, 20001) + } + for name, sort := range allSorts() { + name, sort := name, sort + t.Run(name, func(t *testing.T) { + t.Parallel() + rng := rand.New(rand.NewSource(1)) + for _, n := range sizes { + in := make([]int, n) + for i := range in { + in[i] = rng.Intn(50) - 25 // small range ⇒ many duplicates + } + if !sortedPermutationOf(sort, in) { + t.Errorf("%s failed ordered-permutation at size %d", name, n) + } + } + }) + } +} diff --git a/sort/sort_test.go b/sort/sort_test.go index b632be8..ee49893 100644 --- a/sort/sort_test.go +++ b/sort/sort_test.go @@ -15,10 +15,7 @@ const maxLength int = 1000000 const factor int = 100 const maxSlowLength int = 100000 -var arrayListCache map[string]ds.ArrayList[int] - type sortAlgorithm[V ds.Number] func(ds.ArrayList[V]) ds.ArrayList[V] -type sortAlgorithmInt func([]int) []int func TestSleepSort(t *testing.T) { a := ds.NewRandomArrayList[int](10, 10) @@ -153,8 +150,17 @@ func BenchmarkShuffleSort(b *testing.B) { } */ +// shortMaxLength caps the largest input size exercised under `go test -short` +// (used by `make verify`, which runs under the race detector where the +// million-element cases would be far too slow). The full range still runs in a +// plain `make test`. +const shortMaxLength int = 10000 + func test[V ds.Number](sort sortAlgorithm[V], l int, t *testing.T) { cb := func(t *testing.T) { + if testing.Short() && l > shortMaxLength { + t.Skipf("skipping size %d in -short mode", l) + } t.Parallel() a := ds.NewRandomArrayList[V](l, -1) a = sort(a) @@ -167,6 +173,9 @@ func test[V ds.Number](sort sortAlgorithm[V], l int, t *testing.T) { func testShuffleSort[V ds.Number](sort sortAlgorithm[V], l int, t *testing.T) { cb := func(t *testing.T) { + if testing.Short() && l > shortMaxLength { + t.Skipf("skipping size %d in -short mode", l) + } t.Parallel() a := sort(ds.NewAscendingArrayList[V](l)) if a.Sorted() { |