Another simple sort is the odd-event sort. The idea is to repeatedly make two pa
ID: 3889771 • Letter: A
Question
Another simple sort is the odd-event sort. The idea is to repeatedly make two passes through the array. On the frist pass you look at all the pairs of items a[j] and a[j+1], where j is odd (1,3,5...). If their key values are out of order, you swap them. On the second pass you do the same for all the even values(j =2,4,6...). You do these two passes repeatedly until the array is sorted. Replace the bubbleSort() method in bubbleSort.java(listing3.1) with an oddEvenSort() method. Make sure it works for varying amounts of date. You'll need to figure out how many times to do the two passes,
The odd-even sort is actually useful in a multiprocessing environment, where a separate processor can operate on each odd pair simultaneously and then on each even pair. Because the odd pairs are independent of each other, each pair can be checked - and swapped, if necessary-by a different processor. This makes for a very fast sort.
Listing 3.1
class ArrayBub{ private long [] a; private int nElems;
public ArrayBub(int max) { a = new long[max]; nElems = 0;}
public void insert(long value){a[nElems]=value; nElems++;}
public void display() { for(int j=0; j<nElems; j++) System.out.print(a[j]+ " "); System.out.println(" ");
public void bubbleSort(){int out,in; for(out = nElems-1; out>1; out--;) for(int=0; int<out; in++) if(a[in] > a[in+1]) swap(in,in+1);
private void swap(int one, int two){long tem = a[one]; a[one]=a[two];a[two]=temp;}
Explanation / Answer
import java.io.*;
class ArrayBub {
private long[] a;
private int nElms;
public ArrayBub(int max){
a = new long[max];
nElms = 0;
}
public void insert(long value){
a[nElms] = value;
nElms++;
}
public void display(){
for (int i = 0; i<nElms; i++){
System.out.print(a[i] + " ");
}
System.out.println();
}
public void oddEvenSort(){
boolean sorted = false;
while (!sorted){
sorted = true;
for (int i = 0; i<nElms-1; i++){
if (a[i+1] < a[i])
sorted = false;
}
for (int i = 1; i<nElms; i=i+2){
if (i+1 < nElms){
if (a[i+1] < a[i]){
swap(i+1,i);
}
}
}
for (int i = 0; i<nElms; i=i+2){
if (i+1 < nElms){
if (a[i+1] < a[i]){
swap(i+1,i);
}
}
}
}
}
public void swap(int one, int two){
long temp;
temp = a[one];
a[one] = a[two];
a[two] = temp;
}
}
public class DemoArrayBub{
public static void main(String[] args){
ArrayBub a = new ArrayBub(5);
a.insert(5);
a.insert(3);
a.insert(7);
a.insert(1);
a.insert(4);
System.out.println("Given array:");
a.display();
a.oddEvenSort();
System.out.println("Sorted array:");
a.display();
}
}