From e858efc16960b86175d655add938acd3f1edd13e Mon Sep 17 00:00:00 2001
From: Paul Buetow <paul@buetow.org>
Date: Fri, 17 Jul 2020 09:58:23 +0100
Subject: shuffle sort works

---
 ds/integer.go     | 12 ++++++------
 sort/shuffle.go   | 16 +++++++---------
 sort/sort_test.go |  9 +++++++--
 3 files changed, 20 insertions(+), 17 deletions(-)

diff --git a/ds/integer.go b/ds/integer.go
index 336a941..04fee3e 100644
--- a/ds/integer.go
+++ b/ds/integer.go
@@ -9,24 +9,24 @@ type Integer struct {
 	val int
 }
 
-func RandomIntegers(length, max int) []Comparer {
-	a := make([]Comparer, length)
+func RandomIntegers(length, max int) ArrayList {
+	a := make(ArrayList, length)
 	for i := 0; i < length; i++ {
 		a[i] = Integer{rand.Intn(max)}
 	}
 	return a
 }
 
-func SortedIntegers(length int) []Comparer {
-	a := make([]Comparer, length)
+func SortedIntegers(length int) ArrayList {
+	a := make(ArrayList, length)
 	for i := 0; i < length; i++ {
 		a[i] = Integer{i}
 	}
 	return a
 }
 
-func ReverseSortedIntegers(length int) []Comparer {
-	a := make([]Comparer, length)
+func ReverseSortedIntegers(length int) ArrayList {
+	a := make(ArrayList, length)
 	j := length
 	for i := 0; i < length; i++ {
 		a[i] = Integer{j}
diff --git a/sort/shuffle.go b/sort/shuffle.go
index 040456b..9c6f5b9 100644
--- a/sort/shuffle.go
+++ b/sort/shuffle.go
@@ -2,23 +2,21 @@ package sort
 
 import (
 	"algorithms/ds"
+	"math/rand"
 )
 
 func Shuffle(a ds.ArrayList) ds.ArrayList {
 	length := len(a)
+
 	for i := 0; i < length; i++ {
-		min := i
-		for j := i + 1; j < length; j++ {
-			if a[min].Higher(a[j]) {
-				min = j
-			}
-		}
-		if min == i {
+		r := length - rand.Intn(length-i) - 1
+		if r == i {
 			continue
 		}
 		tmp := a[i]
-		a[i] = a[min]
-		a[min] = tmp
+		a[i] = a[r]
+		a[r] = tmp
 	}
+
 	return a
 }
diff --git a/sort/sort_test.go b/sort/sort_test.go
index d8250c4..ad75fff 100644
--- a/sort/sort_test.go
+++ b/sort/sort_test.go
@@ -34,7 +34,7 @@ func TestShellSort(t *testing.T) {
 }
 
 func TestShuffleSort(t *testing.T) {
-	for i := 1; i <= maxLength; i *= 10 {
+	for i := 10; i <= maxLength; i *= 10 {
 		testShuffle(Shuffle, i, t)
 	}
 }
@@ -57,6 +57,12 @@ func BenchmarkShellSort(b *testing.B) {
 	}
 }
 
+func BenchmarkShuffleSort(b *testing.B) {
+	for i := 1; i <= maxLength; i *= 10 {
+		benchmark(Shuffle, i, b)
+	}
+}
+
 func test(sort sortAlgorithm, length int, t *testing.T) {
 	cb := func(t *testing.T) {
 		t.Parallel()
@@ -92,6 +98,5 @@ func benchmark(sort sortAlgorithm, length int, b *testing.B) {
 }
 
 func makeIntegers(length, max int) ds.ArrayList {
-	//return ds.ReverseSortedIntegers(length)
 	return ds.RandomIntegers(length, max)
 }
-- 
cgit v1.2.3