# Golang program for implementation of Shell Sort

ShellSort is mainly a variation of Insertion Sort. The idea of shellSort is to allow exchange of far items. In shellSort, we make the array N-sorted for a large value of N. We keep reducing the value of N until it becomes 1. An array is said to be N-sorted if all sub-lists of every N'th element is sorted.

### Example

```
``````
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
slice := generateSlice(20)
fmt.Println("\n--- Unsorted --- \n\n", slice)
shellsort(slice)
fmt.Println("\n--- Sorted ---\n\n", slice, "\n")
}
// Generates a slice of size, size filled with random numbers
func generateSlice(size int) []int {
slice := make([]int, size, size)
rand.Seed(time.Now().UnixNano())
for i := 0; i < size; i++ {
slice[i] = rand.Intn(999) - rand.Intn(999)
}
return slice
}
func shellsort(items []int) {
var (
n = len(items)
gaps = []int{1}
k = 1
)
for {
gap := element(2, k) + 1
if gap > n-1 {
break
}
gaps = append([]int{gap}, gaps...)
k++
}
for _, gap := range gaps {
for i := gap; i < n; i += gap {
j := i
for j > 0 {
if items[j-gap] > items[j] {
items[j-gap], items[j] = items[j], items[j-gap]
}
j = j - gap
}
}
}
}
func element(a, b int) int {
e := 1
for b > 0 {
if b&1 != 0 {
e *= a
}
b >>= 1
a *= a
}
return e
}
```

### Output

```
``````
--- Unsorted ---
[86 -261 66 -385 -601 20 -19 417 692 -352 57 -111 -169 -345 -331 138 -132 445 62 50]
--- Sorted ---
[-601 -385 -352 -345 -331 -261 -169 -132 -111 -19 20 50 57 62 66 86 138 417 445 692]
```

##### Most Helpful This Week

Golang program for implementation LIFO Stack and FIFO Queue
Golang program for implementation of Pancake Sort
Golang program for implementation of Quick Sort
Golang program for implementation of AVL Trees
Golang program for implementation of Random Maze Generator
Golang program for implementation of Floyd–Warshall Algorithm