Javad Rajabzadeh for Gopher

Posted on Jun 22, 2021

Algorithms for Go

#go #tutorial

Binary search

package main

import (
    "fmt"
    "time"
)

//works when the array is sorted
func binarySearch(arr []int, x int) int {
    i := 0
    j := len(arr)
    for i != j {
        var m = (i + j) / 2
        if x == arr[m] {
            return m
        }
        if x < arr[m] {
            j = m
        } else {
            i = m + 1
        }
    }
    return -1
}

func main() {
    items := []int{2, 3, 5, 7, 11, 13, 17}

    fmt.Println(binarySearch(items, 1))
    //print -1
    fmt.Println(binarySearch(items, 7))
    //print 3
    fmt.Println(binarySearch(items, 19))
    //print -1

    // *** simplified speed test ***

    items = make([]int, 10000000)
    for i := 0; i < len(items); i++ {
        items[i] = i
    }
    count := 100

    start := time.Now()

    for i := 0; i < count; i++ {
        binarySearch(items, 7777777)
    }

    delta := time.Now().Sub(start)
    nanoseconds := delta.Nanoseconds() / int64(count)

    fmt.Println(nanoseconds)
    // about 88 nanoseconds
}

Fast linear search

package main

import (
    "fmt"
    "time"
)

func fastLinearSearch(arr []int, x int) int {
    i := 0
    count := len(arr)
    arr = append(arr, x)
    for true {
        if arr[i] == x {
            if i < count {
                return i
            }
            return -1
        }
        i++
    }
    return -1
}

func main() {
    items := []int{2, 3, 5, 7, 11, 13, 17}

    fmt.Println(fastLinearSearch(items, 1))
    //print -1
    fmt.Println(fastLinearSearch(items, 7))
    //print 3
    fmt.Println(fastLinearSearch(items, 19))
    //print -1

    // *** simplified speed test ***

    items = make([]int, 10000000)
    for i := 0; i < len(items); i++ {
        items[i] = i
    }
    count := 100

    start := time.Now()

    for i := 0; i < count; i++ {
        fastLinearSearch(items, 7777777)
    }

    delta := time.Now().Sub(start)
    nanoseconds := delta.Nanoseconds() / int64(count)

    fmt.Println(nanoseconds)
    // about 34 148 000 nanoseconds
}

Interpolation search

package main

import (
    "fmt"
    "time"
)

//works when the array is sorted
func interpolationSearch(arr []int, x int) int {
    low := 0
    high := len(arr) - 1

    for (arr[low] < x) && (x < arr[high]) {
        var mid = low + ((x-arr[low])*(high-low))/(arr[high]-arr[low])

        if arr[mid] < x {
            low = mid + 1
        } else if arr[mid] > x {
            high = mid - 1
        } else {
            return mid
        }
    }

    if arr[low] == x {
        return low
    }
    if arr[high] == x {
        return high
    }
    return -1
}

func main() {
    items := []int{2, 3, 5, 7, 11, 13, 17}

    fmt.Println(interpolationSearch(items, 1))
    //print -1
    fmt.Println(interpolationSearch(items, 7))
    //print 3
    fmt.Println(interpolationSearch(items, 19))
    //print -1

    // *** simplified speed test ***

    items = make([]int, 10000000)
    for i := 0; i < len(items); i++ {
        items[i] = i
    }
    count := 100

    start := time.Now()

    for i := 0; i < count; i++ {
        interpolationSearch(items, 7777777)
    }

    delta := time.Now().Sub(start)
    nanoseconds := delta.Nanoseconds() / int64(count)

    fmt.Println(nanoseconds)
    // about 41 nanoseconds
}

Linear search

package main

import (
    "fmt"
    "time"
)

func linearSearch(arr []int, x int) int {
    i := 0
    count := len(arr)
    for i < count {
        if arr[i] == x {
            return i
        }
        i++
    }
    return -1
}

func main() {
    items := []int{2, 3, 5, 7, 11, 13, 17}

    fmt.Println(linearSearch(items, 1))
    //print -1
    fmt.Println(linearSearch(items, 7))
    //print 3
    fmt.Println(linearSearch(items, 19))
    //print -1

    // *** simplified speed test ***

    items = make([]int, 10000000)
    for i := 0; i < len(items); i++ {
        items[i] = i
    }
    count := 100

    start := time.Now()

    for i := 0; i < count; i++ {
        linearSearch(items, 7777777)
    }

    delta := time.Now().Sub(start)
    nanoseconds := delta.Nanoseconds() / int64(count)

    fmt.Println(nanoseconds)
    // about 20 910 000 nanoseconds
}

Bubble sort

package main

import (
    "fmt"
    "time"
)

// Time Complexity O(n^2)
// Space Complexity O(1)

func bubbleSort(arr []int) []int {
    length := len(arr)
    items := make([]int, length)
    copy(items, arr)
    for i := 0; i < length; i++ {
        for j := i + 1; j < length; j++ {
            if items[j] < items[i] {
                var tmp = items[j]
                items[j] = items[i]
                items[i] = tmp
            }
        }
    }
    return items
}

func main() {
    items := []int{4, 1, 5, 3, 2}

    sortItems := bubbleSort(items)
    // sortItems is {1, 2, 3, 4, 5}

    // *** simplified speed test ***

    items = make([]int, 200)
    for i := 0; i < len(items); i++ {
        items[i] = i
    }
    var tmp = items[5]
    items[5] = items[6]
    items[6] = tmp
    count := 10000
    start := time.Now()

    for i := 0; i < count; i++ {
        bubbleSort(items)
    }

    delta := time.Now().Sub(start)
    nanoseconds := delta.Nanoseconds()

    fmt.Println(sortItems)
    fmt.Println(nanoseconds)
    // about 683 000 000 nanoseconds
}

Counting sort

package main

import (
    "fmt"
    "math"
    "time"
)

// Time Complexity O(n+k)
// Space Complexity O(k)

func countingSort(arr []int) []int {
    length := len(arr)
    items := make([]int, length)
    copy(items, arr)

    var min = math.MaxInt32
    var max = math.MinInt32
    for _, x := range arr {
        if x > max {
            max = x
        }
        if x < min {
            min = x
        }
    }

    var counts = make([]int, max-min+1)

    for _, x := range arr {
        counts[x-min]++
    }

    var total = 0
    for i := min; i <= max; i++ {
        var oldCount = counts[i-min]
        counts[i-min] = total
        total += oldCount
    }

    for _, x := range arr {
        items[counts[x-min]] = x
        counts[x-min]++
    }
    return items
}

func main() {
    items := []int{4, 1, 5, 3, 2}

    sortItems := countingSort(items)
    // sortItems is {1, 2, 3, 4, 5}

    // *** simplified speed test ***

    items = make([]int, 200)
    for i := 0; i < len(items); i++ {
        items[i] = i
    }
    var tmp = items[5]
    items[5] = items[6]
    items[6] = tmp
    count := 10000
    start := time.Now()

    for i := 0; i < count; i++ {
        countingSort(items)
    }

    delta := time.Now().Sub(start)
    nanoseconds := delta.Nanoseconds()

    fmt.Println(sortItems)
    fmt.Println(nanoseconds)
    // about 58 000 000 nanoseconds
}

Merge sort

package main

import (
    "fmt"
    "time"
)

// Time Complexity O(n log(n)))
// Space Complexity O(n)

func mergeSort(arr []int) []int {
    items := make([]int, len(arr))
    copy(items, arr)
    doMergeSort(items)
    return items
}

func doMergeSort(items []int) {
    length := len(items)
    if length == 1 {
        return
    }

    var lLeft = length / 2
    var left = make([]int, lLeft)
    copy(left, items[:lLeft])
    var lRight = length - lLeft
    var right = make([]int, lRight)
    copy(right, items[lLeft:])

    doMergeSort(left)
    doMergeSort(right)

    merge(left, right, items)
}

func merge(left []int, right []int, result []int) {
    l := 0
    r := 0
    i := 0

    for l < len(left) && r < len(right) {
        if left[l] < right[r] {
            result[i] = left[l]
            l++
        } else {
            result[i] = right[r]
            r++
        }
        i++
    }
    var length = len(left) - l
    copy(result[i:i+length], left[l:])
    i = i + length
    length = len(right) - r
    copy(result[i:i+length], right[r:])
}

func main() {
    items := []int{4, 1, 5, 3, 2}

    sortItems := mergeSort(items)
    // sortItems is {1, 2, 3, 4, 5}

    // *** simplified speed test ***

    items = make([]int, 200)
    for i := 0; i < len(items); i++ {
        items[i] = i
    }
    var tmp = items[5]
    items[5] = items[6]
    items[6] = tmp
    count := 10000
    start := time.Now()

    for i := 0; i < count; i++ {
        mergeSort(items)
    }

    delta := time.Now().Sub(start)
    nanoseconds := delta.Nanoseconds()

    fmt.Println(sortItems)
    fmt.Println(nanoseconds)
    // about 439 000 000 nanoseconds
}

Quick sort

package main

import (
    "fmt"
    "time"
)

// Time Complexity from O(n log(n)) to O(n^2)
// Space Complexity O(log(n))

func doSort(items []int, fst int, lst int) {
    if fst >= lst {
        return
    }
    i := fst
    j := lst
    x := items[(fst+lst)/2]

    for i < j {
        for items[i] < x {
            i++
        }
        for items[j] > x {
            j--
        }
        if i <= j {
            var tmp = items[i]
            items[i] = items[j]
            items[j] = tmp
            i++
            j--
        }
    }
    doSort(items, fst, j)
    doSort(items, i, lst)
}

func quicksort(arr []int) []int {
    length := len(arr)
    items := make([]int, length)
    copy(items, arr)
    doSort(items, 0, length-1)
    return items
}

func main() {
    items := []int{4, 1, 5, 3, 2}

    sortItems := quicksort(items)
    // sortItems is {1, 2, 3, 4, 5}

    // *** simplified speed test ***

    items = make([]int, 200)
    for i := 0; i < len(items); i++ {
        items[i] = i
    }
    var tmp = items[5]
    items[5] = items[6]
    items[6] = tmp
    count := 10000
    start := time.Now()

    for i := 0; i < count; i++ {
        quicksort(items)
    }

    delta := time.Now().Sub(start)
    nanoseconds := delta.Nanoseconds()

    fmt.Println(sortItems)
    fmt.Println(nanoseconds)
    // about 83 000 000 nanoseconds
}

Redix sort

package main

import (
    "fmt"
    "math"
    "time"
)

// Time Complexity O(nk)
// Space Complexity O(n+k)

func listToBuckets(items []int, cBase int, i int) [][]int {
    var buckets = make([][]int, cBase)

    var pBase = int(math.Pow(
        float64(cBase), float64(i)))
    for _, x := range items {
        //Isolate the base-digit from the number
        var digit = (x / pBase) % cBase
        //Drop the number into the correct bucket
        buckets[digit] = append(buckets[digit], x)
    }

    return buckets
}

func bucketsToList(buckets [][]int) []int {
    result := []int{}

    for _, bucket := range buckets {
        result = append(result, bucket...)
    }

    return result
}

func radixSort(arr []int, cBase int) []int {
    maxVal := 0
    for i, value := range arr {
        if i == 0 || value > maxVal {
            maxVal = value
        }
    }

    length := len(arr)
    items := make([]int, length)
    copy(items, arr)

    i := 0
    for math.Pow(float64(cBase), float64(i)) <= float64(maxVal) {
        items = bucketsToList(listToBuckets(items, cBase, i))
        i++
    }

    return items
}

func main() {
    items := []int{4, 1, 5, 3, 2}

    sortItems := radixSort(items, 10)
    // sortItems is {1, 2, 3, 4, 5}

    // *** simplified speed test ***

    items = make([]int, 200)
    for i := 0; i < len(items); i++ {
        items[i] = i
    }
    var tmp = items[5]
    items[5] = items[6]
    items[6] = tmp
    count := 10000
    start := time.Now()

    for i := 0; i < count; i++ {
        radixSort(items, 10)
    }

    delta := time.Now().Sub(start)
    nanoseconds := delta.Nanoseconds()

    fmt.Println(sortItems)
    fmt.Println(nanoseconds)
    // about 532 200 000 nanoseconds
}

Get n8n VPS hosting 3x cheaper than a cloud solution

Get fast, easy, secure n8n VPS hosting from $4.99/mo at Hostinger. Automate any workflow using a pre-installed n8n application and no-code customization.

Start now

DEV Community

Algorithms for Go

Binary search

Fast linear search

Interpolation search

Linear search

Bubble sort

Counting sort

Merge sort

Quick sort

Redix sort

Get n8n VPS hosting 3x cheaper than a cloud solution

Top comments (0)

The Next Generation Developer Platform

Read next

Fixing Z-Axis Character Jitter: A Practical Guide

React's 'Uncaught TypeError: Cannot read properties of undefined (reading 'jsx')': A Quick Fix

Fixing '@layer utilities...' Tailwind Error: A Quick Guide

Android WebView Crash: Fix "Operation not permitted"

AWS GenAI LIVE!