In bubble sort, we're going to loop through the array and compare each index with the index next to it. If the those two numbers are out of order (the lesser index's value is greater than the greater index's value) we swap those two numbers' places in the array. We keep looping over that array until everything is in place and nothing was swapped during the last iteration.
What's the Big O on this? Well, there's an inner loop to check to see if indexes need to be swapped, and an outer loop that's just checking to see if anything was swapped. That would be make it O(n²). Not efficient, but a great learning tool. You'll never use bubble sort for anything serious.
function bubbleSort(array) {
let result = [...array];
for (let i = 0; i < result.length; i++) {
for (let j = 0; j < result.length - 1; j++) {
if (result[j] > result[j + 1]) {
[result[j], result[j + 1]] = [result[j + 1], result[j]];
}
}
}
return result;
}
console.log(bubbleSort([2, 1, 4, 10]));
// Instead of always iterating n times we can easily optimize
// the algorithm to terminate early.
// Complexity: In the worst case this whole inner for loop of n iterations
// will run O(n) times resulting in a time complexity of O(n^2).
// Since we are doing the array swaps in place the space complexity is O(n).
function bubbleSort(array) {
let result = [...array];
while (true) {
let swapped = false;
for (let j = 0; j < result.length - 1; j++) {
if (result[j] > array[j + 1]) {
[result[j], result[j + 1]] = [result[j + 1], result[j]];
swapped = true;
}
}
if (!swapped) break;
}
return result;
}