Last active
March 6, 2018 20:01
-
-
Save crhntr/7fb8c49696fffd573489399c22757a7b to your computer and use it in GitHub Desktop.
Shell Sort Implemented In Go Using Incremental Insertion Sort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// see https://play.golang.org/p/dB1ELVO8c69 | |
package main | |
import ( | |
"fmt" | |
"math/rand" | |
) | |
const MaxNum = 15 | |
type Node struct { | |
Previous *Node | |
D int | |
Next *Node | |
} | |
// String is a method displays a node and all it's "next" nodes | |
func (node Node) String() string { | |
str := "" | |
cn := &node | |
for cn.Next != nil { | |
str += fmt.Sprintf("%d -> ", cn.D) | |
cn = cn.Next | |
} | |
str += "nil" | |
return str | |
} | |
// NewLinkedListOfNodes creates a linked list of 'length' nodes. | |
func NewLinkedListOfNodes(length int) Node { | |
root := Node{ | |
D: rand.Intn(MaxNum), | |
} | |
currentNode := &root | |
for i := 0; i < length; i++ { | |
currentNode.Next = &Node{ | |
D: rand.Intn(MaxNum), | |
} | |
currentNode = currentNode.Next | |
} | |
return root | |
} | |
// shellSort creates links to previous nodes and calls incrementalInsertionSort | |
func (firstNode *Node) shellSort(first, last int) { | |
for space := (last - first) / 2; space > 0; space = space / 2 { | |
previous, current := firstNode, firstNode | |
counter := 0 | |
fmt.Printf("-----> Before parital sort with space %d : \n", space) | |
fmt.Println(firstNode) | |
for counter < space && current != nil { | |
current = current.Next | |
counter++ | |
} | |
for previous != nil && current != nil { | |
current.Previous = previous | |
current = current.Next | |
previous = previous.Next | |
} | |
firstNode.incrementalInsertionSort(first, last, space) | |
fmt.Printf("-----> After parital sort with space %d : \n", space) | |
fmt.Println(firstNode) | |
} | |
} | |
// incrementalInsertionSort does an insertion sort on elements separated by space | |
func (firstNode *Node) incrementalInsertionSort(first, last, space int) { | |
current := firstNode | |
for counter := 0; counter < space; counter++ { | |
current = current.Next | |
} | |
for current != nil { | |
for c := current; c != nil && c.Previous != nil; c = c.Previous { | |
fmt.Printf("-> Comparing %d with %d\n", c.D, c.Previous.D) | |
if c.Previous.D > c.D { | |
fmt.Printf("-> Swapping %d with %d\n", c.D, c.Previous.D) | |
c.D, c.Previous.D = c.Previous.D, c.D // single line swap... in Go we don't use temp | |
} | |
} | |
current = current.Next | |
} | |
} | |
func main() { | |
numNodes := 11 | |
list := NewLinkedListOfNodes(numNodes) | |
list.shellSort(0, numNodes) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I fixed an outputting error.