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
Example: How to use ReadAtLeast from IO Package in Golang?
Golang program for implementation of Floyd–Warshall Algorithm
How do you handle HTTP client server alerting in Go?
Creating a Struct Instance Using a Struct Literal
Program in Go language to print Floyd's Triangle
Program in Go language to Find Largest Element of an Array