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.print( array[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>_
|
Download this example.
|
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
