Simple BubbleSort in GoLang

Question

I'm just starting in Go.

Please review the below code, and let me know what I can improve in this code.

//BubbleSort takes an []int {7,5,6,9,8} and returns {5,6,7,8,9}
func BubbleSort(arr []int) []int {
    keepRunning := true
    for keepRunning {
        keepRunning = false
        for i := 0; i < len(arr)-1; i++ {
            a := arr[i]
            b := arr[i+1]
            if a > b {
                arr[i], arr[i+1] = b, a
                keepRunning = true
            }
        }
    }
    return arr
}

//edit In this case, I'm doing return simply cause I want to return a new copy, and not modify the original.

But I recently as well learned about GO's GC tricolor pattern. Which will discard the variable until there are no connections left.

So I guess I will need to use the original variable and pass it around and let the code modify the original Slice itself.

Answer 1

let me know what I can improve in this code.

---

For a real-world code review, code should be correct, maintainable, reasonably efficient, and, most importantly, readable.

Writing code is a process of stepwise refinement.

Here's your code. Consider it as a first draft.

func BubbleSort(arr []int) []int {
    keepRunning := true
    for keepRunning {
        keepRunning = false
        for i := 0; i < len(arr)-1; i++ {
            a := arr[i]
            b := arr[i+1]
            if a > b {
                arr[i], arr[i+1] = b, a
                keepRunning = true
            }
        }
    }
    return arr
}

Simplify the code. Express the do ... until construct directly. Remove unnecessary variables. Remove the redundant return value. And so on.

func BubbleSort(a []int) {
    for {
        swap := false
        for i := 1; i < len(a); i++ {
            if a[i-1] > a[i] {
                a[i-1], a[i] = a[i], a[i-1]
                swap = true
            }
        }
        if !swap {
            return
        }
    }
}

Optimize the code. Each pass sorts at least one element to the top.

func BubbleSort(a []int) {
    for i := len(a); i > 0; i-- {
        swap := false
        for j := 1; j < i; j++ {
            if a[j-1] > a[j] {
                a[j-1], a[j] = a[j], a[j-1]
                swap = true
            }
        }
        if !swap {
            return
        }
    }
}

Seek further optimizations. Elements from and above the last swap are sorted.

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

Playground: https://play.golang.org/p/jpoUO5nsJEo

Output:

[7 5 6 9 8]
[5 6 7 8 9]

Write tests using the Go testing package.

Run benchmarks using the Go testing package.

---

Comment: I was wondering if I could remove the keepRunning bool somehow. and in the above case the swap variable – STEEL

---

The swap state variable is used to end the sort as soon as possible. It is not necessary.

For example,

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

Answer 2

As you only modify value position within the slice and not modify its headers, you do not need to return a slice.

//BubbleSort takes an []int {7,5,6,9,8} and returns {5,6,7,8,9}
func BubbleSort(arr []int) {
    keepRunning := true
    for keepRunning {
        keepRunning = false
        for i := 0; i < len(arr)-1; i++ {
            a := arr[i]
            b := arr[i+1]
            if a > b {
                arr[i], arr[i+1] = b, a
                keepRunning = true
            }
        }
    }
}

https://play.golang.org/p/d6wrZ0DYIuG

that is because slice headers are passed by value, but slice backing array is a pointer. Thus modifying value index does not require to pass around the headers, unlike append.

you could try to figure out how to implement it using a more agnostic API.

IE something like BubbleSort(arr []interface{})

then benchmark it against a standard sort.Slice(interface{}).