Bubble Sort in C++
In this article, you will learn about the bubble sort in C++. But before discussing the bubble sort, you must know about the Sorting.
Sorting:
In computer science, sorting is a fundamental operation used to arrange a group of objects in a specific order. You may construct a variety of sorting algorithms in C, each of which has benefits and drawbacks in terms of time and space complexity.
- A sorting algorithm is used to reorder an array or list of elements based on a comparison operator applied to the elements.
- The comparison operator is used to identify the new elemental order in the appropriate data structure.
Types of Sorting Algorithms:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Quick Sort
- Merge Sort
- Counting Sort
- Heap Sort
Bubble Sort:
- A simple sorting method called bubble sort iteratively goes through the list to be sorted, compares nearby components, and swaps them if they are out of order. Repeat this manner till the whole listing is sorted.
- Bubble Sort is an algorithm that iteratively traverses the list, compares nearby members, and swaps out any that are out of order.
- Until no swaps are required, the trip through the list is repeated, signifying that the list is sorted.
- Bubble Sort has an O(n^2) time complexity, where n is the array's element count.
Think about the following array of numbers that you wish to use Bubble Sort to sort in descending order:
Array: [6, 1, 8, 2, 4]
Step 1:
- A comparison is made between the first two elements, 6 and 1. 1 <6, therefore we swap them.
- The array is swapped: [6, 1, 8, 2, 4].
Step 2:
- Evaluate elements 2 and 3, which correspond to 6 and 8. There's no reason to switch.
- There are still [6, 1, 8, 2, 4] in the array.
Step 3:
- Evaluate elements 8 and 2 in the groupings that are third and fourth. 8 > 2, thus we flip them.
- The array is swapped: [6, 1, 8, 2, 4].
Step 4:
- Comparing elements 8 and 4, the fourth and fifth, is the fourth step. 4 < 8, therefore we swap them out.
- Inverted array: [8, 4, 2, 1, 6]
- After being placed at the end of the array at first, the largest element (8), has now "bubbled up" to take its place.
- We now repeat the process, beginning at the beginning of the array:
Step 5:
- A comparison is made between the first two elements, 6 and 1. 6 > 1, therefore we swap them.
- Array swapped: [6, 1, 2, 4, 8]
Step 6:
- Comparing elements 2 and 3, which are 6 and 2, is the sixth step. 6 > 2, therefore we swap them.
- Array swapped: [6, 2, 1,4,8]
Step 7:
- Comparing elements 1 and 4 in the third and fourth positions is step seven. There's no need for a switch because 1 and 4.
- There are still [6, 2, 1, 4, 8] in the array.
Step 8:
- Compare the fourth and fifth elements, 4 and 8. There is no need for a switch because 4<8.
- There are still [6, 2, 1, 4, 8] in the array.
- After the second run through the array, the second-largest member (element 6) has "bubbled up" to the second-to-last position.
- We continue this way for the remaining passes until no more swaps are needed. In every pass, the largest unsorted element "bubbles up" to the correct position.
Step 9:
- No swaps are needed because the array is already sorted.
After sorting in descending order, the final array is [8, 6, 4, 2, 1].
Program:
#include <iostream>
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
void bubbleSortDescending(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] < arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
int size;
std::cout << "Enter size of an array: ";
std::cin >> size;
int arr[size];
std::cout << "Enter the elements of the array:" << std::endl;
for (int i = 0; i < size; i++) {
std::cin >> arr[i];
}
bubbleSortDescending(arr, size);
std::cout << "Array sorted in descending order:" << std::endl;
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
Output:
![Bubble Sort in C++](https://static.tutorialandexample.com/cpp/bubble-sort-in-cpp1.png)
Think about the following array of numbers that we wish to use Bubble Sort to sort in ascending order:
Array: [7, 2, 9, 1, 5]
Step 1:
- Compare the first two elements, 7 and 2. Since 2 is less than 7, we swap them.
- Swapped array: [2, 7, 9, 1, 5]
Step 2:
- Compare elements 7 and 9. No swap is needed as they are already in the correct order.
- Array remains: [2, 7, 9, 1, 5]
Step 3:
- Compare elements 9 and 1. Since 9 is greater than 1, we swap them.
- Swapped array: [2, 7, 1, 9, 5]
Step 4:
- Compare elements 9 and 5. Since 9 is greater than 5, we swap them.
- Swapped array: [2, 7, 1, 5, 9]
- The largest element (9) has now "bubbled up" to the last position.
- Now, we start over from the beginning of the array:
Step 5:
- Compare the first two elements, 2 and 7. No swap is needed.
- Array remains: [2, 7, 1, 5, 9]
Step 6:
- Compare elements 7 and 1. Since 7 is greater than 1, we swap them.
- Swapped array: [2, 1, 7, 5, 9]
Step 7:
- Compare elements 7 and 5. Since 7 is greater than 5, we swap them.
- Swapped array: [2, 1, 5, 7, 9]
Step 8:
- Compare elements 7 and 9. No swap is needed.
- Array remains: [2, 1, 5, 7, 9]
- The second-largest element (7) has "bubbled up" to the second-to-last position.
Step 9:
- The array is already sorted; no swaps are required.
- The sorting process is complete.
The final sorted array in ascending order is [1, 2, 5, 7, 9].
Program:
#include <iostream>
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
void bubbleSortAscending(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) { // Change to ">" for ascending order
swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
int size;
std::cout << "Enter size of an array: ";
std::cin >> size;
int arr[size];
std::cout << "Enter the elements of the array:" << std::endl;
for (int i = 0; i < size; i++) {
std::cin >> arr[i];
}
bubbleSortAscending(arr, size);
std::cout << "Array sorted in ascending order:" << std::endl;
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;}
Output:
![Bubble Sort in C++](https://static.tutorialandexample.com/cpp/bubble-sort-in-cpp2.png)
Although bubble sort is simple to comprehend and use, it is not very effective for handling huge datasets since, in the worst scenario, it has an O(n2) time complexity. Large or complex datasets are rarely sorted using it in practice; it is largely utilized for educational purposes.