Bubble Sort is a simple and elementary sorting algorithm used for sorting arrays. At a high level, Bubble Sort works by comparing adjacent elements in an array and swapping them if they are in the wrong order. This process is repeated for each pair of adjacent elements in the array until the entire array is sorted. Despite its inefficiency, Bubble Sort is often used for educational purposes to introduce fundamental concepts of sorting algorithms.
Imagine you have a list of numbers that you wanted to sort in ascending order. You could sort it by starting at the beginning of the list and comparing each set of adjacent elements. If the elements are in the wrong order, you swap them. You continue this process until you reach the end of the list. At this point you know that at least one element, the last element in the list, is in its correct position. Furthermore, some other elements may have 'bubbled' up to their correct positions as well. You can start back at the beginning of the list and repeat this process until the entire list is sorted.
Bubble Sort uses nested loops, so in this example each pass will represent a single iteration through the outer loop, and each step listed in the pass will represent comparisons made in the inner loop. Let's walk through an example of how the algorithm would work if we were to use it on the following array: [7, 2, 9, 1, 5]
Pass 1:
Array state:
We have made a few swaps in the first pass, and our array now looks like this: [2, 7, 1, 5, 9]
Notice how by swapping adjacent elements we've successfully 'bubbled' the largest number up to its proper place in the array. Let's repeat the process.
Pass 2:
Array state:
Again we have some swaps, and our array looks like this now: [2, 1, 5, 7, 9]
Now there are three numbers sorted into their correct spots. We're making good progress, let's keep going!
Pass 3:
Array state:
After this pass here's what our array looks like: [1, 2, 5, 7, 9]
We've successfully sorted the array! However, since we made a swap on this pass we will still have to repeat the process.
Pass 4:
Array state:
Finally, since we made no swaps on this pass, we can assume that our array is sorted. Great job!
Now that we have a pretty good idea of how it works, lets think about how we would execute it in code. Here is what our pseudocode might look like...
Now that we have our plan written, let's write some code!
function bubbleSort(arr) {
// Set a variable so we don't have to call .length on each iteration
const n = arr.length;
// Create a flag to track whether any swaps occur in the inner loop
let swapped;
// Begin outter loop
do {
// Set swapped to false at the beginning of each pass
swapped = false;
// Begin inner loop
for (let i = 1; i < n; i++) {
// Swap elements if they are in the wrong order
if (arr[i - 1] > arr[i]) {
[arr[i - 1], arr[i]] = [arr[i], arr[i - 1]];
// Set swapped to true if a swap occurs
swapped = true;
}
}
// Loop through the array until no swaps occur
} while (swapped);
return arr;
}
The time complexity of Bubble Sort is O(n^2) in the worst and average cases. This is because, in each pass, it compares and swaps adjacent elements, resulting in a nested loop structure. The space complexity of Bubble Sort is O(1), indicating that the algorithm uses a constant amount of extra space. This is because Bubble Sort only requires a constant amount of additional memory for variables like swapped and i.
In conclusion, while Bubble Sort is a simple algorithm, it's not the most efficient for large datasets. Understanding its inner workings can provide valuable insights into the basics of sorting algorithms.
Check it out in the