The bubble sort algorithm compares two adjacent elements and swaps them if they are not in the intended order. For example,
Suppose we have an unsorted array with elements: 45, 1, 4.
Here, the bubble sort algorithm compares the first element 45 and second element 1. Since 45 is greater than 1, they are swapped (1, 45, 4).
Similarly, the new second element is compared with the next element. This process continues until all the elements are sorted.
Working of Bubble Sort Algorithm
Here, we are trying to sort the elements in ascending order.
1. First Iteration (Compare and Swap)
- Starting from the first index, compare the first and the second elements.
- If the first element is greater than the second element, they are swapped.
- Now, compare the second and the third elements. Swap them if they are not in order.
- The above process goes on until the last element.
Compare the Adjacent Elements
2. 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
Implementation of Bubble Sort in Python, Java and C/C++
# Bubble sort in Python
def bubbleSort(array):
# loop through each element of array
for i in range(len(array)):
# loop to compare array elements
for j in range(0, len(array) - i - 1):
# compare two adjacent elements
# change > to < to sort in descending order
if array[j] > array[j + 1]:
# swapping occurs if
# the first element is greater than second
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
data = [-2, 45, 0, 11, -9]
# call the bubbleSort() method
bubbleSort(data)
print('Sorted Array in Ascending Order:')
print(data)
// Bubble sort in Java
import java.util.Arrays;
class Main {
// method to perform the bubble sort
static void bubbleSort(int array[]) {
int size = array.length;
// loop to access each array element
for (int i = 0; i < size - 1; i++)
// loop to compare array elements
for (int j = 0; j < size - i - 1; j++)
// compare two adjacent elements
// change > to < to sort in descending order
if (array[j] > array[j + 1]) {
// swapping occurs if
// the first element is greater than second
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
// main method
public static void main(String args[]) {
int[] data = { -2, 45, 0, 11, -9 };
// call the method using the class name Main
Main.bubbleSort(data);
System.out.println("Sorted Array in Ascending Order:");
System.out.println(Arrays.toString(data));
}
}
// Bubble sort in C
#include <stdio.h>
// function to perform the bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < size - 1; ++step) {
// loop to compare array elements
for (int i = 0; i < size - step - 1; ++i) {
// compare two adjacent elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping occurs if
// the first element is greater than second
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}
// function to print array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// main function
int main() {
int data[] = {-2, 45, 0, 11, -9};
// find the length of the array
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
printf("Sorted Array in Ascending Order:\n");
// call function to print the array
printArray(data, size);
}
// Bubble sort in C++
#include <iostream>
using namespace std;
// function to perform bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < (size-1); ++step) {
// loop to compare array elements
for (int i = 0; i < size - (step-1); ++i) {
// compare two adjacent elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping occurs if
// the first element is greater than second
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}
// function to print array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
cout << " " << array[i];
}
cout << "\n";
}
// main function
int main() {
int data[] = {-2, 45, 0, 11, -9};
// find the length of the array
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
cout << "Sorted Array in Ascending Order:\n";
// call the function to print the array
printArray(data, size);
}
Optimized Bubble Sort Algorithm
In the above algorithm, all the comparisons are made even if the array is already sorted.
This increases the execution time.
To solve this, we can introduce an extra variable swapped. The value of swapped is set true if there occurs swapping of elements. Otherwise, it is set false.
After an iteration, if there is no swapping, the value of swapped will be false. This means elements are already sorted and there is no need to perform further iterations.
This will reduce the execution time and helps to optimize the bubble sort.
Algorithm for optimized bubble sort is
bubbleSort(array)
swapped <- false
for i <- 1 to indexOfLastUnsortedElement-1
if leftElement > rightElement
swap leftElement and rightElement
swapped <- true
end bubbleSort
Implementation of Optimized Bubble Sort
# Optimized bubble sort in python
def bubbleSort(array):
# loop through each element of array
for i in range(len(array)):
# keep track of swapping
swapped = False
# loop to compare array elements
for j in range(0, len(array) - i - 1):
# compare two adjacent elements
# change > to < to sort in descending order
if array[j] > array[j + 1]:
# swapping occurs if
# the first element is greater than second
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
swapped = True
# no swapping means the array is already sorted
# so no need of further comparison
if not swapped:
break
data = [-2, 45, 0, 11, -9]
# call the bubbleSort() method
bubbleSort(data)
print('Sorted Array in Ascending Order:')
print(data)
// Bubble sort in Java
import java.util.Arrays;
class Main {
// method to perform the bubble sort
static void bubbleSort(int array[]) {
int size = array.length;
// loop to access each array element
for (int i = 0; i < (size-1); i++) {
// check if swapping occurs
boolean swapped = false;
// loop to compare adjacent elements
for (int j = 0; j < (size-i-1); j++) {
// compare two array elements
// change > to < to sort in descending order
if (array[j] > array[j + 1]) {
// swapping occurs if
// the first element is greater than second
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
swapped = true;
}
}
// no swapping means the array is already sorted
// so no need of further comparison
if (!swapped)
break;
}
}
// main method
public static void main(String args[]) {
int[] data = { -2, 45, 0, 11, -9 };
// call the method using the class name Main
Main.bubbleSort(data);
System.out.println("Sorted Array in Ascending Order:");
System.out.println(Arrays.toString(data));
}
}
// Bubble sort in C
#include <stdio.h>
// method to perform the bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < size - 1; ++step) {
// check if swapping occurs
int swapped = 0;
// loop to compare array elements
for (int i = 0; i < size - step - 1; ++i) {
// compare two array elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping occurs if
// the first element is greater than second
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swapped = 1;
}
}
// no swapping means the array is already sorted
// so no need of further comparison
if (swapped == 0) {
break;
}
}
}
// function to print array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// main method
int main() {
int data[] = {-2, 45, 0, 11, -9};
// find the length of the array
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
printf("Sorted Array in Ascending Order:\n");
// call function to print the array
printArray(data, size);
}
// Optimized bubble sort in C++
#include <iostream>
using namespace std;
// function to perform bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < (size-1); ++step) {
// check if swapping occurs
int swapped = 0;
// loop to compare two elements
for (int i = 0; i < (size-step-1); ++i) {
// compare two array elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping occurs if
// the first element is greater than the second
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swapped = 1;
}
}
// no swapping means the array is already sorted
// so no need of further comparison
if (swapped == 0)
break;
}
}
// function to print an array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
cout << " " << array[i];
}
cout << "\n";
}
// main function
int main() {
int data[] = {-2, 45, 0, 11, -9};
// find the length of the array
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
cout << "Sorted Array in Ascending Order:\n";
// call the function to print the array
printArray(data, size);
}
Complexity of Bubble Sort
Bubble Sort is one of the simplest sorting algorithms that compare adjacent elements.
| Cycle | Number of Comparisons |
|---|---|
| 1st | (n-1) |
| 2nd | (n-2) |
| 3rd | (n-3) |
| ....... | ...... |
| last | 1 |
Here, number of comparisons
(n - 1) + (n - 2) + (n - 3) +.....+ 1 = n(n - 1) / 2
nearly equals to n2
Hence, Complexity: O(n2)
Also, if we simply observe the number of loops. The algorithm implements 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 temp is used for swapping. - In the optimized bubble sort algorithm, another variable swapped is used. Hence, the space complexity will be
O(2).
Applications of Bubble Sort
Bubble sort is used in the following cases where
- the complexity of the code does not matter.
- a short and simple code is preferred.