diff options
| -rw-r--r-- | main.go | 2 | ||||
| -rw-r--r-- | sort/insertion.go | 22 | ||||
| -rw-r--r-- | sort/insertion_test.go | 12 | ||||
| -rw-r--r-- | sort/selection.go | 12 |
4 files changed, 41 insertions, 7 deletions
@@ -10,5 +10,5 @@ func main() { fmt.Println("Hello to Algorithms Playground!") a := ds.RandomIntegers(100, 1000) fmt.Printf("Random: %v\n", a) - fmt.Printf("Sorted: %v\n", sort.Selection(a)) + fmt.Printf("Sorted: %v\n", sort.Insertion(a)) } diff --git a/sort/insertion.go b/sort/insertion.go new file mode 100644 index 0000000..d14c275 --- /dev/null +++ b/sort/insertion.go @@ -0,0 +1,22 @@ +package sort + +import ( + "algorithms/ds" +) + +func Insertion(a []ds.Comparer) []ds.Comparer { + length := len(a) + + for i := 0; i < length; i++ { + for j := i; j > 0; j-- { + if a[j].HigherThan(a[j-1]) { + break + } + tmp := a[j] + a[j] = a[j-1] + a[j-1] = tmp + } + } + + return a +} diff --git a/sort/insertion_test.go b/sort/insertion_test.go new file mode 100644 index 0000000..4b503b8 --- /dev/null +++ b/sort/insertion_test.go @@ -0,0 +1,12 @@ +package sort + +import ( + "algorithms/ds" + "testing" +) + +func BenchmarkInsertion1000(b *testing.B) { + a := ds.RandomIntegers(1000, 1000) + b.ResetTimer() + Insertion(a) +} diff --git a/sort/selection.go b/sort/selection.go index e2a774c..2782460 100644 --- a/sort/selection.go +++ b/sort/selection.go @@ -7,18 +7,18 @@ import ( func Selection(a []ds.Comparer) []ds.Comparer { length := len(a) for i := 0; i < length; i++ { - max := i + min := i for j := i + 1; j < length; j++ { - if a[max].HigherThan(a[j]) { - max = j + if a[min].HigherThan(a[j]) { + min = j } } - if max == i { + if min == i { continue } tmp := a[i] - a[i] = a[max] - a[max] = tmp + a[i] = a[min] + a[min] = tmp } return a } |