Bubble Sort program, Algorithm & their time complexity.In this tutorial, We are going to learn about bubble sort algorithm and their implementation in various programming languages.
In this tutorial, we are going to cover following things
- What is Bubble Sort?
- Bubble sort algorithm & it’s time complexity
- Bubble sort program in C & C++
- Bubble sort implementation in PHP
What is Bubble Sort?
Bubble sort is a sorting algorithm, It works by comparing each pair of adjacent elements and switching their positions if necessary. It repeats this process until all the elements are sorted.
The average and worst-case time complexity of bubble sort is – O(n2)
Bubble Sort Algorithm
Bubble Sort Algorithm
1. Compare two adjacent elements.
2. Swap the position of adjacent elements if it’s in wrong order.
C program to swap two number without using third variable
C program to swap two numbers using third variable
3. Repeat the above process until all the elements are sorted.
To understand the algorithm, let’s take an example of an unsorted array. This array needs to be sorted in ascending order.
|
1 2 |
//Array int arr[] = {1, 5, 3, 2} |
STEP 1 – In the first step, 1 is compared with 5. Since 1 is smaller than 5 so the position remains unaffected. Now 5 is compared with 3. 3 is smaller than 5, so the position is swapped. Similarly, 5 is compared with 2. 2 is smaller than 5, so the position is swapped.
|
1 2 |
//After first iteration, Array is arr[] = {1, 3, 2, 5} |
STEP 2 – In the second step, 1 is compared with 3. 1 is smaller than 3 so the position remains unaffected. Now 3 is compared with 2. 2 is smaller than 3, so the position is swapped.
|
1 2 |
//After second iteration, Array is arr[] = {1, 2, 3, 5} |
STEP 3 – In the third step, All the elements of an array is already sorted, so nothing gets changed in this step.
|
1 2 |
//Final output - arr[] = {1, 2, 3, 5} |
Bubble Sort Program in C
We have understood how bubble sort works. Let’s write a bubble sort program in C. In this program, We take an input array from a user (unsorted array) and then sort this array.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <stdio.h> int main(void) { int n, i, temp; printf ("Enter number of elements of an array\n"); scanf ("%d", &n); int arr[n]; printf("Enter %d values in an array", n); //Input for(i = 0; i < n; i++) { scanf("%d", &arr[i]); } // Sorting algorithm for(i = 0; i < n-1; i++) { for(int j = 0; j < n-i-1; j++) { if(arr[j] > arr[j+1]) { temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } } printf("After sorting an array \n"); for(i = 0; i < n; i++) { printf("%d\n", arr[i]); } return 0; } |
C++ Program to Implement Bubble Sort
We have written a C code. In this example, we are going to write a C++ code to implement this sorting algorithm.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <iostream> using namespace std; int main() { int n, i, temp; cout << "Enter number of elements of an array"; cin >> n; int arr[n]; cout << "Enter " << n <<" values in an array"; //Input for(i = 0; i < n; i++) { cin >> arr[i]; } // Sorting algorithm for(i = 0; i < n-1; i++) { for(int j = 0; j < n-i-1; j++) { if(arr[j] > arr[j+1]) { temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } } cout << "After sorting an array \n"; for(i = 0; i < n; i++) { cout << arr[i] << "\n"; } return 0; } |
Bubble Sort Program in PHP
Let’s write a PHP code to implement bubble sort algorithm.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
<?php // algorithm implementation function bubbleSort(array $arr) { $len = count($arr); for($i = 0; $i < $len-1; $i++) { for($j = 0; $j < $len-$i-1; $j++) { if($arr[$j] > $arr[$j+1]) { $temp = $arr[$j+1]; $arr[$j+1] = $arr[$j]; $arr[$j] = $temp; } } } echo "After Sorting \n"; for($i = 0; $i < $len; $i++) { echo $arr[$i]."\n"; } } //Unsorted array $arr = array(9, 2, 4, 8, 1); //Sort using bubble sort bubbleSort($arr); |
Conclusion
Bubble sort algorithm is very easy to implement but it’s not efficient for large data sets.
