## Bi-Directional Bubble Sort Implementation in Java

[Note: This article was originally published in my another blog and has been migrated over here]

Definition:
Cocktail sort, also known as bidirectional bubble sort, cocktail shaker sort, shaker sort (which can also refer to a variant of selection sort), ripple sort, shuttle sort or happy hour sort, is a variation of bubble sort that is both a stable sorting algorithm and a comparison sort. The algorithm differs from bubble sort in that sorts in both directions each pass through the list. This sorting algorithm is only marginally more difficult than bubble sort to implement, and solves the problem with so-called turtles in bubble sort.

Differences From Bubble Sort:
Cocktail sort is a slight variation of bubble sort. It differs in that instead of repeatedly passing through the list from bottom to top, it passes alternately from bottom to top and then from top to bottom. It can achieve slightly better performance than a standard bubble sort. The reason for this is that bubble sort only passes through the list in one direction and therefore can only move items backward one step each iteration.

An example of a list that proves this point is the list (2,3,4,5,1), which would only need to go through one pass of cocktail sort to become sorted, but if using an ascending bubble sort would take four passes. However one cocktail sort pass should be counted as two bubble sort passes. Typically cocktail sort is less than two times faster than bubble sort.

Another optimization can be that the algorithm remembers where the last actual swap has been done. In the next iteration, there will be no swaps beyond this limit and the algorithm has shorter passes. As the Cocktail sort goes bidirectionally, the range of possible swaps, which is the range to be tested, will reduce per pass, thus reducing the overall running time.

[Source of above Text: Wikipedia.

The following is my implementation of Bidirectional Bubble Sort in Java.

```/**
* BidirectionalBubbleSort.java
*
* Author: Kushal Paudyal
* www.icodejava.com
*
*/
package com.kushal.sort;

public class BidirectionalBubbleSort {

/**
* The bidirectional bubble sort method that takes
* an array of unsorted integers, sorts them and
* returns a sorted array.
*/
public static int[] bidirectionalBubbleSort(int array[]) {
int length = array.length;
int j;
int st = -1;
while (st &lt; length) {
st++;
length--;
for (j = st; j &lt; length; j++) {
if (array[j] &gt; array[j + 1]) {
swap(array, j, j + 1);
}
}
for (j = length; --j &gt;= st;) {
if (array[j] &gt; array[j + 1]) {
swap(array, j, j + 1);
}
}
}
return array;
}

/**
* Swapping The Elements at two different indexes of an Arary
*/
private static void swap(int[] anArray, int firstIndex, int secondIndex) {
int temp = anArray[firstIndex];
anArray[firstIndex] = anArray[secondIndex];
anArray[secondIndex] = temp;
}

/**
* Method to print the content of any array.
*/
public static void printArray(int[] array) {
for (int i = 0; i &lt; array.length; i++)
System.out.print(array[i] + "  ");

System.out.println();
}

/**
* Testing the bidirectional bubble sort with some sample unsorted array of
* integers
*/
public static void main(String a[]) {
int unsortedArray[] = { 121, 79, 24, 190, 203, 1, 33, 110 };

System.out.print("Unsorted: \t");
printArray(unsortedArray);

int[] sortedArray = bidirectionalBubbleSort(unsortedArray);
System.out.print("Sorted: \t");
printArray(sortedArray);

}
/*
* SANJAAL CORPS MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
* THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
* TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
* PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SANJAAL CORPS SHALL NOT BE LIABLE FOR
* ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
* DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
*
* THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE
* CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE
* PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT
* NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE
* SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE
* SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE
* PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES"). SANJAAL CORPS
* SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR
* HIGH RISK ACTIVITIES.
*/
}
```

=========================
Sample Output

```Unsorted:     121  79  24  190  203  1  33  110
Sorted:     1  24  33  79  110  121  190  203
```