Table of contents
- What is Bubble sort
- Modified Bubble sort
- Bubble sort example
- Selection sort vs Bubble sort vs Insertion sort
What is Bubble Sort
Bubble sort is one of the easiest and brute force sorting algorithm. It is used to sort elements in either ascending or descending order. Every element is compared with every other element in bubble sort.
It basically does swapping of elements if they are not in the right order depending on their value and the intended order. A nested loop will be used to implement this algorithm.
Bubble Sort Pseudocode
- We are given with an input array which is supposed to be sorted in ascending order
- We start with the first element and i=0 index and check if the element present at i+1 is greater then we swap the elements at index i and i+1.
- If above is not the case, then no swapping will take place.
- Now “ i ” gets incremented and the above 2 steps happen again until the array is exhausted.
- We will ignore the last index as it is already sorted.
- Now the largest element will be at the last index of the array.
- Now we will again set i=0 and continue with the same steps that will eventually place second largest at second last place in the array. Now the last 2 indexes of the array are sorted.
Bubble Sort Algorithm
Bubble Sort(arr, size)
for i=0 to n-i-1
for j=0 to n-i-2
if arr[j]>arr[j+1]
Swap arr[j] and arr[j+1]Bubble Sort Algorithm Dry Run
input:
| 0 | 1 | 2 | 3 | 4 |
| 23 | 10 | 16 | 11 | 20 |
After i=0
| 0 | 1 | 2 | 3 | 4 |
| 10 | 16 | 11 | 20 | 23 |
After i=1
| 0 | 1 | 2 | 3 | 4 |
| 10 | 11 | 16 | 20 | 23 |
After i=2
| 0 | 1 | 2 | 3 | 4 |
| 10 | 11 | 16 | 20 | 23 |
After i=3
| 0 | 1 | 2 | 3 | 4 |
| 10 | 11 | 16 | 20 | 23 |
After i=4
| 0 | 1 | 2 | 3 | 4 |
| 10 | 11 | 16 | 20 | 23 |
Bubble Sort Time Complexity
- Each and every element is compared with the other elements for array which takes n time
- And the above steps continues for n iterations
- Best Time Complexity: O(n^2)
- Average Time Complexity: O(n^2)
- Worst Time Complexity: O(n^2)
Bubble Sort Space Complexity
- No auxiliary space is required in bubble sort implementation
- Hence space complexity is: O(1)
Now we are going to implement Bubble sort in different programming languages such as C,C++, Python, and Java
Bubble Sort in C
#include <stdio.h>
void bubbleSort(int arr[], int size) {
for (int j = 0; j < size - 1; ++j) {
for (int i = 0; i < size - j - 1; ++i) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
void display(int arr[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", arr[i]);
}
printf("n");
}
int main() {
int arr[] = {-2, 45, 0, 11, -9};
int size = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, size);
printf("Sorted array:n");
display(arr, size);
}
Output of the program:
Sorted array:
-9 -2 0 11 45
Bubble Sort in JAVA
class BubbleSort {
void bubbleSort(int arr[]) {
int size = arr.length;
for (int i = 0; i < size - 1; i++)
for (int j = 0; j < size - i - 1; j++)
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
void display(int arr[]) {
int size = arr.length;
for (int i = 0; i < size; i++)
System.out.println(arr[i]+" ");
}
public static void main(String args[]) {
int[] arr = { -2, 45, 0, 11, -9 };
BubbleSort bs = new BubbleSort();
bs.bubbleSort(arr);
System.out.println("Sorted array::");
bs.display(arr);
}
}
Output of the program:
Sorted array:
-9
-2
0
11
45
Bubble Sort in C++
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int size) {
for (int j = 0; j < size - 1; ++j) {
for (int i = 0; i < size - j - 1; ++i) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
void display(int arr[], int size) {
for (int i = 0; i < size; ++i) {
cout << " " << arr[i];
}
cout << "n";
}
int main() {
int arr[] = {-2, 45, 0, 11, -9};
int size = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, size);
cout << "Sorted array :n";
display(arr, size);
}
Output of the program:
Sorted array :
-9 -2 0 11 45
Bubble Sort in Python
def bubbleSort(array):
length = len(array)
for i in range(length-1):
for j in range(0, length-i-1):
if array[j] > array[j+1] :
array[j], array[j+1] = array[j+1], array[j]
arr = [10 7 8 9 1 5 ]
print ("Elements of array before sorting:")
Elements of array before sorting:
for i in range(len(arr)):
print ("%d" %arr[i]),
bubbleSort(arr)
print ("Elements of array after sorting:")
for i in range(len(arr)):
print ("%d" %arr[i]),
Output of the program:
Elements of array before sorting:
10 7 8 9 1 5
Elements of array after sorting:
1 5 7 8 9 10 Modified Bubble Sort
Bubble sort complexities remain o(n2) is all cases including sorted array. We can reduce the time complexity to O(n) if the array is already sorted.Also,we need to introduce a flag variable to stop the bubble sort as soon as it becomes sorted.
The flag variable is initialized as true in every iteration and in for loop if array goes in for swapping we will initialize it to false. But if no swapping takes place in the inner loop then its value will remain true and we will have an if condition after the nested loop that will check the flag value and if flag value remains true, we will break
Modified Bubble Sort Algorithm
bubbleSort(arr)
flag = false
for i=0 to n-1
for j=0 to n-1-i
if leftEle > rightEle
swap leftEle and rightEle
flag =true
if flag is true
break
end
Modified Bubble Sort Time Complexity
- Best Time Complexity : O(n), i.e when the elements in the given array are sorted.So, only once the every element is accessed or traversed.
- Average Time Complexity : O(n^2)
- Worst Time Complexity : O(n^2)
Modified Bubble Sort Space Complexity
- No auxiliary space is required in bubble sort implementation
- Hence space complexity is : O(1)
Modified Bubble Sort in C
#include <stdio.h>
void bubbleSort(int arr[], int size) { // sorting function
for (int j = 0; j < size - 1; ++j) {
int flag = 0;
for (int i = 0; i < size - j - 1; ++i) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
flag = 1;
}
}
if (flag == 0)
break;
}
}
void display(int arr[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", arr[i]);
}
printf("n");
}
int main() { // main function or driver function
int arr[] = {-2, 45, 0, 11, -9};
printf("Elements before Sorting:n");
display(arr, size);
int size = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, size);
printf("Elements after Sorting:n");
display(arr, size);
}Output of the program:
Elements before Sorting:
-2 45 0 11 -9 10
Elements after Sorting:
-9 -2 0 10 11 45 Modified Bubble Sort in JAVA
class BubbleSort {
void bubbleSort(int arr[]) { //sorting method
int size = arr.length;
for (int i = 0; i < size - 1; i++) {
boolean flag = true;
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = false;
}
}
if (flag == true)
break;
}
}
void display(int arr[]) { //method for displaying the elements
int size = arr.length;
for (int i = 0; i < size; i++)
System.out.println(arr[i]+" ");
}
public static void main(String args[]) { //main method or driver method
int[] arr = { -2, 45, 0, 11, -9 };
BubbleSort bs = new BubbleSort();
System.out.println("Elements before Sorting:");
bs.display(arr);
bs.bubbleSort(arr);
System.out.println("Elements after Sorting:");
bs.display(arr);
}
}
Output of the program:
Elements before Sorting:
-2
45
0
11
-9
Elements after Sorting:
-9
-2
0
11
45
Modified Bubble Sort in C++
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int size) { //sorting function
for (int j = 0; j < size - 1; ++j) {
int flag = 0;
for (int i = 0; i < size - j - 1; ++i) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
flag = 1;
}
}
if (flag == 0)
break;
}
}
void display(int arr[], int size) { // display function
for (int i = 0; i < size; ++i) {
cout << " " << arr[i];
}
cout << "n";
}
int main() { // main function or driver function
int arr[] = {-2, 45, 0, 11, -9};
int size = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, size);
cout << "Sorted array :n";
display(arr, size);
}
Output of the program:
Sorted array :
-9 -2 0 11 45
Modified Bubble Sort in Python
def bubbleSort(arr):
for i in range(len(arr)):
flag = True
for j in range(0, len(arr) - i - 1):
if arr[j] > arr[j + 1]:
(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
flag = False
if flag:
break
arr = [-2, 45, 0, 11, -9]
bubbleSort(arr)
print('Sorted array:')
print(arr)
Output of the program:
Sorted array:
[-9, -2, 0, 11, 45]Bubble Sort Example
Example1:
If the input array is sorted, return 1 else return 0. Assuming sorting here is in ascending order.
- Input:
- 1 2 3 4 5 6
- 90 80 55 70 40 10
- Output
- 1
- 0
Code for implementation
import java.util.* ;
class Main {
static boolean check(int arr[], int n)
{
if (n == 0 || n == 1)
return true;
for (int i = 1; i < n; i++)
if (arr[i - 1] > arr[i])
return false;
return true;
}
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++)
arr[i]=in.nextInt();
if (check(arr, n))
System.out.print("Array is sorted");
else
System.out.print("Array is unsorted");
}
}
Output:
Input:12 45 78 90 45 10
Output:Array is unsorted
Difference between Selection, Bubble and Insertion Sort
- In terms of algorithm
- In Bubble sort, adjacent elements are compared and sorted if they are in the wrong order.
- In Selection Sort, we select the smallest element and swap it with the 0th index element in the first iteration. This selection continues for n-1 elements and the single element is already sorted and we will have array sorted by 1 element in every iteration
- In Insertion sort, we create partitions of sorted and unsorted parts. One by one element from the sorted art is taken and sent to the unsorted part for checking and placing it to the right position in sorting using swaps.
- In terms of time and space complexity
- All 3 sort have O(n2) time complexity. But via flag variable we can reduce the time complexity of bubble and insertion to O(n) is the best case.
- Space Complexity is the same for all i.e., O(1)
| Best | Average | Worst | Space | |
| Selection | O(n2) | O(n2) | O(n2) | O(1) |
| Bubble | O(n) | O(n2) | O(n2) | O(1) |
| Insertion | O(n) | O(n2) | O(n2) | O(1) |
- In terms of speed
- Bubble sort is slower than the maximum sort algorithm.
- There are a lot of swaps that might take place in the worst case.
- In terms of in-place
- In-place states that the algorithm is in-place if it does not need extra memory barring some variable creation which counts to constant space.
- Selection, Bubble and Insertion are in-place algorithms and do not require any auxiliary memory.
- In terms of stability
- Stability states that the algorithm is stable if the relative ordering of the same elements in the input and output array remains the same.
- Bubble and Insertion are stable algorithms but the naive selection is not as swapping may cost stability.
| Selection | Bubble | Insertion |
| Select smallest in every iteration do single swap | An adjacent swap of every element with the other element where ordering is incorrect | Take and put the element one by one and put it in the right place in the sorted part. |
| Best case time complexity is O(n2) | Best case time complexity is O(n) | Best case time complexity is O(n) |
| Works better than bubble as no of swaps are significantly low | Worst efficiency as too many swaps are required in comparison to selection and insertion | Works better than bubble as no of swaps are significantly low |
| It is in-place | It is in-place | It is in-place |
| Not stable | Stable | Stable |
This brings us to the end of this article where we learned about bubble sort and its implementation in different languages. Also, we learned how to optimize this algorithm to get better performance. I would highly suggest to take up this free course for data structures and algorithms to improve your coding skills.
