How BubbleSort works

BubbleSort is a small sorting method which is quite fast for small amounts of data. BubbleSort works in-place, there is no need to create an extra array. BubbleSort is very naive in that it really compares every element.

It only swaps if two adjacent elements are not in the right order. In the best case it has an overhead of $O(n)$ if the list is sorted. Otherwise in average and worst case $O(n^2)$.

Here we can see how BubbleSort works. I have shortened it now, because it would be very long.

Implementation of BubbleSort

A small example implementation in "C++", shows how small the code is.

#include <iostream>
#include <vector>

void bubbleSort(std::vector<int> &v)
{
    for(int i = 0; i < v.size() -1 ; i++)
    {
        for(int j = 0; j < v.size() - i - 1; j++)
        {
            if(v[j] > v[j + 1])
            {
                int temp = v[j];
                v[j] = v[j + 1];
                v[j + 1] = temp;
            }
        }
    }
}

void show(std::vector<int> v)
{
    std::cout << "[";
    for(int i = 0; i < v.size(); i++)
    {
        std::cout << v[i] << ", ";
    }

    std::cout << "]" << std::endl;
}

int main()
{
    std::vector<int> v = {4,3,1,2,100,5,2,0,12,32,};
    show(v);
    bubbleSort(v);
    show(v);
}

The function bubbleSort is the sorting method, which takes the list to be sorted and walks through it from beginning to end. The inner loop, on the other hand, compares two adjacent elements and swaps them if necessary, if the element at position $j$ is larger than the element at position $j + 1$. The whole thing is then repeated $n - 1$ times, where n is the number of elements in the list. Since we passed the list as reference the sorting takes place in the original list.

I hope I was able to give a little insight into BubbleSort 😄