Bubble Sort Algorithm Tutorial

Bubble Sort is the simplest sorting algorithm that works by repeatedly comparing the adjacent elements and swapping them if they are in the wrong order. The swapping & passes through a list are repeated until all the elements are not sorted.

The best-case time complexity of Bubble Sort is O(N) and occurs when all the elements in the list are in sorted order, but in the worst case, the complexity becomes O(N²)

Working of Bubble Sort

Let’s understand how the bubble sort works by taking the unsorted array with elements [15 11 14 12 18]

First Pass

(15 11 14 12 18) => (11 15 14 12 18),        since 15 is greater than 11, so we will swap 15 & 11.
(11 15 14 12 18) => (11, 14 15 12 18),       since 15 > 14, swap 15 & 14
(11 14 15 12 18) => (11 14 12 15 18),        since 15 > 12, swap 15 & 12
(11 14 12 15 18) => (11 14 12 15 18),        15 < 18, hence no swapping

Second Pass

(11 14 12 15 18) => (11 14 12 15 18)
(11 14 12 15 18) => (11 12 14 15 18),        since 14 > 12, swap 14 & 12
(11 12 14 15 18) => (11 12 14 15 18)
(11 12 14 15 18) => (11 12 14 15 18)
Now, the array is already sorted, but the algorithm doesn’t know. Hence it will run one more pass without any swap to know it is sorted

Third Pass

(11 12 14 15 18) => (11 12 14 15 18)
(11 12 14 15 18) => (11 12 14 15 18)
(11 12 14 15 18) => (11 12 14 15 18)
(11 12 14 15 18) => (11 12 14 15 18)
This is how the bubble sort will works.

Algorithm

BubbleSort(arr, size){
    //boolean varible to check if elements are swapped
    swapped = false;

    for i in range(0 to size-1){
        //start with assumption that no elements are swapped
        swapped = false;
        for j in range(0 to size-i-1){
            if(arr[j]>arr[j+1]){
                //if element are swapped the mark swapped true 
                swap(arr[i], arr[j]);
                swapped = true;
            }
            /*if no elements are swapped, it means
             the is now sorted */ 
            if(swapped == false)
                break;
        }
    }
    return 
}

Implementation of the above algorithm is CPP

#include <bits/stdc++.h>
using namespace std;

void swap(int *a, int *b){
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

int bubble_sort(int *arr, int size){

	bool swapped;
	int i,j;

	for(i=0; i<size-1; i++)
	{
		swapped = false;
		for(j=0; j<size-i-1; j++)
		{
			if(arr[j]>arr[j+1])
			{
				swap(&arr[j], &arr[j+1]);
				swapped = true;
			}
		}

		if(swapped == false)
			break;
	}

	return 0;
}

int main(){

	int arr[] = {15, 11, 14, 12, 18};
	int arr_size = sizeof(arr)/sizeof(arr[0]);

	bubble_sort(arr, arr_size);
	
	cout<<"Sorted array is:"<<endl;
	for(int i=0; i<arr_size; i++)
		cout<<arr[i]<<" ";
	cout<<endl;

	return 0;
}

Output

Sorted array is:
11 12 14 15 18

Time complexity

The time complexity of BubbleSort is O(N²) in the worst case because in worst case we have to compare every element with every other element N time, where N is number of elements in the array. The best-case time complexity is O(N) and the sorted array only will result in best-case complexity.

Bubble Sort properties at a glance:

1. Best case time complexity = O(N)
2. Worst-case time complexity = O(N²)
3. Auxiliary space requirement = O(1)
4. Number of comparisons required = O(N²)
5. BubbleSort is an in-place sorting algorithm
6. Bubble Sort is a stable sort

Did, we miss something, or do you want to add some other key points?
Please comment.