The Bubble Sort algorithm is one of the simplest and most well-known algorithms for sorting a list of elements. It works by comparing adjacent elements and, if they are in the wrong order, swapping them. This process is repeated until the entire list is completely sorted.
Adjacent means that the elements are next to each other. For example, in the list [5, 3, 8, 4], the elements 5 and 3 are adjacent, as are 3 and 8, and so on. The dictionary defines adjacent as "next to something else."
This was the first algorithm I learned in college, and although it is not the most efficient, it is still an excellent starting point for understanding the basic concepts behind sorting algorithms. I remember having to write it out step by step on paper.
The main idea is to swap elements whenever they are in the wrong order. We start with the first element and compare it with the next one. If the first is greater than the second, we swap them. We then move on to the next pair of elements and repeat the process until we reach the end of the list.
Let's look at a step-by-step example using the list [5, 3, 8, 4]:
- The first comparison is between 5 and 3. Since 5 is greater than 3, we swap them. The list is now
[3, 5, 8, 4]. - The next comparison is between 5 and 8. Since 5 is less than 8, we do nothing. The list remains
[3, 5, 8, 4]. - The next comparison is between 8 and 4. Since 8 is greater than 4, we swap them. The list is now
[3, 5, 4, 8].
As you can see, after the first pass, the largest element (8) has "bubbled" up to its correct position. However, the list is still not completely sorted, so we need to make another pass.
- On the second pass, we start again from the beginning. We compare 3 and 5, but do nothing.
- Next, we compare 5 and 4. Since 5 is greater than 4, we swap them. The list is now
[3, 4, 5, 8]. - The next comparison is between 5 and 8. Since 5 is less than 8, we do nothing. The list remains
[3, 4, 5, 8].
Even though the list is already sorted, the algorithm still performs one more pass to verify that no elements are left out of order.
- On the third pass, we start again from the beginning. We compare 3 and 4, but do nothing.
- Next, we compare 4 and 5, and again, we do nothing.
- Finally, we compare 5 and 8, and once again, we do nothing.
The final result is the sorted list [3, 4, 5, 8].
Let's see how this algorithm is implemented in JavaScript:
function bubbleSort(arr) {
let n = arr.length;
let swapped;
do {
swapped = false;
for (let i = 0; i < n; i++) {
if (arr[i] > arr[i + 1]) {
let temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
} while (swapped);
return arr;
}
To see how it works, we can test it with the following example:
const array = [5, 3, 8, 4];
const sortedArray = bubbleSort(array);
console.log(sortedArray); // Output: [3, 4, 5, 8]
The do...while block ensures that the comparison and swapping process is repeated until no more swaps are needed, indicating that the list is completely sorted.
Meanwhile, the for loop traverses the list during each iteration of the do...while loop, comparing each pair of adjacent elements and performing any necessary swaps.
In this example, the list is traversed multiple times until all the elements are in the correct order. The swapped variable keeps track of whether any swaps were made during a pass. If no swaps occur, it means the list is already sorted, and the algorithm can stop.
The drawback of this algorithm is that, on every pass, it has to traverse the entire array to verify that no elements remain out of order. Imagine what happens if, instead of an array with four elements, we have one with 1000. Try it yourself: start with an array of five or ten elements, then increase its size to 1000. You'll see that the execution time grows considerably.
According to Big O notation, this algorithm has a time complexity of O(n²), which means its execution time grows quadratically as the number of elements increases.
In fact, this is a very common interview question in technical programming interviews.