Bubble sort in Go

I recently started to implement basic algorithms using Go just for practice and learning purposes. I started with Bubble Sort. So in this article we are going to implement a bubble sort algorithm for integers and for any type.

According to GeekforGeeks:

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.

Sounds simple enough for me.

This is an example of how it should work:

first pass
5 1 4 1 original array
1 5 4 1 swap 1 5
1 5 1 4 swap 1 4

second pass
1 5 1 4 don't swap 1 5 (0 and 1 index)
1 1 5 4 swap 1 5 (1 and 2 index)
1 1 4 5 swap 4 5

third pass (don't swap anything)
1 1 4 5
1 1 4 5
1 1 4 5

So on the third pass algorithm went through the entire array and didn't swap anything, that's how we know the array is sorted.

So what are we gonna sort? Numbers? Strings? Go doesn't have generics (yet), so we could either just use a specific data type, like int, or we could use an interface for "comparable" items. Let's implement it for integers first.

So the first thing we need to do is iterate the array to compare the "current" item with the "next" item (xs[i] > xs[i + 1]), we need a "for i" loop for that:

for i := 0; i < len(xs) - 1; i++ {

Normally when we iterate we use i < len(xs) but we need to stop at the element before the last element to prevent "index out of range exception" because we accessing the i + 1 element.

Then we compare the elements:

if xs[i] > xs[i + 1] {

If that's true we should swap the elements. We can do that so:

xs[i], xs[i + 1] = xs[i + 1], xs[i]

So we get the following:

for i := 0; i < len(xs) - 1; i++ {
    if xs[i] > xs[i + 1] {
        xs[i], xs[i + 1] = xs[i + 1], xs[i]
    }
}

So that will only one step through the array, we need to do that until the array is sorted, that's how we'll do it:

for {
    sorted := true
    for i := 0; i < len(xs) - 1; i++ {
        if xs[i] > xs[i + 1] {
            xs[i], xs[i + 1] = xs[i + 1], xs[i]
            sorted = false
        }
    }
    if sorted {
        break
    }
}

So if we swapped the elements a single time, that means the array is not sorted. And if we haven't swapped the elements that mean the array is sorted.

And don't forget to check for the edge cases:

if len(xs) < 2 {
    return xs
}

So here is the full implementation:

func bubbleSort(xs []int) {
    if len(xs) < 2 {
        return
    }
    for {
        sorted := true
        for i := 0; i < len(xs) - 1; i++ {
            if xs[i] > (xs[i + 1]) {
                xs[i], xs[i + 1] = xs[i + 1], xs[i]
                sorted = false
            }
        }
        if sorted {
            break
        }
    }
}

Ok, for the last part let's implement it using interfaces so that we can sort anything, not only integers:

For that algorithm we just need to know whether the element is greater than the other element:

Comparable interface {
        GreaterThan(Comparable) bool
}

We will be using it like so itemA.GreaterThan(itemB).

The implementation will look like this, it's the same but with interfaces:

func bubbleSort(xs []Comparable) {
    if len(xs) < 2 {
        return
    }
    for {
        sorted := true
        for i := 0; i < len(xs) - 1; i++ {
            if xs[i].GreaterThan(xs[i + 1]) {
                xs[i], xs[i + 1] = xs[i + 1], xs[i]
                sorted = false
            }
        }
        if sorted {
            break
        }
    }
}

And let's implement interfaces for uint64:

type ComparableUint64 uint64

func (u *ComparableUint64) GreaterThan(c Comparable) bool {
    x, ok := c.(*ComparableUint64)
    if !ok {
        panic("unexpected")
    }
    return uint64(*u) > uint64(*x)
}

Let's compare benchmarks for both solutions. First let's make a list of 1000 unsorted elements:

func generateBigList() []int {
    length := 1000
    min := 10
    max := 30
    result := make([]int, length)
    for i := 0; i < length; i++ {
        n := rand.Intn(max - min) + min
        result[i] = n
    }
    return result
}

It will generate the same array each time because we don't do rand.Seed.

The benchmark for integers:

func BenchmarkIntegers(b *testing.B) {
    bigList := generateBigList()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        bubbleSortInt(bigList)
    }
}

The benchmark for interfaces:

func BenchmarkInterface(bench *testing.B) {
    intList := generateBigList()
    comparableList := make([]Comparable, 1000)
    for i := range intList {
        item := ComparableUint64(intList[i])
        comparableList[i] = &item
    }
    bench.ResetTimer()
    for i := 0; i < bench.N; i++ {
        bubbleSortInterfaces(comparableList)
    }
}

goos: darwin
goarch: amd64
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz

BenchmarkIntegers-12         1000000          1034 ns/op

BenchmarkInterface-12         219705          4954 ns/op

And as we can see the interfaces solution is almost 5 times slower, I think this is a tradeoff.

When generics will come to Go generics solution will work for any type and I believe it will be as fast as the solution for a specific type.