From 7f87861624a1c5feb5523479db1c242a98f659b2 Mon Sep 17 00:00:00 2001
From: Paul Buetow <paul@buetow.org>
Date: Tue, 14 Jul 2020 22:41:16 +0100
Subject: add shellsort and refactor a bit

---
 ds/comparer.go    |  3 +--
 ds/integer.go     | 43 +++++++++++++++++++++++++++++++++++++------
 sort/sort_test.go | 51 +++++++++++++++++++++++++++++++++++++++------------
 3 files changed, 77 insertions(+), 20 deletions(-)

diff --git a/ds/comparer.go b/ds/comparer.go
index 737ad1b..168ec19 100644
--- a/ds/comparer.go
+++ b/ds/comparer.go
@@ -4,6 +4,5 @@ type Comparer interface {
 	LowerThan(a Comparer) bool
 	HigherThan(a Comparer) bool
 	Equals(a Comparer) bool
+	IntVal() int
 }
-
-type CompareList []Comparer
diff --git a/ds/integer.go b/ds/integer.go
index 69ee0aa..b8026da 100644
--- a/ds/integer.go
+++ b/ds/integer.go
@@ -1,25 +1,56 @@
 package ds
 
-import "math/rand"
+import (
+	"fmt"
+	"math/rand"
+)
 
-type Integer int
+type Integer struct {
+	val int
+}
 
 func RandomIntegers(length, max int) []Comparer {
 	a := make([]Comparer, length)
 	for i := 0; i < length; i++ {
-		a[i] = Integer(rand.Intn(max))
+		a[i] = Integer{rand.Intn(max)}
 	}
 	return a
 }
 
+func SortedIntegers(length int) []Comparer {
+	a := make([]Comparer, length)
+	for i := 0; i < length; i++ {
+		a[i] = Integer{i}
+	}
+	return a
+}
+
+func ReverseSortedIntegers(length int) []Comparer {
+	a := make([]Comparer, length)
+	j := length
+	for i := 0; i < length; i++ {
+		a[i] = Integer{j}
+		j--
+	}
+	return a
+}
+
+func (i Integer) String() string {
+	return fmt.Sprintf("%d", i.val)
+}
+
+func (i Integer) IntVal() int {
+	return i.val
+}
+
 func (i Integer) LowerThan(j Comparer) bool {
-	return i < j.(Integer)
+	return i.val < j.IntVal()
 }
 
 func (i Integer) HigherThan(j Comparer) bool {
-	return i > j.(Integer)
+	return i.val > j.IntVal()
 }
 
 func (i Integer) Equals(j Comparer) bool {
-	return i == j.(Integer)
+	return i.val == j.IntVal()
 }
diff --git a/sort/sort_test.go b/sort/sort_test.go
index 60f8aa3..9593cde 100644
--- a/sort/sort_test.go
+++ b/sort/sort_test.go
@@ -8,46 +8,73 @@ import (
 
 // Store results here to avoid compiler optimizations
 var benchResult []ds.Comparer
+var benchResultInt []int
 
 const maxLength int = 10000
 
 type sortAlgorithm func([]ds.Comparer) []ds.Comparer
+type sortAlgorithmInt func([]int) []int
 
-func TestSort(t *testing.T) {
+func TestSelectionSort(t *testing.T) {
 	for i := 1; i <= maxLength; i *= 10 {
-		test("Selection", i, Selection, t)
-		test("Insertion", i, Insertion, t)
+		test(Selection, i, t)
 	}
 }
 
-func BenchmarkSort(b *testing.B) {
+func TestInsertionSort(t *testing.T) {
 	for i := 1; i <= maxLength; i *= 10 {
-		benchmark("Insertion", i, Insertion, b)
+		test(Insertion, i, t)
 	}
+}
+
+func TestShellSort(t *testing.T) {
+	for i := 1; i <= maxLength; i *= 10 {
+		test(Shell, i, t)
+	}
+}
+
+func BenchmarkInsertionSort(b *testing.B) {
+	for i := 1; i <= maxLength; i *= 10 {
+		benchmark(Insertion, i, b)
+	}
+}
+
+func BenchmarkSelectionSort(b *testing.B) {
+	for i := 1; i <= maxLength; i *= 10 {
+		benchmark(Selection, i, b)
+	}
+}
+
+func BenchmarkShellSort(b *testing.B) {
 	for i := 1; i <= maxLength; i *= 10 {
-		benchmark("Selection", i, Selection, b)
+		benchmark(Shell, i, b)
 	}
 }
 
-func test(name string, length int, sort sortAlgorithm, t *testing.T) {
+func test(sort sortAlgorithm, length int, t *testing.T) {
 	cb := func(t *testing.T) {
 		t.Parallel()
-		a := ds.RandomIntegers(length, length)
+		a := makeIntegers(length, length)
 		a = sort(a)
 		if !Sorted(a) {
 			t.Errorf("Array not sorted: %v", a)
 		}
 	}
-	t.Run(fmt.Sprintf("Test%s%d", name, length), cb)
+	t.Run(fmt.Sprintf("%d", length), cb)
 }
 
-func benchmark(name string, length int, sort sortAlgorithm, b *testing.B) {
+func benchmark(sort sortAlgorithm, length int, b *testing.B) {
 	cb := func(b *testing.B) {
-		a := ds.RandomIntegers(length, length)
+		a := makeIntegers(length, length)
 		b.ResetTimer()
 		for i := 0; i < b.N; i++ {
 			benchResult = sort(a)
 		}
 	}
-	b.Run(fmt.Sprintf("Benchmark%s%d", name, length), cb)
+	b.Run(fmt.Sprintf("%d", length), cb)
+}
+
+func makeIntegers(length, max int) []ds.Comparer {
+	//return ds.ReverseSortedIntegers(length)
+	return ds.RandomIntegers(length, max)
 }
-- 
cgit v1.2.3