Odd-Even Bubble Sort

Odd-Even bubble sort is a variation of the bubble sort algorithm, that is adapted to take advantage for multiprocessing environments, by tasking individual processors to perform comparisons and swaps due to its inherent non-overlapping nature.

In a Odd-Even bubble sort, all elements in odd/even positions are compared with the element in position next to them. If it is found that the element to the right of the odd/even position is greater than element at the odd/even position, then they are swapped.

So the steps include:

Step 1:

Compare element in next Odd position with the next element and perform swap if necessary.

Step 2:

Repeat Step 1, until we reach the last element in position of the data-set

Now, these steps 1 & 2 are repeated for the elements in Even positions.

Now by performing these steps 1 & 2 for all elements at odd positions, followed by all elements at even positions, only moves the bigger element by 2 positions to the right at the most, with one-position shift during step 1 while sorting Odd positions, and that is followed by one-position shift during step 1 while sorting Even positions.

Obviously a 2 position shift does not guarantee that the biggest element will necessarily move to the end of the data-set, provided the biggest element is at position 0, and the data-set is larger than 3. It needs to be moved further, to definitively shift to the end of the data-set which means that steps 1 & 2, for odd and even positions need to be repeated.

In order to determine, how many times steps 1 & 2, for odd and even positions need to be repeated, let us reexamine the fact that the largest element gets shifted 2 positions at the most by performing steps 1 & 2, for odd and even positions. For a element at position 0, to be shifted to position n-1 in a n element data-set, we can easily deduce that n-1 shifts need to happen such as 0->1,1->2,......,n-2->n-1.

An example often helps understand concepts and here is one, for you.

In a 5 element data-set, for a big element to travel from position 0 to position 4, the following 4 shifts need to be happen:

Shift 1: Position 0 -> Position 1

Shift 2: Position 1 -> Position 2

Shift 3: Position 2 -> Position 3

Shift 4: Position 3 -> Position 4

Now, we already concluded that a big element travels 2 positions at most with repetition of steps 1 & 2, for odd and even positions. So for a big element at position 0 to travel to position 4 in a 5 element data-set, at the rate of 2 positions shifts per repetition of steps 1 & 2, we only need:

4 positions to shift/2 positions shift per repetition
= 2 repetitions of odd and even shift steps 1 & 2

And the shifts would look like this:

Step 1 - Odd: Shift 1: Position 0 -> Position 1

Step 1 - Even: Shift 1: Position 1 -> Position 2

Step 1 - Odd: Shift : Position 2 -> Position 3

Step 1 - Even: Shift 1: Position 3 -> Position 4

So for a element to shift from 0 to n-1 in a n element data-set, at the rate of 2 positions shifts per repetition of steps 1 & 2, we only need:

 n-1 positions to shift/2 positions shift per repetition

= (n-1)/2 repetitions of odd and even shift steps 1 & 2

which we will refer as “repetition count” here after.

Since there is no such thing as half-shift in our algorithm, we always “ceil” the result of the (n-1)/2  to the nearest higher integer, so a 5/2 = 2.5 becomes 3, in a 6 element data-set.

The following video demonstrates how a Odd-Even algorithm works, since nothing can beat seeing something in action:

In our programmatic implementation, we use the following variables to represent the key variables to track the odd, even and repetition count:

Next odd position to sort ("Odd" pointer in workings video): "op"

Next even position to sort("Even" pointer in workings video): "ep"

Repetition count("Repetition Counter" in workings video): "rc"

And we utilize the “ceil” method that is defined in several languages to determine the value of “rc”. Here is a reference to java’s own “ceil” method:

https://www.tutorialspoint.com/java/lang/math_ceil.htm

Removing Duplicates from sorted data-set in one pass

In order to remove duplicates in a sorted data-set, we can employ several algorithms with varying degrees of efficiency. The algorithm that is discussed in this video, involves a single pass of the data-set, and probably one of the efficient techniques with a worst case efficiency of O(N), for a data-set of size N.

This technique involves repeatedly finding and recognizing the next unique value, (in contrast to finding the duplicates) and re-inserting/copying that next unique value in successive positions starting from position 0, overwriting the values in those positions. Finally, when there are no more unique values, we either resize the data-set to end at the last overwritten position or empty the remaining positions after the last overwritten position.

Three separate variables are engaged in tracking the important parameters of this algorithm:

Last Unique Value Index ( tracked using variable “ui”)

The value pointed by “Last Unique Value”, represents the unique value that is found in our search.

Current Index (tracked using variable “ci”)

The value pointed by “Current Index”, at any given moment, represents the current value that is being checked to identify if it is unique or repeated (hence a duplicate).

Next Replaceable Index (tracked using variable “ni”)

The value pointed by “Next Replaceable Index”, at any given moment, represents the position, where the next identified unique value (identified by checking if value at position “last unique value” is different than value at position “Current Index”) is inserted by replacing the value at that position previously.

Initially, an assumption is made that the value at position “Last Unique Value Index” is the value at position 0, and the current index, as well as next replaceable index are pointing to position 1.

With that assumption, we will repeatedly sought out the next unique value, by comparing the value at “Current Index” with value at “Last unique value Index”, by repeating the following steps until “Current Index” reaches the end of our data set.

Step 1:

If value at “Current Index” with value at “Last unique value Index” are found to be different, we replace the value at position “Next Replaceable Index” with the value at position “Current Index”,and update our “Last unique value index” to point to position “Current Index”.

Step 2:

If value at “Current Index” with value at “Last unique value Index” are found to be the same, then we move our “Current Index” to the next position and repeat Step 1.

These steps and the algorithm is better understood by watching the following video about how this technique works:

These steps are converted into a program in the following video:

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