What is Bubble sort

The Bubble sort algorithm is one of the most simple sorting algorithms out there. It repeatedly steps trough a list of elements, compares adjacent elements and swaps them if they are in the wrong order. Or at least that’s what Wikipedia just says.

I know that you already know what a Bubble sort algorithm is

Bubble sort is one of the most famous algorithms in the world. Even if you’re a newbie and have just started to programming today it’s quite possible that you’ve already seen some reference to it.

If by some very reason it’s not your case you can go to the final section of this article to find more information about the algorithm itself and how it works.

This article is just an excuse to revisit this algorithm and how it works.

A naive solution

// To find out the final code instead of only the algorithm
// check the Go Playground link.
// [...]

// BubbleSort receives an slice of integers that
// sorts in O(n^2).
func BubbleSort(nums []int) {
	items := len(nums)

	// We run the outer loop items - 1 times.
	// Because at the end of each iteration we should
	// have to bubbled up ith smallest item.
	for i := 1; i < items-1; i++ {

		// We then run a inner loop on the rest of the
		// unsorted slice.
		for j := items - 1; j >= i; j-- {
			if nums[j] < nums[j-1] {
				nums[j], nums[j-1] = nums[j-1], nums[i]
			}
		}
	}
}

It may appear that the code above is “correct”. And it is. But there is a little problem. What if, for example, the slice ends up sorted after the first or the second round?

A little optimization

// [...]

// BubbleSort receives an slice of integers that
// sorts in O(n^2).
func BubbleSort(nums []int) {
	var sorted bool
	items := len(nums)

	// We run the outer loop until we have sorted all the items.
	for !sorted {
		// In each iteration we are going to
		// change sorted to true.
		sorted = true

		// Now we're going to range over our slice checking
		// if they're sorted or not.
		for i := 1; i < items; i++ {

			// If they're not sorted we swap them and change
			// sorted to false to loop again.
			if nums[i-1] > nums[i] {
				nums[i-1], nums[i] = nums[i], nums[i-1]
				sorted = false
			}
		}
	}
}

Final code

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func main() {
	nums := randomSlice(100)
    fmt.Printf("original slice of %v elements: %v\n", len(nums), nums)
    fmt.Println()

	start := time.Now()
	BubbleSort(nums)
	end := time.Now()

	fmt.Printf("%v items ordered in %v\n", len(nums), end.Sub(start))
	fmt.Println(nums)
}

func randomSlice(size int) []int {
	s := make([]int, size, size)
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < size; i++ {
		s[i] = rand.Intn(100)
	}

	return s
}

func BubbleSort(nums []int) {
	var sorted bool
	items := len(nums)

	for !sorted {
		sorted = true
		for i := 1; i < items; i++ {
			if nums[i-1] > nums[i] {
				nums[i-1], nums[i] = nums[i], nums[i-1]
				sorted = false
			}
		}
	}
}

Go playground

You check the code in the Go Playground click here.

Due to how time works on the Go Playground you would be unable to check the performance of the algorithm.