binaryInsertionSort.go 945 Bytes
Newer Older
Ilia Prokhorov's avatar
Ilia Prokhorov committed
1
2
package main

3
4
5
6
7
import (
	"fmt"
	"math/rand"
	"time"
)
Ilia Prokhorov's avatar
Ilia Prokhorov committed
8

9
10
const numbersCount = 20
const maximalNumber = 100
Ilia Prokhorov's avatar
Ilia Prokhorov committed
11

12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func binarySearch(numbers []int, item int, low int, high int) int {
	for high > low {
		center := (low + high) / 2
		if numbers[center] < item {
			low = center + 1
		} else if numbers[center] > item {
			high = center - 1
		} else {
			return center
		}
	}

	if numbers[low] < item {
		return low + 1
	} else {
		return low
	}
Ilia Prokhorov's avatar
Ilia Prokhorov committed
29
30
31
}

func main() {
32
33
34
35
36
37
38
	rand.Seed(time.Now().Unix())
	var numbers [numbersCount]int
	for i := 0; i < numbersCount; i++ {
		numbers[i] = rand.Intn(maximalNumber)
	}
	fmt.Println(numbers)

Ilia Prokhorov's avatar
Ilia Prokhorov committed
39
	for i := 1; i < len(numbers); i++ {
40
41
42
43
44
45
46
		searchAreaLastIndex := i - 1
		insertNumber := numbers[i]
		insertIndex := binarySearch(numbers[:], insertNumber, 0, searchAreaLastIndex)
		for x := searchAreaLastIndex; x >= insertIndex; x-- {
			numbers[x+1] = numbers[x]
		}
		numbers[insertIndex] = insertNumber
Ilia Prokhorov's avatar
Ilia Prokhorov committed
47
48
49
	}
	fmt.Println(numbers)
}