Algorithms

Bubble Sort

Bubble sort walks a slice comparing neighboring pairs and swapping the ones out of order, carrying the largest value to the end on every pass.

Strategy

Brute force

Compare every neighboring pair, and pass over the list again until a pass changes nothing.

Compare: look at one pair of neighbors.
Swap: put the larger of the two on the right.
Repeat: sweep again, one slot shorter each time, until a pass makes no swaps.

unsorted comparing now locked in place

Press Step to compare one pair at a time. The bigger number of each pair moves right, so the largest value floats to the end of the row.

Purpose

Put a slice of values in order, smallest to largest.

Input

An unsorted []int.

Output

The same slice, sorted in place.

Constraints

Every pass walks the whole unsorted stretch, so a long list takes a long time.
Equal values keep the order they arrived in, so the sort is stable.
Real sorting jobs go to slices.Sort. This one is for learning the idea.

How bubble sort works

You walk the list comparing each pair of neighbors, swapping them when they are the wrong way round. One pass carries the largest value to the end. Repeat until a pass makes no swaps.

It is slow on anything big, so you reach for it to learn the idea rather than to sort real data.

What bubble sort keeps track of

Name	Type	What it is for
a	[]int	The values you are sorting, shuffled in place.
n	int	How much of the slice is still unsorted.
i	int	The left value of the pair being compared.
swapped	bool	Whether this pass moved anything.

Walk through it

1 Start with a slice

It is sorted where it sits, so nothing comes back.

a := []int{8, 3, 7, 4, 9, 1, 5}

bubbleSort(a)

2 Compare a pair

Look at a value and the one next to it. If the left one is bigger, swap them.

if a[i] > a[i+1] {
    a[i], a[i+1] = a[i+1], a[i]
    swapped = true
}

3 Sweep the unsorted part

Do that for every neighboring pair, left to right. The largest value ends up at the far right.

for i := 0; i < n-1; i++ {
    // compare and swap
}

4 Shrink the range and go again

The last value is settled, so the next pass can stop one slot earlier.

for n := len(a); n > 1; n-- {
    // one sweep
}

5 Stop when a pass changes nothing

A sweep with no swaps means the list is already in order.

if !swapped {
    return
}

The whole program

Put it together and the slice comes out sorted in place, smallest to largest.

package main

import "fmt"

func bubbleSort(a []int) {
    for n := len(a); n > 1; n-- {
        swapped := false

        for i := 0; i < n-1; i++ {
            if a[i] > a[i+1] {
                a[i], a[i+1] = a[i+1], a[i]
                swapped = true
            }
        }

        if !swapped {
            return
        }
    }
}

func main() {
    a := []int{8, 3, 7, 4, 9, 1, 5}
    bubbleSort(a)
    fmt.Println(a)
}

Terminal

$ go run main.go
[1 3 4 5 7 8 9]

Previous Merge Sort Next Topic Insertion Sort