summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ds/arraylist.go8
-rw-r--r--ds/comparer.go10
-rw-r--r--ds/elem.go10
-rw-r--r--ds/integer.go26
-rw-r--r--sort/insertion.go4
-rw-r--r--sort/merge.go49
-rw-r--r--sort/merge2.go37
-rw-r--r--sort/merge3.go26
-rw-r--r--sort/shuffle.go3
-rw-r--r--sort/sort_test.go41
10 files changed, 181 insertions, 33 deletions
diff --git a/ds/arraylist.go b/ds/arraylist.go
index 243efe1..d3feef5 100644
--- a/ds/arraylist.go
+++ b/ds/arraylist.go
@@ -5,7 +5,7 @@ import (
"strings"
)
-type ArrayList []Comparer
+type ArrayList []Elem
func (a ArrayList) FirstN(n int) string {
var sb strings.Builder
@@ -37,7 +37,7 @@ func (a ArrayList) Sorted() bool {
}
func (a ArrayList) Swap(i, j int) {
- tmp := a[i]
- a[i] = a[j]
- a[j] = tmp
+ tmp := a[i]
+ a[i] = a[j]
+ a[j] = tmp
}
diff --git a/ds/comparer.go b/ds/comparer.go
deleted file mode 100644
index 8fb3727..0000000
--- a/ds/comparer.go
+++ /dev/null
@@ -1,10 +0,0 @@
-package ds
-
-type Comparer interface {
- Equal(a Comparer) bool
- Lower(a Comparer) bool
- LowerEqual(a Comparer) bool
- Higher(a Comparer) bool
- HigherEqual(a Comparer) bool
- Int() int
-}
diff --git a/ds/elem.go b/ds/elem.go
new file mode 100644
index 0000000..0589e81
--- /dev/null
+++ b/ds/elem.go
@@ -0,0 +1,10 @@
+package ds
+
+type Elem interface {
+ Equal(a Elem) bool
+ Lower(a Elem) bool
+ LowerEqual(a Elem) bool
+ Higher(a Elem) bool
+ HigherEqual(a Elem) bool
+ Int() int
+}
diff --git a/ds/integer.go b/ds/integer.go
index 04fee3e..4abb349 100644
--- a/ds/integer.go
+++ b/ds/integer.go
@@ -6,7 +6,7 @@ import (
)
type Integer struct {
- val int
+ Val int
}
func RandomIntegers(length, max int) ArrayList {
@@ -36,29 +36,29 @@ func ReverseSortedIntegers(length int) ArrayList {
}
func (i Integer) String() string {
- return fmt.Sprintf("%d", i.val)
+ return fmt.Sprintf("%d", i.Val)
}
func (i Integer) Int() int {
- return i.val
+ return i.Val
}
-func (i Integer) Equal(j Comparer) bool {
- return i.val == j.Int()
+func (i Integer) Equal(j Elem) bool {
+ return i.Val == j.Int()
}
-func (i Integer) Lower(j Comparer) bool {
- return i.val < j.Int()
+func (i Integer) Lower(j Elem) bool {
+ return i.Val < j.Int()
}
-func (i Integer) LowerEqual(j Comparer) bool {
- return i.val <= j.Int()
+func (i Integer) LowerEqual(j Elem) bool {
+ return i.Val <= j.Int()
}
-func (i Integer) Higher(j Comparer) bool {
- return i.val > j.Int()
+func (i Integer) Higher(j Elem) bool {
+ return i.Val > j.Int()
}
-func (i Integer) HigherEqual(j Comparer) bool {
- return i.val >= j.Int()
+func (i Integer) HigherEqual(j Elem) bool {
+ return i.Val >= j.Int()
}
diff --git a/sort/insertion.go b/sort/insertion.go
index 465e8b4..3e271b0 100644
--- a/sort/insertion.go
+++ b/sort/insertion.go
@@ -12,9 +12,7 @@ func Insertion(a ds.ArrayList) ds.ArrayList {
if a[j].Higher(a[j-1]) {
break
}
- tmp := a[j]
- a[j] = a[j-1]
- a[j-1] = tmp
+ a.Swap(j, j-1)
}
}
diff --git a/sort/merge.go b/sort/merge.go
new file mode 100644
index 0000000..e57ea6d
--- /dev/null
+++ b/sort/merge.go
@@ -0,0 +1,49 @@
+package sort
+
+import (
+ "algorithms/ds"
+)
+
+func Merge(a ds.ArrayList) ds.ArrayList {
+ aux := make(ds.ArrayList, len(a))
+ mergeSort(a, aux, 0, len(a)-1)
+
+ return a
+}
+
+func mergeSort(a, aux ds.ArrayList, lo, hi int) {
+ if lo >= hi {
+ return
+ }
+ mid := lo + (hi-lo)/2
+
+ mergeSort(a, aux, lo, mid)
+ mergeSort(a, aux, mid+1, hi)
+ merge(a, aux, lo, mid, hi)
+}
+
+func merge(a, aux ds.ArrayList, lo, mid, hi int) {
+ for i := lo; i <= hi; i++ {
+ aux[i] = a[i]
+ }
+
+ i := lo
+ j := mid + 1
+
+ for k := lo; k <= hi; k++ {
+ switch {
+ case i > mid:
+ a[k] = aux[j]
+ j++
+ case j > hi:
+ a[k] = aux[i]
+ i++
+ case aux[i].Higher(aux[j]):
+ a[k] = aux[j]
+ j++
+ default:
+ a[k] = aux[i]
+ i++
+ }
+ }
+}
diff --git a/sort/merge2.go b/sort/merge2.go
new file mode 100644
index 0000000..774c3c5
--- /dev/null
+++ b/sort/merge2.go
@@ -0,0 +1,37 @@
+package sort
+
+import (
+ "algorithms/ds"
+ "sync"
+)
+
+// Merge2 is a parallelized version of Merge
+func Merge2(a ds.ArrayList) ds.ArrayList {
+ aux := make(ds.ArrayList, len(a))
+ mergeSort2(a, aux, 0, len(a)-1)
+
+ return a
+}
+
+func mergeSort2(a, aux ds.ArrayList, lo, hi int) {
+ mid := lo + (hi-lo)/2
+ defer merge(a, aux, lo, mid, hi)
+
+ if hi-lo <= 1000 {
+ mergeSort(a, aux, lo, mid)
+ mergeSort(a, aux, mid+1, hi)
+ return
+ }
+
+ var wg sync.WaitGroup
+ wg.Add(2)
+ go func() {
+ mergeSort2(a, aux, lo, mid)
+ wg.Done()
+ }()
+ go func() {
+ mergeSort2(a, aux, mid+1, hi)
+ wg.Done()
+ }()
+ wg.Wait()
+}
diff --git a/sort/merge3.go b/sort/merge3.go
new file mode 100644
index 0000000..fbc1650
--- /dev/null
+++ b/sort/merge3.go
@@ -0,0 +1,26 @@
+package sort
+
+import (
+ "algorithms/ds"
+)
+
+// Merge3 is the bottom up version of merge sort.
+func Merge3(a ds.ArrayList) ds.ArrayList {
+ length := len(a)
+ aux := make(ds.ArrayList, length)
+
+ for sz := 1; sz < length; sz = sz + sz {
+ for lo := 0; lo < length-sz; lo += sz + sz {
+ merge(a, aux, lo, lo+sz-1, min(lo+sz+sz-1, length-1))
+ }
+ }
+
+ return a
+}
+
+func min(a, b int) int {
+ if a <= b {
+ return a
+ }
+ return b
+}
diff --git a/sort/shuffle.go b/sort/shuffle.go
index 9c6f5b9..26db8c4 100644
--- a/sort/shuffle.go
+++ b/sort/shuffle.go
@@ -10,9 +10,6 @@ func Shuffle(a ds.ArrayList) ds.ArrayList {
for i := 0; i < length; i++ {
r := length - rand.Intn(length-i) - 1
- if r == i {
- continue
- }
tmp := a[i]
a[i] = a[r]
a[r] = tmp
diff --git a/sort/sort_test.go b/sort/sort_test.go
index bd9db9b..a0e4729 100644
--- a/sort/sort_test.go
+++ b/sort/sort_test.go
@@ -33,6 +33,29 @@ func TestShellSort(t *testing.T) {
}
}
+func TestMergeSort(t *testing.T) {
+ for i := 1; i <= maxLength; i *= 10 {
+ test(Merge, i, t)
+ }
+ test(Merge, maxLength*2, t)
+}
+
+func TestMerge2Sort(t *testing.T) {
+ t.Log("Parallel merge sort")
+ for i := 1; i <= maxLength; i *= 10 {
+ test(Merge2, i, t)
+ }
+ test(Merge2, maxLength*2, t)
+}
+
+func TestMerge3Sort(t *testing.T) {
+ t.Log("Bottom-up merge sort")
+ for i := 1; i <= maxLength; i *= 10 {
+ test(Merge3, i, t)
+ }
+ test(Merge3, maxLength*2, t)
+}
+
func TestQuickSort(t *testing.T) {
for i := 1; i <= maxLength; i *= 10 {
test(Quick, i, t)
@@ -63,6 +86,24 @@ func BenchmarkShellSort(b *testing.B) {
}
}
+func BenchmarkMergeSort(b *testing.B) {
+ for i := 1; i <= maxLength; i *= 10 {
+ benchmark(Merge, i, b)
+ }
+}
+
+func BenchmarkMerge2Sort(b *testing.B) {
+ for i := 1; i <= maxLength; i *= 10 {
+ benchmark(Merge2, i, b)
+ }
+}
+
+func BenchmarkMerge3Sort(b *testing.B) {
+ for i := 1; i <= maxLength; i *= 10 {
+ benchmark(Merge3, i, b)
+ }
+}
+
func BenchmarkQuickSort(b *testing.B) {
for i := 1; i <= maxLength; i *= 10 {
benchmark(Quick, i, b)
generated by cgit v1.2.3 (git 2.25.1) at 2026-08-08 07:01:51 +0000