Bubble sort in Go
Tags: algorithms, datastructures, go, programming
Published: 2021-03-05 08:51:50

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:

```markdown
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:

```json
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:

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

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

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

So we get the following:

```json
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:

```go
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:

```go
if len(xs) < 2 {
	return xs
}
```

So here is the full implementation:

```go
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:

```go
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:

```go
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`:

```go
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:

```go
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:

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

The benchmark for interfaces:

```go
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)
	}
}
```

```bash
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.