Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
The pass through the list is repeated until the list is sorted.
It is called Bubble Sort because smaller elements "bubble" to the top of the list with each pass.
function bubbleSort(arr) {
var n = arr.length;
var swapped;
do {
swapped = false;
for (var i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
// Swap arr[i] and arr[i + 1]
var temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
} while (swapped);
return arr;
}
var array = [64, 34, 25, 12, 22, 11, 90];
console.log("Original array: " + array);
console.log("Sorted array: " + bubbleSort(array));
Time Complexity:
Worst Case: O(n^2)
The worst case scenario occurs when the input array is sorted in reverse order. In this case, Bubble Sort performs n passes through the array, and in each pass, it makes a swap for each pair of adjacent elements. This results in a time complexity of O(n^2).
Space Complexity:
Bubble Sort is an in-place sorting algorithm, meaning it does not require additional space proportional to the input size.
It sorts the elements within the given array itself, so the space complexity is O(1), indicating constant space usage regardless of the input size.
Refereneces:
https://s-satsangi.medium.com/insertion-sort-selection-sort-and-bubble-sort-5eb16d55a4de