Simple Sort and Search

Bubble sort

• Without recursion

func bubbleSort(l []int) []int {
    repeat := true
    for repeat {
        repeat = false
        for i := 0; i < len(l)-1; i++ {
            if l[i+1] < l[i] {
                l[i], l[i+1] = l[i+1], l[i]
                repeat = true
            }
        }
    }
    return l
}

• With recursion

func bubbleSort(l []int) []int {
    repeat := false
    for i := 0; i < len(l)-1; i++ {
        if l[i+1] < l[i] {
            l[i], l[i+1] = l[i+1], l[i]
            repeat = true
        }
    }
    if repeat {
        bubbleSort(l)
    }
    return l
}

Merge Sort

• With recursion

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

func merge(left, right []int) []int {
    result := []int{}
    for len(left) > 0 || len(right) > 0 {
        if len(left) > 0 && len(right) > 0 {
            if left[0] < right[0] {
                result, left = append(result, left[0]), left[1:]
            } else {
                result, right = append(result, right[0]), right[1:]
            }
        } else if len(left) > 0 {
            result, left = append(result, left[0]), left[1:]
        } else {
            result, right = append(result, right[0]), right[1:]
        }
    }
    return result
}

Quick Sort

• With recursion

func quickSortRecursive(list []int) []int {
    if len(list) < 2 {
        return list
    }
    var left, right []int
    pivot := len(list) - 1
    pivotValue := list[pivot]
    list = append(list[0:pivot], list[pivot+1:]...)
    for i := 0; i < len(list); i++ {
        if list[i] < pivotValue {
            left = append(left, list[i])
        } else {
            right = append(right, list[i])
        }
    }
    result := append([]int{pivotValue}, quickSortRecursive(right)...)
    result = append(quickSortRecursive(left), result...)
    return result
}