## 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.

## 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
}
}
}
}
``````