Free Data Structures and Algorithms courses with real-time projects Start Now!!
Ever witnessed a car racing tournament? There are multiple laps in a race. While the race is in progress, let’s say team A is in 4th position. Team B is just behind team A and Team C is ahead of Team A. Now, in lap 1, if team A is faster than team C, it will overtake it. In other words, teams A and C swap their positions. Similarly, if team E is faster than team F, they will swap positions. In the next lap, Team B and C might swap positions depending on their speed comparisons.
A bubble sort algorithm works in a similar manner. Consider each lap as one iteration. It swaps all the places not in order in a single iteration and moves to the next iteration. Here, we will learn the working of the bubble sort algorithm, and an optimized approach for the same.
Bubble sort
Bubble sort is the simplest sorting algorithm. Sorting is the process of arranging the elements in a dataset either in ascending or descending order. In this comparison-based sorting algorithm, each pair of adjacent elements is compared. If the elements are not found to be in the required order, they are swapped.
1. After each iteration, the largest remaining element is at the highest index. (while arranging in ascending order.)
2. Swaps adjacent elements only.
Working of bubble sort
1. Start for the starting index. Compare the current element to the next element.
2. If the current element and next element are not in order, swap them.
3. Repeat step 2 until you reach the end of the array. This is the end of iteration 1.
4. Repeat steps 1, 2, 3 until the array is sorted.
Bubble Sort Algorithm
Step 1: Repeat For i = 0 to N-1
Step 2: Repeat For j = i + 1 to N - I
Step 3: If Arr[ j ] > Arr[ i ]
swap Arr[ j ] and Arr[ i ]
[end of step 2]
[end of step 1]
Step 4: stop
Bubbel Sort Pseudocode
procedure bubbleSort( array)
len = array.length;
for i = 0 to loop-1 do:
for j = 0 to loop-1 do:
if list[j] > list[j+1] then
swap( list[j], list[j+1] )
end if
end for
end for
return array
end procedure
Example of Bubble Sort
Let’s sort the characters in the word “DATAFLAIR” by the bubble sort technique.
ITERATION 1
Technology is evolving rapidly!
Stay updated with DataFlair on WhatsApp!!
After iteration 1 ‘T’, the largest element is set at the last position.
ITERATION 2
ITERATION 3
ITERATION 4
ITERATION 5
ITERATION 6
ITERATION 7
ITERATION 8
Stability of Bubble sort algorithm
The stability of sorting algorithms comes into the picture when the same element is present more than once in a dataset. If the same elements in the unsorted dataset appear in the same order in the sorted dataset, then the algorithm is said to be a stable algorithm.
In the above example, the letter ‘A’ appears three times in the original array in the order RED, GREEN, and YELLOW. In the final sorted array after iteration 8, the order of A’s is the same as in the original. Hence, we can say that bubble sort is a stable sorting algorithm.
Implementation of Bubble sort in C
#include <stdio.h>
void main()
{
int arr[] = {34,8,25,45,13,70,54,68,100,3,92,86};
int len = 12;
for (int i = 0; i < len - 1; i++)
{
for (int j = 0; j < len - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
printf("Sorted Array:\n");
for (int i = 0; i < len - 1; i++)
{
printf("%d ",arr[i]);
}
}
Bubble sort Implementation in C++
#include <iostream>
using namespace std;
int main()
{
int arr[] = {34,8,25,45,13,70,54,68,100,3,92,86};
int len = 12;
for (int i = 0; i < len - 1; i++)
{
for (int j = 0; j < len - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
cout << "Sorted Array:\n";
for (int i = 0; i < len - 1; i++)
{
cout << " " << arr[i];
}
}
Bubble sort Implementation in Java
public class Bubblesort
{
static void bubbleSort(int arr[])
{
int i,j,len;
len = arr.length;
Boolean swap;
for (i = 0; i < len - 1; i++)
{
for (j = 0; j < len - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.println("Sorted Array:");
for (i = 0; i < len - 1; i++)
System.out.print(arr[i]+" ");
}
public static void main(String args[])
{
int[] data = {34,8,25,45,13,70,54,68,100,3,92,86 };
Bubblesort.bubbleSort(data);
}
}
Implementation of Bubble sort in Python
def bubbleSort(array):
for i in range(len(array)):
for j in range(0, len(array) - i - 1):
if array[j] > array[j + 1]:
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
data = [34,8,25,45,13,70,54,68,100,3,92,86]
bubbleSort(data)
print('Sorted Array:')
print(data)
Optimized Bubble sort
In the example we discussed above, you can clearly see that even if the array is sorted, all the comparisons and iterations are still performed. This results in higher execution time, and more comparisons that are useless since the array is already sorted. The last swap in the above example is done in iteration 4. But still, the program continues to compare until iteration 8 which is useless and inefficient.
To counter this problem, we introduce a binary variable that is set to a false value. If even one swap is made in the array during sorting, it changes to true, else it remains false. If after any iteration, it is not changed, then the array is sorted and no need for further comparisons.
In the above example, if we apply optimized bubble sort, then the execution will be stopped after iteration 5 since no swap is made there.
Algorithm of Optimized Bubble Sort
Step 1: Repeat For i = 0 to N-1
Swap = false
Step 2: Repeat For j = i + 1 to N - I
Step 3: If Arr[ j ] > Arr[ i ]
swap Arr[ j ] and Arr[ i ]
swap = true
[end of step 2]
If swap == false
Goto step 4
[end of step 1]
Step 4: stop
Optimized Bubble Sort Pseudocode
procedure bubbleSort( array)
len = array.length;
for i = 0 to loop-1 do:
swap =false
for j = 0 to loop-1 do:
if list[j] > list[j+1] then
swap( list[j], list[j+1] )
swap = true
end if
end for
If swap = = false
break;
end for
return array
end procedure
Implementation of Optimized bubble sort in C
#include <stdio.h>
void main()
{
int arr[] = {34,8,25,45,13,70,54,68,100,3,92,86};
int len = 12, swap;
for (int i = 0; i < len - 1; i++)
{
swap=0;
for (int j = 0; j < len - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swap =1;
}
}
if (swap == 0)
break;
}
printf("Sorted Array:\n");
for (int i = 0; i < len - 1; i++)
{
printf("%d ",arr[i]);
}
}
Optimized bubble sort Implementation in C++
#include <iostream>
using namespace std;
int main()
{
int arr[] = {34,8,25,45,13,70,54,68,100,3,92,86};
int len = 12,swap;
for (int i = 0; i < len - 1; i++)
{
swap=0;
for (int j = 0; j < len - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swap =1;
}
}
if (swap ==0)
break;
}
cout << "Sorted Array:\n";
for (int i = 0; i < len - 1; i++)
{
cout << " " << arr[i];
}
}
Optimized bubble sort Implementation in Java
public class Bubblesort
{
static void bubbleSort(int arr[])
{
int i,j,len;
len = arr.length;
Boolean swap;
for (i = 0; i < len - 1; i++)
{
swap = false;
for (j = 0; j < len - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swap = true;
}
}
if (swap==false)
break;
}
System.out.println("Sorted Array:");
for (i = 0; i < len - 1; i++)
System.out.print(arr[i]+" ");
}
public static void main(String args[])
{
int[] data = {34,8,25,45,13,70,54,68,100,3,92,86 };
Bubblesort.bubbleSort(data);
}
}
}
Implementation of Optimized bubble sort in Python
def bubbleSort(array):
for i in range(len(array)):
swap = false
for j in range(0, len(array) - i - 1):
if array[j] > array[j + 1]:
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
swap = true;
if swap==false:
break;
data = [34,8,25,45,13,70,54,68,100,3,92,86]
bubbleSort(data)
print('Sorted Array:')
print(data)
Complexity of Bubble Sort
In Bubble sort, adjacent elements are compared.
| iteration | comparisons |
| 1 | (n-1) |
| 2 | (n-2) |
| 3 | (n-3) |
| . | . |
| . | . |
| . | . |
| n-1 | 1 |
Total number of comparison :
(n-1) + (n-2) + (n-3) ………. + 1
= n(n-1)/2 ≈ n^2 ( complexity)
Best Case Complexity: When elements are already sorted.
Average Case Complexity: When elements are jumbled i.e. they are neither in ascending or descending order.
Worst Case Complexity: When elements are sorted in the opposite of the required order.
Space complexity: One extra variable, temp, is used to swap the variables.
| Scenario | Complexity |
| Worst case | O(n^2) |
| Average case | O(n) |
| Best case | O(n^2) |
| space | O(1) |
Advantages of Bubble sort
1. Used in computer graphics since it can detect very small errors and can fix it in O(2n) time.
2. Easy to Understand.
3. Minimum space requirement as compared to other sorting algorithms.
Disadvantages of bubble sort
1. Not suitable for large datasets.
Conclusion
Bubble sort is the easiest sorting algorithm. Bubble sort is a stable algorithm where the order of the same elements remains unchanged.
Though the worst-case complexity of this algorithm does not make this suitable for very large datasets, by using the optimized version of the bubble, the execution time can be improved to some extent for small datasets. We have also seen the working and implementation of the bubble sort algorithm.