This is fairly straightforward and inefficient way of sorting an array, but it is also a very easy to implement algorithm and is usually used when teaching the basics of sorting to new students. The intuition is also simple: you start by comparing the two last elements with each other. If the last is smaller than the one that precedes it, we swap them, so that the last element is the largest. We keep moving this sliding window of two array elements and swapping according to the same rule until we reach the end of the array. Then, we repeat the same process but starting from the second to last and third to last elements, and so on and so forth. This means that we are left with a procedure with a worst case and average case scenarios of time complexity of $O(n^2)$. Much like insertion sort this algorithm also has the best case scenario of $O(n)$, which only happens if the array is almost sorted.
Pseudocode
We can describe the algorithm in pseudocode (assuming array indexes start in 1) as follows:
1
2
3
4
5
6
| BUBBLE-SORT(A)
for i = 1 to A.length - 1
for j = A.length down to i + 1
if A[j] < A[j-1]
swap A[j] with A[j-1]
|
Note that this implementation does not reflect the algorithms performance on the best case scenario.
Implementation
Python
1
2
3
4
5
6
7
8
9
| def bubble_sort(array):
for i in range(0, len(array) - 1):
for j in range(len(array) -1, i, -1):
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
array = [43, 2, 21, 3, 70, 8]
bubble_sort(array)
print(array)
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| package main
import "fmt"
func bubbleSort(array []int) {
for i := 0; i < len(array)-1; i++ {
for j := len(array) - 1; j > i; j-- {
if array[j] < array[j-1] {
array[j], array[j-1] = array[j-1], array[j]
}
}
}
}
func main() {
array := []int{43, 2, 21, 3, 70, 8}
bubbleSort(array)
fmt.Println(array)
}
|
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| fn bubble_sort(array: &mut [i32]) {
for i in 0..array.len() {
for j in (i+1..array.len()).rev() {
if array[j] < array[j-1] {
(array[j], array[j-1]) = (array[j-1], array[j]);
}
}
}
}
fn main() {
let mut array: [i32; 6] = [43, 2, 21, 3, 70, 8];
bubble_sort(&mut array);
println!("{:?}", array);
}
|
References
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 3rd Edition