Golang React JS Technology Blog

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 to implement Binary Tree Golang program for implementation of Binary Search Golang program for implementation of Random Maze Generator Golang program for drawing a Cuboid Golang program for implementation of Tower of Hanoi Algorithm Golang program for implementation of Median of Medians Golang program for implementation of Linear Search Golang program for implementation of Linked List Golang program to print all Permutations of a given string Golang program for implementation LZW Data Compression and Uncompression