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(n²).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

Bubble Sorting in Java

Introduction

In this example we are going to sort integer values of an array using bubble sort.

Bubble sort is also known as exchange sort. Bubble sort is a simplest sorting algorithm. In bubble sort algorithm array is traversed from 0 to the length-1 index of the array and compared one element to the next element and swap values in between if the next element is less than the previous element. In other words, bubble sorting algorithm compare two values and put the largest value at largest index. The algorithm follow the same steps repeatedly until the values of array is sorted. In worst-case the complexity of bubble sort is O(n2) and in best-case the complexity of bubble sort is Ω(n).

Code description:

Bubble Sorting is an algorithm in which we are comparing first two values and put the larger one at higher index. Then we take next two values compare these values and place larger value at higher index. This process do iteratively until the largest value is not reached at last index. Then start again from zero index up to n-1 index. The algorithm follows the same steps iteratively unlit elements are not sorted.

Working of 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 bubble sort algorithm to sort the values of an array.
1.Compare A[0] and A[1] .
2.If A[0]>A[1] then Swap A[0] and A[1].
3.Take next A[1] and A[2].
4.Comapre these values.
5.If A[1]>A[2] then swap A[1] and A[2]
...............................................................
................................................................
at last compare A[n-1] and A[n]. If A[n-1]>A[n] then swap A[n-1] and A[n]. As we see the highest value is reached at n^th position. At next iteration leave n^th value. Then apply the same steps repeatedly on A[0],A[1],A[2]................ A[n-1] elements repeatedly until the values of array is sorted.

In our example we are taking the following array values
12 9 4 99 120 1 3 10

The basic steps followed by algorithm:-

In the first step compare first two values 12 and 9.
12 9 4 99 120 1 3 10

As 12>9 then we have to swap these values
Then the new sequence will be
9 12 4 99 120 1 3 10

In next step take next two values 12 and 4
9 12 4 99 120 1 3 10

Compare these two values .As 12>4 then we have to swap these values.
Then the new sequence will be
9 4 12 99 120 1 3 10

We have to follow similar steps up to end of array. e.g.
9 4 12 99 120 1 3 10
9 4 12 99 120 1 3 10
9 4 12 99 1 120 3 10
9 4 12 99 1 120 3 10
9 4 12 99 1 3 120 10
9 4 12 99 1 3 10 120

When we reached at last index .Then restart same steps unlit the data is not sorted.

The output of this example will be :
1 3 4 9 10 12 99 120

public class bubbleSort{
 public static void main(String a[]){
   int i;
   int array[] = {12,9,4,99,120,1,3,10};
   System.out.println("Values Before the sort:\n");
   for(i = 0; i < array.length; i++)
     System.out.print( array[i]+"  ");
   System.out.println();
   bubble_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 bubble_srt( int a[], int n ){
   int i, j,t=0;
   for(i = 0; i < n; i++){
     for(j = 1; j < (n-i); j++){
       if(a[j-1] > a[j]){
         t = a[j-1];
         a[j-1]=a[j];
         a[j]=t;
       }
     }
   }
 }
}

Output of the example:

C:\array\sorting>javac bubbleSort.java

C:\array\sorting>java bubbleSort
Values Before the sort:
12  9  4  99  120  1  3  10

Values after the sort:
1  3  4  9  10  12  99  120

Two Dimensional arrays

Two-dimensional arrays are defined as "an array of arrays". Since an array type is a first-class Java type, we can have an array of ints, an array of Strings, or an array of Objects. For example, an array of ints will have the type int[]. Similarly we can have int[][], which represents an "array of arrays of ints". Such an array is said to be a two-dimensional array.
The command

int[][] A = new int[3][4];

declares a variable, A, of type int[][], and it initializes that variable to refer to a newly created object. That object is an array of arrays of ints. Here, the notation int[3][4] indicates that there are 3 arrays of ints in the array A, and that there are 4 ints in each of those arrays.
To process a two-dimensional array, we use nested for loops. We already know about for loop. A loop in a loop is called a Nested loop. That means we can run another loop in a loop.

Notice in the following example how the rows are handled as separate objects.

Code: Java
int[][] a2 = new int[10][5];
// print array in rectangular form
for (int i=0; i<a2.length; i++) {
   for (int j=0; j<a2[i].length; j++) {
       System.out.print(" " + a2[i][j]);
   }
   System.out.println("");
}

In this example, "int[][] a2 = new int[10][5];" notation shows a two-dimensional array. It declares a variable a2 of type int[][],and it initializes that variable to refer to a newly created object. The notation int[10][5] indicates that there are 10 arrays of ints in the array a2, and that there are 5 ints in each of those arrays.

Here is the complete code of the example:

public class twoDimension{
 public static void main(String[] args) {
   int[][] a2 = new int[10][5];
   for (int i=0; i<a2.length; i++) {
     for (int j=0; j<a2[i].length; j++) {
       a2[i][j] = i;
       System.out.print(" " + a2[i][j]);
     }
     System.out.println("");
   }
 }
}

Here is the output for the program:

C:\tamana>javac twoDimension.java

C:\tamana>java twoDimension
0 0 0 0 0
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
6 6 6 6 6
7 7 7 7 7
8 8 8 8 8
9 9 9 9 9