Day 15c: Advanced Sorting and Searching Algorithms in Go

Advanced Sorting Techniques in Go

Merge Sort

Merge Sort is a divide-and-conquer algorithm that splits the array into halves, recursively sorts them, and then merges the sorted halves. Here’s a Go implementation:

package main

import (
    "fmt"
)

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := []int{}
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

func main() {
    data := []int{38, 27, 43, 3, 9, 82, 10}
    sorted := mergeSort(data)
    fmt.Println("Sorted Array:", sorted)
}

Quick Sort

Quick Sort is another divide-and-conquer algorithm but uses a pivot to partition the array into subarrays. It's often faster than Merge Sort for smaller datasets:

package main

import (
    "fmt"
)

func quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    pivot := arr[len(arr)/2]
    left := []int{}
    right := []int{}
    equal := []int{}
    for _, v := range arr {
        if v < pivot {
            left = append(left, v)
        } else if v > pivot {
            right = append(right, v)
        } else {
            equal = append(equal, v)
        }
    }
    left = quickSort(left)
    right = quickSort(right)
    return append(append(left, equal...), right...)
}

func main() {
    data := []int{10, 7, 8, 9, 1, 5}
    sorted := quickSort(data)
    fmt.Println("Sorted Array:", sorted)
}

Heap Sort

Heap Sort utilizes a binary heap to sort elements. Here’s a simple implementation in Go:

package main

import (
    "fmt"
)

func heapSort(arr []int) []int {
    n := len(arr)
    // Build max heap
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }
    // Extract elements from heap one by one
    for i := n - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    }
    return arr
}

func heapify(arr []int, n, i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2

    if left < n && arr[left] > arr[largest] {
        largest = left
    }
    if right < n && arr[right] > arr[largest] {
        largest = right
    }
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    }
}

func main() {
    data := []int{12, 11, 13, 5, 6, 7}
    sorted := heapSort(data)
    fmt.Println("Sorted Array:", sorted)
}

Advanced Searching Algorithms

Linear Search

Linear Search checks each element of the array one by one. Although simple, it's inefficient for large datasets:

package main

import (
    "fmt"
)

func linearSearch(arr []int, target int) int {
    for i, v := range arr {
        if v == target {
            return i
        }
    }
    return -1
}

func main() {
    data := []int{10, 20, 30, 40, 50}
    target := 30
    index := linearSearch(data, target)
    if index != -1 {
        fmt.Printf("Found %d at index %d\n", target, index)
    } else {
        fmt.Printf("%d not found\n", target)
    }
}

Depth-First Search (DFS)

DFS is a graph traversal algorithm. It can be implemented recursively or iteratively using a stack:

package main

import (
    "fmt"
)

func dfs(graph map[int][]int, start int, visited map[int]bool) {
    visited[start] = true
    fmt.Println(start)
    for _, neighbor := range graph[start] {
        if !visited[neighbor] {
            dfs(graph, neighbor, visited)
        }
    }
}

func main() {
    graph := map[int][]int{
        0: {1, 2},
        1: {2},
        2: {0, 3},
        3: {3},
    }
    visited := make(map[int]bool)
    fmt.Println("DFS starting from node 2:")
    dfs(graph, 2, visited)
}

Breadth-First Search (BFS)

BFS explores nodes level by level, using a queue to keep track of the next nodes to visit:

package main

import (
    "fmt"
)

func bfs(graph map[int][]int, start int) {
    queue := []int{start}
    visited := make(map[int]bool)
    visited[start] = true
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        fmt.Println(node)
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }
}

func main() {
    graph := map[int][]int{
        0: {1, 2},
        1: {2},
        2: {0, 3},
        3: {3},
    }
    fmt.Println("BFS starting from node 2:")
    bfs(graph, 2)
}

Real-World Applications of Sorting and Searching

• Database Indexing: Searching and retrieving records efficiently.
• Data Analytics: Sorting datasets for meaningful insights.
• Pathfinding: Using DFS and BFS in AI and game development.
• Search Engines: Binary search for ranked results and data storage.
• Networking: Shortest-path algorithms rely on BFS and DFS.