Bubble Sort is based on the idea of repeatedly comparing pairs of adjacent elements and then swapping their positions if they are in the wrong order. Bubble sort is a stable, in-place sort algorithm.
How it works:
- In an unsorted array of
n
elements, start with the first two elements and sort them in ascending order. (Compare the element to check which one is greater). - Compare the second and third element to check which one is greater, and sort them in ascending order.
- Compare the third and fourth element to check which one is greater, and sort them in ascending order.
- …
- Repeat steps 1–
n
until no more swaps are required.
Visualisation:
Complexity Analysis
Bubble sort has a worst-case and average complexity of O(n2)
, where n
is the number of items being sorted. When the list is already sorted (best-case), the complexity of bubble sort is only O(n)
. The space complexity for Bubble Sort is O(1)
, because only single additional memory space is required (for temp
swap element).
Implementation
// Normal
const bubbleSort = function(array) {
let swaps;
do {
swaps = false;
for (let i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1]) {
let temp = array[i + 1];
array[i + 1] = array[i];
array[i] = temp;
swaps = true;
}
}
} while (swaps);
return array;
};
// Recursively
const bubbleSort = function (array, pointer = array.length - 1) {
// Base Case
if (pointer === 0) {
return array;
}
for (let i = 0; i < pointer; i++) {
if (array[i] > array[i + 1]) {
let temp = array[i + 1];
array[i + 1] = array[i];
array[i] = temp;
}
}
// Recursive call on smaller portion of the array
return bubbleSort(array, pointer - 1);
};