package main

import (
    "fmt"
    "math"
)

func LinearSarch(a []int, key int) string {
    point := 0
    for point < len(a) {
        if key == a[point] {
            return fmt.Sprintf("found the index is %d", point)
        }
        point += 1
    }
    return "Not found Index"

}

func BinarySarch(a []int, key int, Left int, Right int) string {
    if Left <= Right {
        midPoint := int(math.Floor(float64(Left+Right) / 2))
        if key == a[midPoint] {
            return fmt.Sprintf("found the index is %d", midPoint)
        } else if key < a[midPoint] {
            return BinarySarch(a, key, Left, midPoint-1)
        } else {
            return BinarySarch(a, key, midPoint+1, Right)
        }
    }
    return "Not found"

}

func selection(a []int) {
    for i := 0; i < len(a)-1; i++ {
        min := i
        for j := i + 1; j < len(a); j++ {
            if a[j] < a[min] {
                min = j
            }
        }
        temp := a[i]
        a[i], a[min] = a[min], temp
    }

}

func insertion(a []int) {
    for i := 1; i < len(a); i++ {
        temp := a[i]
        j := i - 1
        for j >= 0 && a[j] > temp {
            a[j+1] = a[j]
            j--
        }
        a[j+1] = temp

    }

}

func bubblesort(a []int) {
    for i := 0; i < len(a)-1; i++ {
        for j := 0; j < len(a)-1-i; j++ {
            if a[j] > a[j+1] {
                temp := a[j]
                a[j] = a[j+1]
                a[j+1] = temp
            }
        }

    }

}

func sellsort(arr []int, n int) {
    for gap := n / 2; gap > 0; gap = gap / 2 {
        for j := gap; j < n; j++ {
            for i := j - gap; i >= 0; i -= gap {
                if arr[i+gap] > arr[i] {
                    break
                } else {
                    temp := arr[i]
                    arr[i] = arr[i+gap]
                    arr[i+gap] = temp
                }

            }

        }
    }

}
func partition(arr []int, lb int, ub int) int {
    pivot := arr[lb]
    start := lb
    end := ub
    for start < end {
        if arr[start] <= pivot {
            start += 1
        }
        for arr[end] > pivot {
            end -= 1
        }
        if start < end {
            temp := arr[start]
            arr[start] = arr[end]
            arr[end] = temp
         }
    }
    temp := arr[lb]
    arr[lb] = arr[end]
    arr[end] = temp
    return end
}

func quikSort(arr []int, lb int, ub int) {
    if lb < ub {
        p := partition(arr, lb, ub)
        quikSort(arr, lb, p-1)
        quikSort(arr, p+1, ub)
    }
}

func main() {
    a := []int{10, 20, 30, 10, 5, 3, 2}
    bubblesort(a)
    sellsort(a, len(a))
    insertion(a)
    selection(a)
    fmt.Println(a)
    b := BinarySarch(a, 30, 0, len(a)-1)
    q := LinearSarch(a, 30)
    fmt.Println(b, q)

}