Bubble Sort is a fundamental sorting algorithm that is easy to understand and implement. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This article will provide an in-depth look at Bubble Sort in C++, presenting multiple examples with different solutions and their respective outputs.
Prerequisites
To effectively follow this article, you should have:
- Basic understanding of the C++ programming language.
- Familiarity with arrays and loops in C++.
Introduction
In this article, we will discuss the implementation of Bubble Sort in C++. Bubble Sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. This process is repeated until the list is sorted. We will cover different methods to implement Bubble Sort, providing detailed explanations and example outputs.
1. Basic Bubble Sort Implementation
1.1 Explanation
The basic Bubble Sort algorithm involves iterating through the list multiple times and swapping adjacent elements if they are in the wrong order. This process continues until no more swaps are needed, indicating that the list is sorted.
1.2 Code Implementation
#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] and arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
1.3 Output
Sorted array:
11 12 22 25 34 64 90
2. Optimized Bubble Sort with Early Termination
2.1 Explanation
The optimized Bubble Sort algorithm improves the basic version by adding a flag that checks if any swaps were made during a pass. If no swaps are made, the list is already sorted, and the algorithm can terminate early.
2.2 Code Implementation
#include <iostream>
using namespace std;
void optimizedBubbleSort(int arr[], int n) {
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped)
break;
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {64, 25, 12, 22, 11, 34, 90};
int n = sizeof(arr) / sizeof(arr[0]);
optimizedBubbleSort(arr, n);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
2.3 Output
Sorted array:
11 12 22 25 34 64 90
3. Bubble Sort Using Vectors
3.1 Explanation
In this method, we use vectors from the C++ Standard Library to implement Bubble Sort. This approach provides the advantage of dynamic sizing and other functionalities offered by vectors.
3.2 Code Implementation
#include <iostream>
#include <vector>
using namespace std;
void bubbleSort(vector<int>& arr) {
int n = arr.size();
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] and arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void printArray(vector<int>& arr) {
for (int i = 0; i < arr.size(); i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
cout << "Sorted array: \n";
printArray(arr);
return 0;
}
3.3 Output
Sorted array:
11 12 22 25 34 64 90
Conclusion
In this article, we explored different methods to implement Bubble Sort in C++. We started with the basic Bubble Sort algorithm, then moved on to an optimized version with early termination, and finally demonstrated a dynamic approach using vectors. Each method provides unique advantages, from understanding the basic sorting mechanism to efficiently handling larger datasets with dynamic sizing. Understanding these techniques will enhance your ability to implement sorting algorithms and optimize your code for better performance. Bubble Sort, while simple, is a great starting point for learning about more complex sorting algorithms and their applications.