- [[selection sort]], [[insertion sort]], [[merge sort]], [[sorting algorithms]]
# Idea
We "bubble up" the largest number to the right/top by swapping elements in the list. This process is also known as **sinking swap** because the largest element sinks to the top.
Bubble sort is a simple algorithm that requires minimal memory. However, it is often outperformed by more advanced [[sorting algorithms]] like [[quick sort]] or [[merge sort]]. Due to its poor performance, bubble sort is typically not used in practice unless the array is already nearly sorted.
Despite its $O(n^2)$ time complexity making it unsuitable for large datasets, bubble sort remains valuable in specific scenarios where its simplicity, stability, and low memory usage are advantageous.
## Algorithm
We make multiple passes through an array, swapping elements if the i-th element is larger than the (i+1)-th element. After the first pass through all the elements, the largest element will have "bubbled" to the end of the array. In the subsequent pass, we loop through all but the final element (since it is already sorted), swapping elements if necessary. This process continues, with each pass sorting one additional element at the end of the array.
The sorted data accumulates at the top of the array, such that large values are sorted first.
### Optimization
If the array is almost sorted already, we can optimize bubble sort by checking if any swaps were made in the previous pass. If not, the array is already sorted and we don't need more passes.
We can also traverse the list in both directions alternately, which helps in cases where small elements are located near the end of the list. It's known as the [[bidirectional bubble sort]].
## Example of one pass
After a single pass, the largest element is moved/bubbled/sinked to the top/right.
![[20240527145026.png]]
## Example of multiple passes (bold: to swap; italics: sorted)
- pass 1
- **5 2** 4 3 1
- 2 **5 4** 3 1
- 2 4 **5 3** 1
- 2 4 3 **5 1**
- 2 4 3 1 *5*
- pass 2
- 2 **4 3** 1 *5*
- 2 3 **4 1** *5*
- 2 3 1 *4 5*
- pass 3
- 2 **3 1** *4 5*
- 2 1 *3 4 5*
- pass 4
- **2 1** *3 4 5*
- *1 2 3 4 5*
```python
def bubble_sort(l):
n = len(l)
while n > 0:
for i in range(n):
if i < n - 1 and l[i] > l[i + 1]:
l[i], l[i + 1] = l[i + 1], l[i]
n -= 1
return l
def bubble_sort2(l):
for max_i in range(len(l) - 1, 0, -1):
for i in range(max_i):
if l[i] > l[i + 1]:
l[i], l[i + 1] = l[i + 1], l[i]
return l
print(bubble_sort([4, 2, 6, 5, 1, 3]))
print(bubble_sort2([4, 2, 6, 5, 1, 3]))
def bubble_sort_optimized(l):
for max_i in range(len(l) - 1, 0, -1):
swap = False
for i in range(max_i):
if l[i] > l[i + 1]:
l[i], l[i + 1] = l[i + 1], l[i]
swap = True
if not swap:
break
print("one pass")
return l
print(bubble_sort_optimized([3, 1, 4, 5, 6]))
# keep track of last swap position
def bubbleSortWithLastSwap(arr):
n = len(arr)
while n > 0:
new_n = 0
for i in range(1, n):
if arr[i-1] > arr[i]:
arr[i-1], arr[i] = arr[i], arr[i-1]
new_n = i
n = new_n
```
```javascript
// UNOPTIMIZED VERSION OF BUBBLE SORT
function bubbleSort(arr){
for(var i = arr.length; i > 0; i--){
for(var j = 0; j < i - 1; j++){
console.log(arr, arr[j], arr[j+1]);
if(arr[j] > arr[j+1]){
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
// ES2015 Version
function bubbleSort(arr) {
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};
for (let i = arr.length; i > 0; i--) {
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
return arr;
}
bubbleSort([8,1,2,3,4,5,6,7]);
```
## Performance
Time complexity
- worst case: $O(n^2)$, when the list is in reverse order
- best case: $O(n)$, when the list is already sorted
- average case: $O(n^2)$, when the elements are in random order
Space complexity
- $O(1)$: it's an in-place sorting algorithm, meaning it requires only a constant mount of additional space
# References
- [Log In and Start Learning | Udemy](https://www.udemy.com/course/data-structures-algorithms-python/learn/lecture/27617268#overview)
- [Bubble Sort visualize | Algorithms | HackerEarth](https://www.hackerearth.com/practice/algorithms/sorting/bubble-sort/visualize/)
- [Log In and Start Learning | Udemy](https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/learn/lecture/11071948#overview)