Last Updated on 2022-07-19 by Clay
Bubble sort is the first sorting method that most people come into contact with, because it is really the most intuitive and best-written sorting method.
The principle of Bubble Sort
It is called bubble sort because suppose that if we want to sort a set of array of length N from small to large, we are sequentially comparing each value between 0 and N-1, as long as the value of the current alignment if it's larger than the next value, we'll swap them.
Keep doing, and the small values will gradually float to the beginning of the array like bubbles in water.
Suppose we have the following array:
4 5 3 1 2 7 6
First we compare 4 and 5. The value 4 is smaller than 5, so we do not swap them.
Then we compare 5 and 3, The Value 5 is larger than 3, so we swap them. Now the array is looks like:
4 3 5 1 2 7 6
We'll keep repeating this process until the first round is out of order.
4 3 1 2 5 6 7
Of course, it is usually impossible to sort the entire array with only one round, and we can only guarantee that the largest value will be pushed to the end of the array.
That is to say, the purpose of our next round of sorting will be to push the "second largest value" to the second position form the bottom of the array... and so on until the array is sorted.
Below is a sample code that I will also print it out.
Bubble Sort Sample Code
Complexity
It is a relatively stable complexity method, and the additional space required is only O(1), but it may not be suitable to use the sorting method with such a high time complexity in a longer array.
| Time Complexity | O(n^2) |
| Space Complexity | O(1) |
C++ Sample Code
#include <iostream>
#include <vector>
using namespace std;
void swap(int* n1, int* n2) {
int temp = *n1;
*n1 = *n2;
*n2 = temp;
}
void printArr(int arr[], int size) {
for (int i=0; i<size; ++i) {
cout << arr[i] << " ";
}
cout << endl;
}
void bubbleSort(int arr[], int size) {
// Sort
for (int i=0; i<size-1; ++i) {
// Check is swaped in this loop
bool isSwaped = false;
for (int j=0; j<size-i-1; ++j) {
if (arr[j] > arr[j+1]) {
swap(&arr[j], &arr[j+1]);
isSwaped = true;
}
}
// Print progress
cout << i+1 << ": ";
printArr(arr, size);
if (!isSwaped) break;
}
}
int main() {
int arr[] = {4, 5, 3, 1, 2, 7, 6};
int size = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, size);
return 0;
}
Output:
1: 4 3 1 2 5 6 7
2: 3 1 2 4 5 6 7
3: 1 2 3 4 5 6 7
4: 1 2 3 4 5 6 7 Python Sample Code
# coding: utf-8
def bubbleSort(arr, size):
for i in range(size-1):
# Check the swap exist or not
isSwaped = False
for j in range(size-i-1):
if (arr[j] > arr[j+1]):
arr[j], arr[j+1] = arr[j+1], arr[j]
isSwaped = True
# Print progress
print("{}: {}".format(i+1, arr))
if not isSwaped:
break
def main():
# Init
arr = [4, 5, 3, 1, 2, 7, 6]
size = len(arr)
# Sort
bubbleSort(arr, size)
if __name__ == "__main__":
main()
Output:
1: [4, 3, 1, 2, 5, 6, 7]
2: [3, 1, 2, 4, 5, 6, 7]
3: [1, 2, 3, 4, 5, 6, 7]
4: [1, 2, 3, 4, 5, 6, 7]This is really one of the most intuitive sorting methods.
References
- https://www.geeksforgeeks.org/bubble-sort/
- https://en.wikipedia.org/wiki/Bubble_sort
- https://www.programiz.com/dsa/bubble-sort