I failed this Bubble Sort interview! (Software engineering)
Corrections:
2:15, they swap when a is greater than b
6:08, you cannot exit a bubble sort early in the way I described
6:50, Dart/Javascript List.sort / Array.sort does not use bubble sort
-------
Had to record the audio twice! Forgot to discuss time complexity on this bubble sort, which I'm guessing is O(n^2) worst case and O(n) best case.
Also, after making this video I have learned that there are much more efficient sorting algorithms, even though I intuitively believed that bubble sort was fairly optimized. Which brings up the question, why would an interview request that someone build something that is not efficient and they won't see on the job? Wouldn't it be better to ask them which sorting algorithm is efficient?
Dart uses Dual-Pivot Quicksort, and the implementation can be found here: https://github.com/dart-lang/sdk/blob... Interestingly enough, this appears to also have an O(n^2) worst case, so intuitively bubble sort does appear to have an optimized worst case, but not an optimized average or best case. Always interesting how intuitive engineering can predict part of the story very quickly, but not all of it. Be careful!
Sorting algorithm comparisons: https://www.toptal.com/developers/sor...
Tweet: / 1499814068592553988
Wikipedia: https://en.wikipedia.org/wiki/Bubble_...
Dartpad: https://dartpad.dev/8d17668c590015c86...