Sorting is one of the most basic operations you can apply to data. You can sort elements in different programming languages using various sorting algorithms like Quick Sort, Bubble Sort, Merge Sort, Insertion Sort, etc. Bubble Sort is the most simple algorithm among all these.
In this article, you'll learn about the working of the Bubble Sort algorithm, the pseudocode of the Bubble Sort algorithm, its time and space complexity, and its implementation in various programming languages like C++, Python, C, and JavaScript.
How Does the Bubble Sort Algorithm Work?
Bubble Sort is the simplest sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order. This concept can be explained more efficiently with the help of an example. Consider an unsorted array with the following elements: {16, 12, 15, 13, 19}.
Example:
Here the adjacent elements are compared and if they're not in ascending order, they're swapped.
Pseudocode of the Bubble Sort Algorithm
In pseudocode, the Bubble Sort algorithm can be expressed as:
bubbleSort(Arr[], size)
// loop to access each array element
for i=0 to size-1 do:
// loop to compare array elements
for j=0 to size-i-1 do:
// compare the adjacent elements
if Arr[j] > Arr[j+1] then
// swap them
swap(Arr[j], Arr[j+1])
end if
end for
end for
end
The above algorithm processes all the comparisons even if the array is already sorted. It can be optimized further by stopping the algorithm if the inner loop didn’t cause any swap. This will reduce the execution time of the algorithm.
Thus, the pseudocode of the optimized Bubble Sort algorithm can be expressed as:
bubbleSort(Arr[], size)
// loop to access each array element
for i=0 to size-1 do:
// check if swapping occurs
swapped = false
// loop to compare array elements
for j=0 to size-i-1 do:
// compare the adjacent elements
if Arr[j] > Arr[j+1] then
// swap them
swap(Arr[j], Arr[j+1])
swapped = true
end if
end for
// if no elements were swapped that means the array is sorted now, then break the loop.
if(not swapped) then
break
end if
end for
end
Time Complexity and Auxiliary Space of the Bubble Sort Algorithm
The worst-case time complexity of the Bubble Sort Algorithm is O(n^2). It occurs when the array is in descending order and you want to sort it in ascending order or vice-versa.
The best-case time complexity of the Bubble Sort Algorithm is O(n). It occurs when the array is already sorted.
The average-case time complexity of the Bubble Sort Algorithm is O(n^2). It occurs when the elements of the array are in jumbled order.
The auxiliary space required for the Bubble Sort algorithm is O(1).
C++ Implementation of the Bubble Sort Algorithm
Below is the C++ implementation of the Bubble Sort algorithm:
// C++ implementation of the
// optimised Bubble Sort algorithm
#include <iostream>
using namespace std;
// Function to perform Bubble Sort
void bubbleSort(int arr[], int size) {
// Loop to access each element of the array
for (int i=0; i<(size-1); i++) {
// Variable to check if swapping occurs
bool swapped = false;
// loop to compare two adjacent elements of the array
for (int j = 0; j < (size-i-1); j++) {
// Comparing two adjacent array elements
if (arr[j] > arr[j + 1]) {
// Swap both elements if they're
// not in correct order
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no elements were swapped that means the array is sorted now,
// then break the loop.
if (swapped == false) {
break;
}
}
}
// Prints the elements of the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {16, 12, 15, 13, 19};
// Finding the length of the array
int size = sizeof(arr) / sizeof(arr[0]);
// Printing the given unsorted array
cout << "Unsorted Array: " << endl;
printArray(arr, size);
// Calling bubbleSort() function
bubbleSort(arr, size);
// Printing the sorted array
cout << "Sorted Array in Ascending Order:" << endl;
printArray(arr, size);
return 0;
}
Output:
Unsorted Array:
16 12 15 13 19
Sorted Array in Ascending Order:
12 13 15 16 19
Python Implementation of the Bubble Sort Algorithm
Below is the Python implementation of the Bubble Sort algorithm:
# Python implementation of the
# optimised Bubble Sort algorithm
# Function to perform Bubble Sort
def bubbleSort(arr, size):
# Loop to access each element of the list
for i in range (size-1):
# Variable to check if swapping occurs
swapped = False
# loop to compare two adjacent elements of the list
for j in range(size-i-1):
# Comparing two adjacent list elements
if arr[j] > arr[j+1]:
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
swapped = True
# If no elements were swapped that means the list is sorted now,
# then break the loop.
if swapped == False:
break
# Prints the elements of the list
def printArray(arr):
for element in arr:
print(element, end=" ")
print("")
arr = [16, 12, 15, 13, 19]
# Finding the length of the list
size = len(arr)
# Printing the given unsorted list
print("Unsorted List:")
printArray(arr)
# Calling bubbleSort() function
bubbleSort(arr, size)
# Printing the sorted list
print("Sorted List in Ascending Order:")
printArray(arr)
Output:
Unsorted List:
16 12 15 13 19
Sorted List in Ascending Order:
12 13 15 16 19
C Implementation of the Bubble Sort Algorithm
Below is the C implementation of the Bubble Sort algorithm:
// C implementation of the
// optimised Bubble Sort algorithm
#include <stdio.h>
#include <stdbool.h>
// Function to perform Bubble Sort
void bubbleSort(int arr[], int size) {
// Loop to access each element of the array
for (int i=0; i<(size-1); i++) {
// Variable to check if swapping occurs
bool swapped = false;
// loop to compare two adjacent elements of the array
for (int j = 0; j < (size-i-1); j++) {
// Comparing two adjacent array elements
if (arr[j] > arr[j + 1]) {
// Swap both elements if they're
// not in correct order
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no elements were swapped that means the array is sorted now,
// then break the loop.
if (swapped == false) {
break;
}
}
}
// Prints the elements of the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf(" \n ");
}
int main() {
int arr[] = {16, 12, 15, 13, 19};
// Finding the length of the array
int size = sizeof(arr) / sizeof(arr[0]);
// Printing the given unsorted array
printf("Unsorted Array: \n");
printArray(arr, size);
// Calling bubbleSort() function
bubbleSort(arr, size);
// Printing the sorted array
printf("Sorted Array in Ascending Order: \n");
printArray(arr, size);
return 0;
}
Output:
Unsorted Array:
16 12 15 13 19
Sorted Array in Ascending Order:
12 13 15 16 19
JavaScript Implementation of the Bubble Sort Algorithm
Below is the JavaScript implementation of the Bubble Sort algorithm:
// JavaScript implementation of the
// optimised Bubble Sort algorithm
// Function to perform Bubble Sort
function bubbleSort(arr, size) {
// Loop to access each element of the array
for(let i=0; i<size-1; i++) {
// Variable to check if swapping occurs
var swapped = false;
// loop to compare two adjacent elements of the array
for(let j=0; j<size-i-1; j++) {
// Comparing two adjacent array elements
if(arr[j] > arr[j+1]) {
// Swap both elements if they're
// not in correct order
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swapped = true;
}
// If no elements were swapped that means the array is sorted now,
// then break the loop.
if (swapped == false) {
break;
}
}
}
}
// Prints the elements of the array
function printArray(arr, size) {
for (let i=0; i<size; i++) {
document.write(arr[i] + " ");
}
document.write("
")
}
var arr = [16, 12, 15, 13, 19];
// Finding the length of the array
var size = arr.length;
// Printing the given unsorted array
document.write("Unsorted Array:
");
printArray(arr, size);
// Calling bubbleSort() function
bubbleSort(arr, size);
// Printing the sorted array
document.write("Sorted Array in Ascending Order:
");
printArray(arr, size);
Output:
Unsorted Array:
16 12 15 13 19
Sorted Array in Ascending Order:
12 15 13 16 19
Now You Understand the Working of the Bubble Sort Algorithm
Bubble Sort is the simplest sorting algorithm and is mainly used to understand the foundations of sorting. Bubble Sort can also be implemented recursively, but it provides no additional advantages to do so.
Using Python, you can implement the Bubble Sort algorithm with ease. If you're unfamiliar with Python and want to kickstart your journey, starting off with a "Hello World" script is a great choice.