Monday 12 September 2011

Bidirectional Bubble Sort in Java

Introduction : Bidirectional Bubble Sort
In this example we are going to sort integer values of an array using bi-directional bubble sort.

Definition:

A alternative of bubble sort is bi-directional bubble sort. The  bi-directional bubble sort compares each adjacent pair of elements in an array. The values will be swap if necessary. The values passes from the beginning to the end and also from the end to the beginning. It stops when there is no any element to swap.
Bi-directional bubble sorting also known as cocktail shaker sort, shaker sort, double-direction bubble sort. The complexity of bi-directional bubble sort is O(n2).Bi-directional bubble sort is  better than bubble sort. In Bi-directional bubble sort at least one elements is moved forward or backward to its place in the array with each pass. But in the case of bubble sort moves elements by forward direction to its place, but can only move elements backward in only one location in each pass.
  
Working of bi-directional bubble sort algorithm:
Say we have an array unsorted  A[0],A[1],A[2]................ A[n-1] and A[n] as input. Then the following steps are followed by bi-directional bubble sort algorithm to sort the values of an array.
 1.Compare A[0] &A[1] and  A[n-1] & A[n] .
 2.If A[0]>A[1] then Swap A[0] & A[1] and also if A[n-1]>A[n] then swap it.
 3.Take next A[1] & A[2] and A[n-2] & A[n-1].
 4.Comapre these values.
 5.If A[1]>A[2] then Swap A[1] & A[2] and also if A[n-2]>A[n-1] then swap it.
 ...............................................................
................................................................
Stop: when there is no any  pass for swap or the array values are in sorted order.

The code of the program :
public class BidirectionalBubbleSort{
  public static void main(String a[]){
  int i;
  int array[] {12,9,4,99,120,1,3,10};
  System.out.println("\n\n RoseIndia\n\n");
  System.out.println(" Selection Sort\n\n");
  System.out.println("Values Before the sort:\n");
  for(i = 0; i < array.length; i++)
  System.out.printarray[i]+"  ");
  System.out.println();
  bidirectionalBubble_srt(array, array.length);
  System.out.print("Values after the sort:\n");
  for(i = 0; i <array.length; i++)
  System.out.print(array[i]+"  ");
  System.out.println();
  System.out.println("PAUSE");
  }

  public static void bidirectionalBubble_srt(int array[]int n){
  int j;
  int st = -1;
  while (st <  n) {
  st++;
  n--;
  for (j = st; j <  n; j++) {
  if (array[j> array[j + 1]) {
  int T = array[j];
  array[j= array[j + 1];
  array[j + 1= T;
  }
  }
  for (j =  n; --j >= st;) {
  if (array[j> array[j + 1]) {
  int T = array[j];
  array[j= array[j + 1];
  array[j + 1= T;
  }
  }
  }
  }
}
Output of the example:
C:\array\sorting>javac BidirectionalBubbleSort.java
C:\array\sorting>java BidirectionalBubbleSort
       RoseIndia
       Selection Sort
Values Before the sort:
12  9  4  99  120  1  3  10
Values after the sort:
1  3  4  9  10  12  99  120
PAUSE
C:\array\sorting>_

No comments: