Sorting is a fundamental concept in computer science and programming that involves arranging data collection in a specific order. The most common order for sorting data is numerical or alphabetical. we can use different sorting algorithms to accomplish this.
Some of the algorithms are selection sort, merge sort, insertion sort, bubble sort, etc.
In this blog, we will focus on the sorting algorithm named bubble sort C++ and look at the different implementation methods as well.
Bubble Sort in C++ is an easy sorting algorithm that repeatedly iterates through the given list of elements, compares each adjacent element every time, and swaps them if they are not in order.
This is a simple gist of how it works. Let us look at an example while explaining how it works stepwise for better understanding.
Working of Bubble Sort Algorithm
Let us take an example of an array that has the following elements - 6, 4, 8, 1, 5
Iteration 1
We iterate through the array.
We first compare the elements on the first and the second index.
Swap the elements if the element on the first index is greater than that on the second index.
Then we move on to the elements on the second and third indexes, compare them, and swap if the element on the second index is greater than the one on the third index.
Repeat this till the last element of the array.
Iteration 2
We repeat the same steps as iteration 1 till our array is sorted.
Notice that at the end of each iteration, the largest element present in the unsorted part of the array is finally placed at the end.
Iteration 3
Repeat the steps in iteration 1 till the last unsorted element.
For each iteration, we do the comparisons only until the last element is unsorted in the array.
The array is sorted when all the elements are placed at the right place
Implementation of Bubble Sort in C++
Now that we have understood how bubble sort works let's look at the various implementations of Bubble sort C++.
C++
C++
#include <iostream> using namespace std;
void bubbleSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { for (int j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) { swap(arr[j], arr[j+1]); } } } }
void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; }
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: "; printArray(arr, n);
bubbleSort(arr, n); cout << "Array sorted using brute force bubble sort: "; printArray(arr, n);
return 0; }
Output
Original array: 64 34 25 12 22 11 90
Array sorted using brute force bubble sort: 11 12 22 25 34 64 90
Explanation
The bubbleSort() function implements the brute force version of the bubble sort algorithm. It takes an array arr and its size n as input and uses two nested loops to iterate over the array and compare adjacent elements.
If two adjacent elements are in the wrong order, they are swapped. This process is repeated until the array is fully sorted.
Time and Space Complexity
The time complexity of the brute force bubble sort is O(N2) because it must compare every pair of elements in the array. The Space complexity id O(1). because we are using only auxiliary variables.
Optimized Bubble Sort in C++
Optimized Bubble Sort in C++ enhances the traditional Bubble Sort algorithm's efficiency by minimizing unnecessary iterations. It includes a flag to track whether any swaps occurred during a pass. If no swaps are made, it concludes that the array is already sorted and terminates early. This optimization reduces the average-case time complexity to O(n) for nearly sorted arrays while maintaining O(n^2) in the worst-case scenario. By avoiding unnecessary comparisons, it significantly improves performance for partially sorted data sets.
Algorithm for Optimized Bubble Sort
Start with an unsorted array of elements.
Set a boolean flag swapped to true initially.
Initialize a loop to iterate over the array, i from 0 to n-1, and continue looping while swapped is true.
Within the loop, set swapped to false.
Initialize another loop to iterate over the array from the first element to the second-to-last element, j from 0 to n-i-1.
Within the inner loop, compare each adjacent pair of elements.
If an element is greater than the next element, swap them and set swapped to true.
After completing a pass through the array, if no swaps were made, the array is sorted, and the loop terminates.
Otherwise, repeat steps 3-8 until the array is sorted.
Print the sorted array.
Implementation of Optimized Bubble Sort in C++
C++
C++
#include <iostream> using namespace std;
void optimizedBubbleSort(int arr[], int n) { bool swapped = true; for (int i = 0; i < n-1 && swapped; i++) { swapped = false; for (int j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) { swap(arr[j], arr[j+1]); swapped = true; } } } }
void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; }
int main() {
int arr[] = {56, 99, -1, 4, 34, 9}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Original array: "; printArray(arr, n);
Original array: 56 99 -1 4 34 9
Array sorted using optimized bubble sort: -1 4 9 34 56 99
Explanation
The optimizedBubbleSort() function implements an optimized version of the bubble sort algorithm. It takes an array arr and its size n as input and also uses two nested loops to iterate over the array and compare adjacent elements.
However, it includes an additional optimization: if no swaps are made during a pass through the array, the algorithm knows that the array is already sorted and can exit early.
Time and Space Complexity
The time complexity of the optimized force bubble sort is O(n) because it must compare every pair of elements in the array. The Space complexity is O(1). because we are using only auxiliary variables.
Time and Space Complexities
Name
Complexity
Best Time Complexity
O(n)
Average Time Complexity
O( n2)
Worst Time Complexity
O(n2)
Space Complexity
O(1)
Characteristics of Bubble Sort
Simple Implementation: Bubble Sort is straightforward to implement, making it easy to understand and code, suitable for educational purposes and small datasets.
Comparison-Based: It relies on pairwise comparisons between adjacent elements to sort the array, comparing and swapping elements until the array is sorted.
Inefficient for Large Datasets: Bubble Sort's time complexity of O(n^2) makes it inefficient for large datasets, as it involves nested loops and multiple passes through the array.
Stable Sorting Algorithm: Bubble Sort preserves the relative order of equal elements, making it a stable sorting algorithm.
Space Complexity: Bubble Sort has a space complexity of O(1), as it sorts the array in place without requiring additional memory.
Adaptive Nature: While generally inefficient, Bubble Sort can be adaptive for nearly sorted arrays, requiring fewer iterations to complete sorting.
Advantages of Bubble Sort in C++
Programmers widely use bubble sort; let us look at its advantages.
The primary advantage of the bubble sort is that it is popular and easy to implement.
In the bubble sort, elements are swapped in place without using additional temporary storage.
The space requirement is at a minimum
Disadvantages of Bubble Sort in C++
Here are some disadvantages of using bubble sort as your sorting algorithm.
The main disadvantage of the bubble sort is that it does not deal well with a list containing a huge number of items.
The bubble sort requires N2 processing steps for every N number of elements to be sorted.
The bubble sort algorithm is unsuitable for real-life applications, only academic purposes.
A Bubble sort are used for typical small datasets and educational . It is frequently used for small or nearly sorted datasets, is easy to apply, and aids in the teaching of sorting ideas. However, in practical applications, it is incredibly inefficient for larger datasets.
What are the five steps of the bubble sort algorithm?
The Bubble Sort method compares nearby entries in an array, swaps them if they are out of order, and then repeats this procedure for every pair of elements from the start to the end of the array. This keeps happening until no further swaps are required.
Why is it called bubble sort?
Bubble Sort is named so because during each iteration, smaller or larger elements "bubble" to their correct positions, similar to bubbles rising to the surface in water. This sorting algorithm repeatedly compares adjacent elements and swaps them if they are in the wrong order, gradually moving larger elements towards the end of the array.
Is bubble sort a stable algorithm?
Yes, the bubble sort algorithm is stable. A stable sorting algorithm means that two elements with equal keys are in the same order in the sorted array as in the unsorted input array.
How many loops do we need for a bubble sort algorithm?
To sort an array containing n elements, the bubble sort algorithm generally requires n-1 iterations of a loop to sort the array. In each iteration, the algorithm compares the adjacent elements and swaps them in case of wrong order.
Conclusion
In conclusion, we learned what Bubble Sort in C++ is and how it works. We looked at the two ways we can implement it - the Brute force and Optimized methods. We saw the time and space complexity as well.
80+ registered 