write insertion sort

1 files changed, 70 insertions, 0 deletions

diff --git a/exercises/2.1-2/sort_test.go b/exercises/2.1-2/sort_test.go
new file mode 100644
index 0000000..680597c
--- /dev/null
+++ b/exercises/2.1-2/sort_test.go
@@ -0,0 +1,70 @@
+package main
+
+import (
+	"fmt"
+	"testing"
+)
+
+func assertEqual(t *testing.T, expected interface{}, actual interface{}) {
+	if expected != actual {
+		t.Fatalf("%v != %v", expected, actual)
+	}
+}
+
+func insertionSort(A []int) []int {
+	for j := 1; j < len(A); j++ {
+		key := A[j]
+		i := j - 1
+		for i >= 0 && A[i] > key {
+			A[i+1] = A[i]
+			i = i - 1
+		}
+		A[i+1] = key
+	}
+	return A
+}
+
+func insertionSortDescending(A []int) []int {
+	for j := 1; j < len(A); j++ {
+		key := A[j]
+		i := j - 1
+		for i >= 0 && A[i] < key {
+			A[i+1] = A[i]
+			i = i - 1
+		}
+		A[i+1] = key
+	}
+	return A
+}
+
+func TestInsertionSort(t *testing.T) {
+	t.Run("Ascending order", func(t *testing.T) {
+		items := []int{31, 41, 59, 26, 41, 58}
+
+		results := insertionSort(items)
+
+		fmt.Printf("%v\n", results)
+
+		assertEqual(t, 26, results[0])
+		assertEqual(t, 31, results[1])
+		assertEqual(t, 41, results[2])
+		assertEqual(t, 41, results[3])
+		assertEqual(t, 58, results[4])
+		assertEqual(t, 59, results[5])
+	})
+
+	t.Run("Descending order", func(t *testing.T) {
+		items := []int{31, 41, 59, 26, 41, 58}
+
+		results := insertionSortDescending(items)
+
+		fmt.Printf("%v\n", results)
+
+		assertEqual(t, 26, results[5])
+		assertEqual(t, 31, results[4])
+		assertEqual(t, 41, results[2])
+		assertEqual(t, 41, results[3])
+		assertEqual(t, 58, results[1])
+		assertEqual(t, 59, results[0])
+	})
+}