Last week, we looked at merge sorting, an algorithm used to sort an array of numbers. Today let's look at an important to know, but far less efficient way of sorting numbers, bubble sorts.
Bubble sorts can have a linear time complexity, O(n) if the array is already sorted, but for the most part, the time will be quadratic, or O(n²). This is because bubble sorting works by comparing adjacent elements and sorting from smallest to largest, one at a time. In the image above, we have an example where the first iteration compares 5 to 1 and swaps the two. Then 5 to 4 and swaps, followed by comparing 5 to 2 and swap, then 5 and 8 before finishing the iteration. This continues until each element has been properly swapped. Let's write some code that does this.
Because it is a comparison loop, we have a nested for loop that compares one element against each of the others as it’s sorted. Inside the second loop, we have a conditional that if the element in front of the next element is bigger, we begin the swap. We manage this by creating a temporary variable and set it as the first element, then reassign that element to the next in line. We then reassign that element with the temporary value. And then we move on to the next one until we reach the end. And that is bubble sorts! You can see how it isn't the most efficient, but it’s still an important algorithm to know. Hope this helps!
