Golang ProgramsGolang Programs

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.
// Shell Sort in Golang
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
}
C:\golang\time>go run s2.go

--- 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]


C:\golang\time>