bubble-sort.asc

Bubble Sort

Bubble sort is a simple sorting algorithm that "bubbles up" the biggest values to the right side of the array. It’s also called sinking sort because the most significant values "sink" to the right side of the array. 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(n²) to sort.

Bubble Sort Implementation

Bubble Sort implementation in JavaScript

link:../../../src/algorithms/sorting/bubble-sort.js[role=include]

1. 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.

2. Starting from index 0 compare current and next element

3. If they are out of order, swap the pair

4. Repeat pair comparison until the last element that has been bubbled up to the right side array.length - i.

5. (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.

6. Each step moves the largest element from where it was to the right side. So, we need to do this n - 1 times to sort the array in case most elements need to be swapped.

The swap function is implemented as follows:

link:../../../src/algorithms/sorting/sorting-common.js[role=include]

It uses JavaScript ES6 destructing arrays.

JavaScript Array destructuring

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); //️↪️ 2

Swapping 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); //️↪️ 1

Without 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.

Bubble Sort Properties

• [Stable]: ✅ Yes

• [In-place]: ✅ Yes

• [Online]: ✅ Yes

• [Adaptive]: ✅ Yes, O(n) when already sorted

• Time Complexity: ⛔️ part01-algorithms-analysis.asc O(n²)

• Space Complexity: ✅ part01-algorithms-analysis.asc O(1)