Bubble Sort
Bubble Sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. It is an elementary sorting algorithm that is not suitable for large datasets due to its high time complexity. The algorithm is named "Bubble Sort" because the smaller elements "bubble" to the beginning of the list, while the larger elements "sink" to the end.
Algorithm
The Bubble Sort algorithm works as follows:
Start at the beginning of the list. Compare each pair of adjacent elements in the list. If the elements are in the wrong order (i.e., the first element is greater than the second element), swap them. Continue this process until the end of the list is reached. If any elements were swapped during the pass, repeat steps 1-4. If no elements were swapped during a pass, the list is sorted, and the algorithm terminates.
Pseudocode
Here is a simple pseudocode for Bubble Sort:
function bubbleSort(arr)
do
swapped = false
for i = 1 to length(arr) - 1
if arr[i-1] > arr[i]
swap(arr[i-1], arr[i])
swapped = true
end if
end for
while swapped
end function
Time Complexity
The time complexity of Bubble Sort is O(n^2) in the worst and average cases, where n is the number of elements in the list. In the best case (when the list is already sorted), the time complexity is O(n) since the algorithm can be easily modified to terminate early if no swaps were performed during a pass.
Space Complexity
The space complexity of Bubble Sort is O(1) because it is an in-place sorting algorithm, meaning it does not require additional memory for temporary storage.
C++ Example
Here is an example implementation of Bubble Sort in C++:
#include <iostream>
#include <vector>
void bubbleSort(std::vector < int > & arr) {
bool swapped;
do {
swapped = false;
for (size_t i = 1; i < arr.size(); ++i) {
if (arr[i - 1] > arr[i]) {
std::swap(arr[i - 1], arr[i]);
swapped = true;
}
}
} while (swapped);
}
int main() {
std::vector < int > arr = {
64,
34,
25,
12,
22,
11,
90
};
bubbleSort(arr);
std::cout << "Sorted array is: ";
for (int i: arr) {
std::cout << i << " ";
}
return 0;
}