Sort an Array with a JavaScript do while Loop using Bubble Sort
Bubble sort is often one of the first sorting algorithms people learn because it closely resembles how we might physically sort a collection of items. We loop through our list of items, comparing our current item with the next one. If our current item is less than the next one, we swap them. We continue looping through the list until we make a loop without any swaps.
This is a very inefficient algorithm with a time complexity of O(n^2). Given a list of length n, we must compare each item against every other item in the list, which gives us n * n, or rather n^2. That means for a list of length 10, our worst case scenario will require 100 loops to sort our list. A list just twice as long will take 4x as many loops to solve.
Instructor: [00:00] To write the bubble sort algorithm, let's create a function that accepts an array, mutates that array for sorting and then returns that array. Bubble sort works by looping over the array as many times as necessary to get it sorted.
[00:14] Each time we iterate over the array, we check if the current item is greater than the next item. If it is, we swap it in place, and we indicate that we've made a swap during this iteration.
[00:25] Then if we've made a swap, we loop through the array again. We continue looping until we make a pass where no items have been swapped.
[00:33] Since the way we know that an array is sorted is that no swaps occurred during it, we need to at least iterate over the array once in order to determine that it's sorted. This is a perfect situation for a do/while loop in our algorithm.
[00:48] Since the condition we're going to test is whether or not a swap occurred in each iteration, we need to store a variable that holds that swap state for us. We can pass it as the condition into our while portion of our do/while loop.
[01:02] The first thing we need to do in our do/block is reset the swap value. This prevents any bugs from occurring from setting swap to true in the previous iteration and forgetting to reset it.
[01:14] Now we want to iterate over each item in our array, so we'll use array.foreach for that. Foreach receives a callback function. The arguments given to that callback function that we need are the item and the index of that item.
[01:29] The condition that we're checking is if this item is greater than the next item, so we can use array-index-plus-one. If this condition is met, what we want to do is temporarily store our current item in a variable. We'll then set the current array index to the next item and set the next array index to our temporarily stored item.
[01:52] This has swapped our two items, and thus, we can now set swap to true. That's our bubble sort algorithm in total.
[02:01] I want to add something that helps us visualize what the algorithm does through each iteration, so I'm going to use the Print Array utility that I've imported into this file to display the state of the array before each comparison. Now I'm going to create an array of unsorted numbers.
[02:20] We can pass that numbers array into our bubble sort function. If I log this into our terminal, we'll get to see the array as it transforms through each comparison and swap.
[02:30] If we scroll all the way out, we can see how our array was sorted. Now this was happening before each comparison. The 10 quickly moved all the way to the right because it's greater than every current item.
[02:41] We begin to see less drastic movements of items as the array becomes more and more sorted, all the way until we get to the end and we see what appears to be about 19 redundant passes through the array.
[02:53] This happens because of the two swaps with the one in the very last iteration here, and then we go through all the rest of the iterations, the nine iterations of our array with swapped being true.
[03:05] Then we need to make one more pass through the array even though we know it's sorted because we need to guarantee that nothing gets swapped.
Hi Alexander, it's true that we could optimize this further, but that misses the point. As the episode text discusses, bubble sort is an inefficient algorithm, it performs poorly. I teach this algorithm just to show people how to do it, as their first sorting algorithm and demonstrate why it performs poorly. There are better algorithms that come in the other lessons.
Makes sense. Thanks for explaining your point.
From observing the array in the process of sorting it's possible to notice that each iteration pushes the maximum number to the right side, so with each iteration the array becomes sorted from the end and it's not needed to loop over all items in the 2nd loop.
Wikipedia article shows even better improvement: https://en.wikipedia.org/wiki/Bubble_sort