/
shell_sort.go
63 lines (58 loc) · 1.11 KB
/
shell_sort.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//main package has examples shown
// in Go Data Structures and algorithms book
package main
// importing fmt and bytes package
import (
"fmt"
)
// shell sorter method
func ShellSorter(elements []int) {
var (
n = len(elements)
intervals = []int{1}
k = 1
)
for {
var interval int
interval = power(2, k) + 1
if interval > n-1 {
break
}
intervals = append([]int{interval}, intervals...)
k++
}
var interval int
for _, interval = range intervals {
var i int
for i = interval; i < n; i += interval {
var j int
j = i
for j > 0 {
if elements[j-interval] > elements[j] {
elements[j-interval], elements[j] = elements[j], elements[j-interval]
}
j = j - interval
}
}
}
}
//power function
func power(exponent int, index int) int {
var power int
power = 1
for index > 0 {
if index&1 != 0 {
power *= exponent
}
index >>= 1
exponent *= exponent
}
return power
}
// main method
func main() {
var elements []int
elements = []int{34, 202, 13, 19, 6, 5, 1, 43, 506, 12, 20, 28, 17, 100, 25, 4, 5, 97, 1000, 27}
ShellSorter(elements)
fmt.Println(elements)
}