Sorting in Go using Bubble sort

Go has its own package for handing sorting – called “sort” but in this post we are going to use the Go language to implement a sorting algorithm called Bubble sort.

Problem definition: Given a slice of integers sort them in ascending order

Bubble sort is an iterative comparison algorithm that sorts the elements by swapping them around if they are out of order. If a larger element comes before a smaller one => swap them and move on to the next position of the array.

Example

Assume we have the following list of integers that we would like to sort using our very own Bubble sort

{6, 5, 3, 1, 8, 7, 2, 4} // n = 8

The algorithm is going to perform n = 8 iterations, one for each possible length of the array and at each iteration it is going to perform m = n - 1 pair comparisons.
After its of the n iterations the largest item of the sub-array is going to find its way to its correct location in the final sorted array. This means that:

  • after the 1st iteration 8 should be at position n=7 of the list
  • after the 2nd iteration 7 should be at position n=6 of the list etc.

In the images below we can see the starting view of the list of integers at each iteration along with the comparisons that the algorithm is going to perform in each iteration. Green means that the element is at its rightful place and is not taking part in the current iteration.

Iterations of the Bubble sort algorithm

Implementation

The implementation of the algorithm in Go is really straightforward as all we need to implement is two nested for loops and a helper method that will allow us to swap two elements.

Let’s start with the swap method. In Go slices passed as arguments in a method can be modified from within the method so all we need to pass to our method is our slice and the positions we want to swap.

func swap(nums []int32, i, j int) {
	tmp := nums[i]
	nums[i] = nums[j]
	nums[j] = tmp
}

Next we can implement the nested for loops we discussed about earlier

func BubbleSort(nums []int32) {
	for n := len(nums); n > 1; n-- {
		for j := 1; j < n; j++ {
			if nums[j-1] > nums[j] {
				swap(nums, j-1, j)
			}
		}
	}
}

I have uploaded the full implementation and testing in this Github library. The Github version of the code also includes another optimization we can introduce that allows the algorithm to terminate early if all the elements are in the right order.

Complexity

Bubble sort is not an efficient algorithm – not even by far 😄. It’s average complexity is О(n2) which means that you are probably better off trying something else.

Bubble sort performs best if the input is already sorted as in this case it will have complexity О(n). On its first iteration the algorithm will make 0 swaps and therefore terminate early (see the Github file for Bubble sort for this optimization).

On the plus side it is very easy to understand and for really sort inputs it really does not make much of a difference what you use.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s