Bubble Sort and it's Optimization

Sorting 10,000 numbers in an array...

...or, Why you shouldn't use Bubble Sort.

Sort Basics

What are we going to do?

In our data are stored an array of 10,000 unique integers between 1 and 10,000 (inclusive) in random order. Just open the console in dev-tools if you want to view the pre-sorted array.

  1. We will sort our array using the built-in Array.prototype.sort() function and time how long it takes.

  2. We will sort our array using the standard bubble-sort algorithm. This algorithm 'bubbles' the highest number to the end of the array by making a series of comparisons between two consecutive values in the array as it iterates through the array. So it will iterate through the entire array and on each iteration will also iterate through the entire array. This is n^2 time.

  3. We will sort our array again using the bubble-sort with some special modifications.

    • We can assume on each full iteration through the array that the last item will be in proper order. So we can limit our inner-iterations array.length minus the number of full iterations completed.

    • Also, we can stop the full iterations once we have completed an inner iterations without making a swap.

    • By making these two changes, compared to the bubble sort, we reduce sort time dramatically and reduce total iterations by just over 50%. Nevertheless, Bubble Sort remains a very inefficient sort algorithm.

    • Inspired by: https://dev.to/vaidehijoshi/bubbling-up-with-bubble-sorts

See Console to Verify Sort


JS Sort

Optimized Bubble

Bubble Sort