Golang Algorithms Implementation

bubblesort.go

package main

import (
	"fmt"
)

func bubblesort(arr []int) []int {
	is_changed := true
	n := len(arr) - 1
	for is_changed {
		is_changed = false
		for i := 0; i < n; i++ {
			if arr[i] > arr[i+1] {
				is_changed = true
				arr[i], arr[i+1] = arr[i+1], arr[i]
			}
		}
	}
	
	return arr
}

func main() {
	arr := []int {1, 2, 4, 1, 2, 5, 1, 2, 5, 7, 1}
	fmt.Println(bubblesort(arr))
}

dijkstra.go

package main

import (
	"fmt"
	"math"
)

func dijkstra(from string, to string, graph map[string]map[string]int) int64 {
	dist := make(map[string]int64, len(graph))
	for k := range graph {
		dist[k] = math.MaxInt64
	}
	
	dist[from] = 0
	nvisited := 0
	visited := make(map[string]bool, len(graph))
	for k := range graph {
		visited[k] = false
	}
	
	for nvisited <= len(graph) {
		var min_dist int64 = math.MaxInt64
		min_k := ""
		for k, v := range dist {
			if v <= min_dist && !visited[k] {
				min_k = k
				min_dist = v
			}
		}
		
		if min_k == "" {
			nvisited++
			continue
		}
		
		for k, v := range graph[min_k] {
			new_dist := int64(v) + dist[min_k]
			if new_dist < dist[k] {
			
				dist[k] = new_dist
			}
		}
		
		visited[min_k] = true
		nvisited++
	} 
	

	return dist[to]
}

func main() {
	graph := map[string]map[string]int{
		"book":   map[string]int{"disc": 5, "poster": 0},
		"disc":   map[string]int{"guitar": 15, "drum": 20},
		"poster": map[string]int{"guitar": 30, "drum": 35},
		"guitar": map[string]int{"piano": 20},
		"drum":   map[string]int{"piano": 10},
		"piano":  map[string]int{},
	}
	dist := dijkstra("book", "piano", graph)
	fmt.Println(dist)
}

quicksort.go

package main

import (
	"fmt"
)

func quicksort(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}
	
	var less []int
	var more []int
	pivot := arr[len(arr)/2]
	is_pivot_scored := false
	for i := 0; i < len(arr); i++ {
		if arr[i] == pivot {
			if !is_pivot_scored {
				is_pivot_scored = true;
			} else {
				less = append(less, pivot)
			}
			continue;
		}
		
		if arr[i] < pivot {
			less = append(less, arr[i])
		} else {
			more = append(more, arr[i])
		}
	}
	
	less = quicksort(less)
	less = append(less, pivot)
	more = quicksort(more)
	less = append(less, more...)
	
	return less
}

func main() {
	arr := []int{3, 2, 1, 2, 1, 3, 3, 5}
	fmt.Println(quicksort(arr))
}

segmenttree.go

package main

import (
	"fmt"
)

type SegmentTree struct {
	a []int
	b []int
}

func NewSegmentTree(c []int) *SegmentTree {
	a := make([]int, len(c))
	b := make([]int, 4*len(c)+1)
	copy(a, c)
	return &SegmentTree{a, b}
}

func (self *SegmentTree) Build() {
	self.construct(1, 0, len(self.a)-1)
}

func (self *SegmentTree) construct(v, l, r int) int {
	if l == r {
		self.b[v] = self.a[l]
		return self.b[v]
	}
	m := (l + r) / 2
	lsum := self.construct(2*v, l, m)
	rsum := self.construct(2*v+1, m+1, r)
	self.b[v] = lsum + rsum

	return self.b[v]
}

func (self SegmentTree) Get(i int, j int) int {
	return self.getSum(1, 0, len(self.a)-1, i, j)
}

func (self SegmentTree) getSum(v, lt, rt, l, r int) int {
	if lt == l && rt == r {
		return self.b[v]
	}

	m := (lt + rt) / 2
	switch {
	case r <= m:
		return self.getSum(2*v, lt, m, l, r)
	case l > m:
		return self.getSum(2*v+1, m+1, rt, l, r)
	default:
		lsum := self.getSum(2*v, lt, m, l, m)
		rsum := self.getSum(2*v+1, m+1, rt, m+1, r)
		return lsum + rsum
	}
}


func (self *SegmentTree) Update(i, val int) {
	self.updateElement(i, val, 1, 0, len(self.a) - 1)
}


func (self *SegmentTree) updateElement(i, val, v, l, r int) {
	if l == i && r == i {
		self.b[v] = val
		return
	}
	
	m := (l + r) / 2
	if i <= m {
		self.updateElement(i, val, 2*v, l, m)
	} else {
		self.updateElement(i, val, 2*v + 1, m + 1, r)
	}
	
	self.b[v] = self.b[2*v] + self.b[2*v + 1]
}


func (self SegmentTree) Print() {
	for i := 0; i < len(self.b); i++ {
		fmt.Print(self.b[i], " ")
	}
}

func main() {
	a := []int{1, 2, 3, 4, 5, 6, 7}
	tree := NewSegmentTree(a)
	tree.Build()
	fmt.Println(tree.Get(0, 1) == 3)
	fmt.Println(tree.Get(0, 3) == 10)
	fmt.Println(tree.Get(3, 3) == 4)
	fmt.Println(tree.Get(2, 5) == 18)
	
	tree.Update(2, 4)
	fmt.Println(tree.Get(2, 5) == 19)
	tree.Update(1, 2)
	fmt.Println(tree.Get(1, 1) == 2)
}

suffixarray.go

package main

import (
	"fmt"
	"sort"
	"strings"
)

type SuffixArray struct {
	substrings []string
	indices    []int
}

func (self SuffixArray) Search(s string) (int, bool) {
	k := sort.SearchStrings(self.substrings, s)
	has_prefix := strings.HasPrefix(self.substrings[k], s)
	if k < len(self.substrings) && has_prefix {
		return self.indices[k], true
	} else {
		return -1, false
	}
}

func NewSuffixArray(s string) *SuffixArray {
	runes := []rune(s)
	a := make([]string, len(runes))
	b := make([]int, len(runes))
	for i := 0; i < len(runes); i++ {
		a[i] = string(runes[i:])
		b[i] = i
	}

	sort.Slice(a, func(i int, j int) bool {
		if a[i] <= a[j] {
			b[i], b[j] = b[j], b[i]
			return true
		}

		return false
	})

	return &SuffixArray{a, b}
}

func main() {
	suff := NewSuffixArray("missisipi")
	if i, ok := suff.Search("sis"); ok {
		fmt.Println("Found at ", i)
	} else {
		fmt.Println("Not found")
	}
}