3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Do you have any reason to reimplement a slow sort instead of using a decent one already in the language? (this is true regardless of the language in question) \$\endgroup\$ – Nyos Oct 28 '19 at 16:57
  • 4
    \$\begingroup\$ @Nyos im just using it as means of learning. \$\endgroup\$ – STEEL Oct 28 '19 at 17:19
  • \$\begingroup\$ @Nyos as well not sure why ``` sort.Slice(elements, func(a, b int) bool { return a < b }) ``` does not work \$\endgroup\$ – STEEL Oct 28 '19 at 18:08
  • \$\begingroup\$ @STEEL: sort.Slice(elements, func(a, b int) bool { return a < b }) does not work because your less function is wrong. See sort func Slice: func Slice(slice interface{}, less func(i, j int) bool). For example, play.golang.org/p/uP5_XZHWqb8. \$\endgroup\$ – peterSO Oct 29 '19 at 13:00
8
\$\begingroup\$

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]
            }
        }
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks, @peterSO I have edited my OG post. I was wondering if I could remove the keepRunning bool somehow. and in the above case the swap variable \$\endgroup\$ – STEEL Oct 29 '19 at 15:15
1
\$\begingroup\$

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{}).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ In this case, I actually want to return and a new copy of Slice to avoid mutation. And any way to remove the keepRunning bool, any way kind like Python generator? \$\endgroup\$ – STEEL Oct 28 '19 at 18:04
  • \$\begingroup\$ in such case i believe it is better to provide the allocation-less implementation version of the algorithm and let the user create a slice and copy the data to it before the sort. \$\endgroup\$ – mh-cbon Oct 28 '19 at 18:06
  • \$\begingroup\$ idk what is a python generator. you don t want to prevent mutation by copy, it is slow. the keeprunning variable has little incidence. the size of the slice and the selected sort algorithm are more meaningful. The standard library provides efficient sort implementations that uses a lot of CS to provide the best. \$\endgroup\$ – mh-cbon Oct 28 '19 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.