Bubble Sort — An Introduction

This blog is an article introducing the basics of bubble sort. Bubble sort is one of the first algorithms I learned as a programmer and it was quite tough for me to understand the implementation. Two years into my degree and I feel I have been able to understand the concept in the best possible way from some amazing faculties and lectures I have had the opportunity to attend.

In this post, I will focus on Bubble Sort. I will explain what Bubble Sort is, how Bubble Sort is implemented as an algorithm. I will explain how time complexities work in this algorithm with some examples.

Bubble Sort Theory

“Bubble sorting would be the wrong way.” — Barack Obama

This algorithm is always one of the first concepts in computer science because it is a relatively easy concept for beginners.
Bubble sort splits a given array into two parts, sorted and unsorted. Let’s take an array as an example.

Like the motion of a bubble in water rising above the water surface, each array element moves towards its end in each iteration. That’s why it’s called bubble sort.

Working of Bubble Sort

You are trying to sort items in ascending order.

First Iteration (Compare and Swap)

1. Starting from the first index, compare the first and the second elements.
2. If the first element is greater than the second element, they are swapped.
3. Now, compare the second and the third elements. Swap them if they are not in order.
4. The above process goes on until the last element

Remaining Iteration

The same process goes on for the remaining iterations.

After each iteration, the largest element among the unsorted elements is placed at the end.

In each iteration, the comparison takes place up to the last unsorted element.

The array is sorted when all the unsorted elements are placed at their correct positions.

Bubble Sort Algorithm

bubbleSort(array)
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
end bubbleSort

Bubble Sort Implementation in C++

#include <iostream>
 
using namespace std;
 
// Sort arr[] of size n using Bubble Sort. 
void BubbleSort (int arr[], int n)
{
	int i, j;
	for (i = 0; i < n; ++i)
	{
		for (j = 0; j < n-i-1; ++j)
		{
			// Comparing consecutive data and switching values if value at j > j+1.
			if (arr[j] > arr[j+1])
			{
				arr[j] = arr[j]+arr[j+1];
				arr[j+1] = arr[j]-arr[j + 1];
				arr[j] = arr[j]-arr[j + 1];
			}
		}
		// Value at n-i-1 will be maximum of all the values below this index.
	}	
}	
 
int main()
{
	int n, i;
	cout<<"\nEnter the number of data element to be sorted: ";
	cin>>n;
 
	int arr[n];
	for(i = 0; i < n; i++)
	{
		cout<<"Enter element "<<i+1<<": ";
		cin>>arr[i];
	}
 
	BubbleSort(arr, n);
 
	// Display the sorted data.
	cout<<"\nSorted Data ";
	for (i = 0; i < n; i++)
        cout<<"->"<<arr[i];
 
	return 0;
}

Bubble Sort Code Explanation

1. Take input of data.
2. Call BubbleSort() function with ‘arr’ the array of data and ’n’ the number of values, in the argument list.
3. Implement Sorting algorithm using nested for loop.
4. The first loop will run on ‘i’ from 0 to n-1.
5. The second loop will run on ‘j’ from 0 to n-i-1.
6. Compare two consecutive values.
7. Switch the values if arr[j+1] <arr[j].
8. Return to main and display the result.
9. Exit.

Bubble Sort Complexity

Bubble Sort compares the adjacent elements.

Hence, the number of comparisons is

(n-1) + (n-2) + (n-3) +.....+ 1 = n(n-1)/2

nearly equals to n2

Hence, Complexity: O(n2)

Also, if we observe the code, bubble sort requires two loops. Hence, the complexity is n*n = n2

1. Time Complexities

• Worst Case Complexity: O(n2)
  If we want to sort in ascending order and the array is in descending order then the worst case occurs.
• Best Case Complexity: O(n)
  If the array is already sorted, then there is no need for sorting.
• Average Case Complexity: O(n2)
  It occurs when the elements of the array are in jumbled order (neither ascending nor descending).

2. Space Complexity

• Space complexity is O(1) because an extra variable is used for swapping.
• In the optimized bubble sort algorithm, two extra variables are used. Hence, the space complexity will be O(2).

Bubble Sort Applications

Bubble sort is used if

• complexity does not matter
• short and simple code is preferred

Overall Bubble Sort is an important concept to understand when it comes to algorithms. Thank you for reading this blog post. See you soon in another post where we talk about some other sorting algorithms.