diff options
Diffstat (limited to 'sort')
| -rw-r--r-- | sort/sleep.go | 5 | ||||
| -rw-r--r-- | sort/sort_test.go | 17 |
2 files changed, 17 insertions, 5 deletions
diff --git a/sort/sleep.go b/sort/sleep.go index 3ca45b2..146ff3a 100644 --- a/sort/sleep.go +++ b/sort/sleep.go @@ -7,7 +7,10 @@ import ( ) func Sleep[V ds.Integer](a ds.ArrayList[V]) ds.ArrayList[V] { - sorted := ds.NewArrayList[V](len(a)) + // Start empty with capacity len(a): the received values are appended below. + // NewArrayList(len(a)) would create a slice of that *length* (all zeros) and + // the appends would then produce len(a) spurious leading zeros. + sorted := make(ds.ArrayList[V], 0, len(a)) numCh := make(chan V) var wg sync.WaitGroup diff --git a/sort/sort_test.go b/sort/sort_test.go index ee49893..4fd2a04 100644 --- a/sort/sort_test.go +++ b/sort/sort_test.go @@ -18,10 +18,19 @@ const maxSlowLength int = 100000 type sortAlgorithm[V ds.Number] func(ds.ArrayList[V]) ds.ArrayList[V] func TestSleepSort(t *testing.T) { - a := ds.NewRandomArrayList[int](10, 10) - a = Sleep(a) - if !a.Sorted() { - t.Errorf("Array not sorted: %v", a) + orig := ds.NewRandomArrayList[int](10, 10) + in := make([]int, len(orig)) + copy(in, orig) + + out := Sleep(orig) + if !out.Sorted() { + t.Errorf("Array not sorted: %v", out) + } + // Also require the output to be a permutation of the input: sortedness alone + // would not catch a dropped or duplicated value. (Exhaustive termination / + // deadlock guarantees for the coordination live in formal/tla/SleepSort.tla.) + if !sameMultiset(in, out) { + t.Errorf("Sleep sort output is not a permutation of input: in=%v out=%v", in, out) } } |