Bubble sort is a simple sorting algorithm that "bubbles up" the biggest values to the array’s right side. It’s also called sinking sort because of the most significant values "sink" to the array’s right side. This algorithm is adaptive, which means that if the array is already sorted, it will take only O(n) to "sort". However, if the array is entirely out of order, it will require O(n2) to sort.
link:../../../src/algorithms/sorting/bubble-sort.js[role=include]-
Convert any iterable (array, sets, etc.) into an array or if it’s already an array, it clones it, so the input is not modified.
-
Starting from index 0 compare current and next element
-
If they are out of order, swap the pair
-
Repeat pair comparison until the last element that has been bubbled up to the right side
array.length - i. -
(optimization) If there were no swaps, this means that the array is sorted. This single-pass makes this sorting adaptive, and it will only require O(n) operations.
-
Each step moves the largest element from where it was to the right side. We need to do this
n - 1times to cover all items.
swap function is implemented as follows:link:../../../src/algorithms/sorting/sorting-common.js[role=include]It uses JavaScript ES6 destructing arrays.
Assignment separate from declaration
A variable can be assigned to its values using the destructing syntax.
let a, b;
[a, b] = [1, 2];
console.log(a); //↪️ 1
console.log(b); //️↪️ 2Swapping variables
Two variables' values can be swapped in one line using the destructuring expression.
[a, b] = [b, a];
console.log(a); //↪️ 2
console.log(b); //️↪️ 1Without the destructuring assignment, swapping two values requires a temporary variable.
Bubble sort has a part01-algorithms-analysis.asc running time, as you might infer from the nested for-loop.
-
[Stable]: ✅ Yes
-
[In-place]: ✅ Yes
-
[Online]: ✅ Yes
-
[Adaptive]: ✅ Yes, O(n) when already sorted
-
Time Complexity: ⛔️ part01-algorithms-analysis.asc O(n2)
-
Space Complexity: ✅ part01-algorithms-analysis.asc O(1)