A Bi-directional Bubble Sort

In a traditional bubble sort, we repeatedly find the largest elements and move them towards the end of the dataset, from left to right, eventually sorting the entire dataset.

A variation of this technique involves finding the smallest element from the dataset and moving it from right to left. This would accumulate the smallest elements towards the starting part of the dataset, and cut the time required to of course reduce the sort time in half, since we can confidently skip trying to sort all of the smallest elements once they are moved to the left.

We will refer this technique as Bi-directional Bubble Sort, where the largest elements are carried from left to right, and the smallest elements are moved from right to left, in each iteration.

Here is a video demo of how Bi-directional Bubblesort works:

Now what would  a program for a Bi-directional Bubble Sort look like ? Watch the video to see how it is written :

As always, we will try to compare these 2 variations of Bubble sort by measuring the the time it took to measure how long these 2 variations took to sort 100,000 randomly generated numbers. Here are the results:

Technique	Time to sort 100k random values (in msec)	Time to sort 100k random values (in sec)
Bubble sort - Traditional	20552 msec	20 sec
Bubble Sort - Bi-directional	13078 msec	13 sec