Bubble sort


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