Monday 12 September 2011

Odd Even Transposition Sort In Java

Introduction
In this example we are going to sort integer values of an array using odd even transposition sort.

Odd even transposition sort is a parallel sorting algorithm. Odd Even is based on the Bubble Sort technique of comparing two numbers and swapping them and put higher value at larger index .In each parallel computational steps can pair off either the odd or even neighboring pairs. Each number (In Processing Element-PE) would look to it's right neighbor and if it were greater, it would swap them.

Code description:
The odd even transposition sort is a parallel sorting algorithm. That mean more than one compression can made at one iteration. The comparison is same as bubble sort.
Working of odd even transposition sort:

The code of the program :

public class OddEvenTranspositionSort{
  public static void main(String a[]){
  int i;
  int array[] {12,9,4,99,120,1,3,10,13};
  
  System.out.println("\n\n RoseIndia\n\n");
  System.out.println(" Odd Even Transposition 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();
  odd_even_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 odd_even_srt(int array[],int n){
  for (int i = 0; i < n/2; i++ ) {
  for (int j = 0; j+< n; j += 2)
  if (array[j> array[j+1]) {
  int T = array[j];
  array[j= array[j+1];
  array[j+1= T;
  }
  for (int j = 1; j+< array.length; j += 2)
  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 OddEvenTranspositionSort.java
C:\array\sorting>java OddEvenTranspositionSort
       RoseIndia
       Odd Even Transposition Sort
Values Before the sort:
12  9  4  99  120  1  3  10  13
Values after the sort:
1  3  4  9  10  12  13  99  120
PAUSE
C:\array\sorting>_

No comments: