Bubble sort is a simple sorting algorithm that orders a list. It repetedly compares neighbouring elements and swaps them if they are in the wrong order. This cause the largest element to move to the end of the list, almost like a "bubble". However, bubble sort is very inefficient on larger lists compared to other alogorithms.
Here is the code for Bubble sort in JavaScript:
let n = array.length
for (let i = 0; i < n - 1; i ++) {
let swapped = False
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
swapped = true
}
}
if (swapped === false) {
break
}
}
For example, if we had the list [4, 3, 1, 5, 2]
The first thing is the 4 and 3 would swap because 4 > 3
[3, 4, 1, 5, 2]
Then the 4 and the 1 because 4 > 1
[3, 1, 4, 5, 2]
but not the 4 and 5 because 4 < 5
[3, 1, 4, 5, 2]
and then the 5 and 2 would swap because 5 > 2
[3, 1, 4, 2, 5]
This is one pass, and this idea would repeat until the list is ordered
[1, 3, 4, 2, 5]
[1, 3, 4, 2, 5]
[1, 3, 2, 4, 5]
[1, 3, 2, 4, 5]
[1, 3, 2, 4, 5]
[1, 2, 3, 4, 5]
| Case | Time complexity | Info |
|---|---|---|
| Best Case | O(n) | The list is already sorted so only one pass is needed |
| Average Case | O(n^2) | Many comparisons and swaps may be needed |
| Worst Case | O(n^2) | The list is ordered backwards |
*n is the number of elements in the list
What are the advantages of Bubble Sort?
- It's simple to understand
- Does not require large amounts of memory
- Can detect if a list is already sorted
What are the disadvantages of Bubble Sort?
- It's inefficient for large datasets
- Usually slower than other algorithms such as merge sort
- Can require many swaps and passes