Bubble sort is a simple and well-known sorting algorithm. It is a comparison-based algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list as the sort progresses.
The basic idea behind bubble sort is that it repeatedly compares adjacent elements of an array and swaps them if they are in the wrong order. The bubble sort algorithm is considered to be the simplest sorting algorithm, but it is also one of the least efficient. The worst-case time complexity of bubble sort is O(n^2) for an array of size n. However, it can be optimized to O(n) in the best-case scenario.
Bubble sort can be implemented in C++ using the following steps:
First, we need to define the array that we want to sort.
Next, we initialize two variables, i and j, to iterate through the array.
We then use a nested loop to iterate through the array and compare each pair of adjacent elements.
If the current element is greater than the next element, we swap them.
We continue this process until the array is sorted.
Here is an example of bubble sort implemented in C++:
#include <iostream>
using namespace std;
void bubbleSort(int array[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
int main() {
int array[] = {5, 2, 9, 1, 5, 6};
int size = sizeof(array) / sizeof(array[0]);
bubbleSort(array, size);
cout << "Sorted array: \n";
for (int i = 0; i < size; i++)
cout << array[i] << " ";
return 0;
}
In this example, we first define the array that we want to sort. We then pass this array and its size to the function "bubbleSort". Inside the function, we use two nested loops to iterate through the array and compare each pair of adjacent elements. If the current element is greater than the next element, we swap them. We continue this process until the array is sorted. Finally, we print out the sorted array to the console.
Bubble sort has some performance optimization that can be used to make the algorithm more efficient. One of the most common optimizations is called the "short bubble", which is a modified version of the basic bubble sort algorithm. The short bubble sort keeps track of the last swap made during each pass through the array, and only checks elements up to that point on the next pass. This reduces the number of comparisons needed and can make a significant difference in the performance of the algorithm.
Another optimization is the "cocktail sort", which is a variation of the bubble sort algorithm that sorts in both directions.
