Bubble Sort
Bubble Sort is a naive sorting implementation.
We might thing that to sort an array, we could just run through it element by element and, when a subsequent element is less than the previous element, flip the two values.
Set a flag for swapped. Each time we flip two values, set the flag to true. After we iterate through the array, if the flag is true, we recursively call the function again & set the value to false.
When we are able to run through the entire array without flipping, we return the sorted array.
This is not an efficient algorithm. Also, Obama said not to use it.
Consider the worst-case scenario of a completely unsorted array:
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1].
It will take 10 loops to sort the array.
function bubbleSort(arr, ct) {
if (!ct) {
ct = 0;
}
let swapped = false;
const swapIndices = (a, b) => {
let temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
};
for (var i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) {
swapped = true;
swapIndices(i - 1, i);
}
}
ct++;
if (ct === arr.length + 10) {
return arr;
}
return swapped ? bubbleSort(arr, ct) : { sortedArr: arr, count: ct };
}