Bubble sort using TypeScript
Bubble sort is considered the simplest sorting algorithm to implement. We’ll approach the problem in two ways. Once using a set number of iterations, and next using an idiomatic approach.
We’ll be covering this problem using TypeScript / Javascript
[00:00] First, we will go ahead and create a simple sorting function that explains the concept of bubble sort. The function takes an array of numbers as an argument, and will return a sorted array of numbers. Within the function, we create a copy of the original array using slice and then we return this array.
[00:25] Before returning it, we will sort it using bubble sort. Bubble sort works by looping over the input array n times. In each iteration, the goal is to bubble the highest-ranking value to the end. We loop through all the items in the array, and we simply check if the current value on the left is greater than the current value of the right.
[00:54] If so, we swap the variables at the two positions. This ensures that we keep bubbling the highest value to the last position of the array. Since we're looking up the (j+1)th item, it makes obvious sense to terminate the inner loop 1 before the last index. To demonstrate this bubbling of the highest value, let's run through a simple example.
[01:22] We will sort the array 4, 3, 2, 1. We expect the final result to be 1, 2, 3, 4. Within the function, we will log out the original array, and we will also log out the array whenever we do a swap.
[01:39] If we run this, you can see that 4 is bubbling to the end, and then 3 is bubbling to the second last position, and finally, 2 gets bubbled to the second position. This explains the concept of bubble sort and how it gets its name.
[02:05] Note that instead of always iterating n times, we can easily optimize the algorithm to terminate early. Let's duplicate the function to present a more idiomatic bubble sort implementation. We get rid of this always-in-time iterating outer loop.
[02:23] We create a variable to track if any bubbling takes place. We note it down whenever we swap a variable and break out of the loop once no more swapping is needed. Finally, we wrap the whole thing in a VAR loop that will terminate if no variable bubbling happens in an iteration.
[02:48] This implementation is similar to the previous one with the simple addition of early termination. This also explains the main real world use case of bubble sort, which is if you only have a few values that need to be swapped around, bubble sort can be pretty fast.
[03:08] In the worst case, this whole inner FOR loop of n iterations will run 0n) times, resulting in time complexity of 0n)2. Since we are doing the array swaps in place, the space complexity 0n).
@brent, if you see the the array[j] and array[j + 1] are indexes in the array and we are just swapping the values at the index.
@Basarat, how does the code get out of while (true) loop in the Idiomatic implementation?
@Basarat, never mind I got it. Didn't realize the flag set was inside the while loop.
@Basarat: I created arrays of 10K and 50K random integers. I sorted the same array in nodejs using both bubble sort examples. The idiomatic example performs slower that the basic sort example. Is that expected?
##############################################
# #
***** bubble sort *****
# #
##############################################
bubbleSortProcessing-[10000]: 4758.006ms
earlyTerminationBubbleSortProcessing-[10000]: 4994.364ms
[nodemon] clean exit - waiting for changes before restart
[nodemon] restarting due to changes...
[nodemon] starting `node ./index.js`
##############################################
# #
***** bubble sort *****
# #
##############################################
bubbleSortProcessing-[50000]: 119734.447ms
earlyTerminationBubbleSortProcessing-[50000]: 125780.788ms
[nodemon] clean exit - waiting for changes before restart
I did notice a performance gain with Idiomatic sort using smaller data sets.
##############################################
# #
***** bubble sort *****
# #
##############################################
bubbleSortProcessing-[500]: 16.692ms
earlyTerminationBubbleSortProcessing-[500]: 12.605ms
[nodemon] clean exit - waiting for changes before restart
I was wondering if you could help me understand how the swap line works.
[array[j], array[j + 1]] = [array[j + 1], array[j]];
Instead of swapping, it looks like the line is setting a new two item array to another new two item array.
^ For anyone wondering about this too, check out this SO answer https://stackoverflow.com/questions/872310/javascript-swap-array-elements
This is using array destructuring to swap elements. I'd seen it with variables, but not on arrays like this before.
I was wondering if you could help me understand how the swap line works.
Instead of swapping, it looks like the line is setting a new two item array to another new two item array.