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.
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
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.