When a large amount of data is to be dealt with, the most efficient way is to store it in an optimized manner, where it is arranged in either ascending or descending format. There are many sorting techniques but in this article, we will study one Bubble Sort Algorithm, and understand how it works, with its implementation in C++.
What is Bubble Sort?
The Bubble Sort, also called Sinking Sort, is a sorting algorithm that compares each pair of adjacent elements. The basic technique of bubble sort is that the first element of the list is compared to the second, the second to the third element, and so on. Each iteration moves each element of the array closer to the end, similar to how air bubbles rise to the surface of the water.
This is how bubble sort gets its name. Here, the sorting is done in the form of passes or iterations. As a result, the largest element is placed in its rightful place in the list at the end of each iteration.
If you are new to programming this might be the first sorting technique you will learn because it is easy to understand, and simple to code. Sorting is one of the most basic concepts that programmers need to learn and Bubble Sort is your entry point in this new world. You can store and optimize a huge amount of data when you will work in the real world.
Algorithm for Bubble Sort
Here is the basic algorithm for Bubble Sort:
Step1: for k = 0 to n-1 repeat Step 2 Step2: for j = k + 1 to n – k repeat Step3: if A[j] > A[k] Swap A[j] and A[k] [end of inner for loop] [end if outer for loop] Step4: end
How Does Bubble Sort Work?
- If the order of adjacent elements is incorrect, we compare them ( a[k] > a[j] ) and swap them.
- Assume we have an array of length 'n'. Therefore, to sort 'n' elements using the previous step, we require an 'n-1' pass.
- After following these steps, the largest element goes to the end of the array. The next largest is one place behind the last. The 'kth' largest element is swapped to its rightful place in the array in the 'kth' pass.
- So basically, at least one element from 'n - k + 1' will appear at its right place at the end of the ith pass. It will be the 'kth' largest element (for 1 *= k *= n - 1) of the array. Because in the 'kth' pass of the array, in the 'jth' iteration (for 1 <= j <= n - k), we are checking if 'a[j] > a[j + 1]', and 'a[j]' will always be greater than 'a[j + 1]' when it is the largest element in range '[1, n - k + 1]'. We'll now swap it. The process will continue until the largest element in the array is at the '(n - k + 1)th' position.
Check the pseudocode below:
begin bubbleSort(array): N <- length(array) for j = 0 to N: for i = 0 to N-1: if array[i] > array[i+1] temp <- array[i] array[i+1] <- array[i] array[i] <- temp end if end for end for return array end bubbleSort begin modifiedbubbleSort(array): N <- length(array) for j = 0 to N: flag = False for i = 0 to N-1: if array[i] > array[i+1] temp <- array[i] array[i+1] <- array[i] array[i] <- temp flag = True end if end for if flag == False: break end for return array end modifiedbubbleSort
Here, we traverse the array using two iterative loops.
We begin with the '0th' element in the first loop, then we begin with an adjacent element in the second loop. We compare each of the neighboring components in the inner loop body and swap them if they are out of order. The heaviest element bubbles up at the end of each iteration of the outer loop.
Bubble Sort Example
Let us consider the below array of elements to sort.
As we can see from the above illustration, the greatest element bubbles up to the last with each pass, sorting the list. Each element is compared to its adjacent element and switched with one another if they are not in order.
If the array is to be sorted in ascending order at the end of the first pass, the largest element is placed at the end of the list. The second largest element is placed at the second last position in the list for the second pass, and so on.
At last, we will have sorted the entire list when n-1 (where n is the total number of entries in the list) passes. The final output of the bubble sort will be as shown below.
C++ Program for Bubble Sort
Here is the C++ Program with complete code to implement Bubble Sort:
#include<bits/stdc++.h> #define swap(x,y) { x = x + y; y = x - y; x = x - y; } using namespace std; /** * Function to Sort the array using Modified Bubble Sort Algorithm * @param arr: Array to be Sorted * @param n: Size of array * @return : None */ void bubbleSort(int arr[], int n) { int i, j; bool flag; // Outer pass for(i = 0; i < n; i++) { flag = false; // Set flag as false for(j = 0; j < n-i-1; j++) { // Compare values if( arr[j] > arr[j+1]) { swap(arr[j],arr[j+1]); flag = true; } } // If no to elements are swapped then // array is sorted. Hence Break the loop. if(!flag) { break; } } } int main(int argv, char* argc[]) { int arr[] = {1,5,6,8,3,4,7,2,9}; int n = sizeof(arr)/sizeof(int); cout<<"Unsorted Array :"; for(int i=0;i<n;i++) // Print the Original Array cout<<arr[i]<<" "; cout<<endl; bubbleSort(arr,n); // Call for Bubble Sort Function cout<<"Sorted Array :"; for(int i=0;i<n;i++) // Print the Sorted Array cout<<arr[i]<<" "; return(0); }
Output:
Unsorted Array :1 5 6 8 3 4 7 2 9 Sorted Array :1 2 3 4 5 6 7 8 9
Time Complexity
Considering the average case and worst-case scenarios, the time complexity of bubble sort is O(n^2) where n is the total number of elements in the array. It is because we have to make use of two loops traversing through the entire array for sorting the elements. In the best case, when the array is completely sorted, the complexity is O(n).
Recursive Implementation of Bubble Sort
A recursive version of Bubble sort is a variant of the Bubble sort algorithm that sorts an array using recursion. In recursive bubble sort, the first n-1 elements of the array are sorted, and then the remaining n-1 elements of the array are sorted recursively. When we reach an array of size one, the recursion ends.
We have given below the example code for recursive implementation:
// Recursive Bubble Sort function void bubbleSortRecursive(int arr[], int n) { // Base case if (n == 1) return; for (int i=0; i<n-1; i++) if (arr[i] > arr[i+1]) swap(arr[i], arr[i+1]); // Recursively sort the remaining n-1 elements bubbleSortRecursive(arr, n-1); }
Is the Bubble Sort algorithm stable?
A sorting algorithm is said to be stable when the relative order of equal elements in the sorted output remains the same as it did in the original input. This means that if two elements in the input array have the same value and appear in a given order, the algorithm will keep that order in the final output.
The bubble sort is a stable sorting algorithm because it guarantees that the relative order of equal components is maintained. Since it swaps neighboring elements only if they are out of order and not if they are equivalent, there is no change in order.
Why is Bubble Sort not efficient?
The main reason why Bubble sort is not considered efficient since it has a time complexity of O(n2), which implies that the time required to sort the input array grows quadratically as the size of the array grows. This makes sorting huge arrays impractical since it becomes progressively sluggish and resource intensive.
Furthermore, it requires several swaps between neighboring items, which can be expensive in terms of memory access, especially when the input data is stored in an external memory such as a hard disc or flash drive.
Conclusion
We studied Bubble Sort in this blog with how it works and the C++ program to implement it. It is not commonly used compared to other sorting algorithms but still has its own importance in the technical world. Learning bubble sort is well worth the effort because it acts as a bridge to understanding higher-level concepts and makes it easier.
