Sunday, 29 April 2012

Bubble Sort with Early Exit in Java

import java.io.*;

class BubbleSort 
{
 public static void main(String[] args) 
 {
  try
  {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.print("Enter name of the source file: ");
   FileReader fr =new FileReader(br.readLine());

   char[] buffer = new char[2048];
   int len = fr.read(buffer);

   String data = new String(buffer,0,len);

   String[] element = data.split(",");

   int[] a = new int[element.length];


   System.out.println("\n\nBefore Sorting: ");

   for(int i=0; i<a.length; i++)
   {
    a[i] = Integer.parseInt(element[i]);
    System.out.print(a[i]+"\t");
   }

   int c=0,m=0; //variables to keep track of comparisons and moves

   
   //Main logic of bubble sort with early exit
   

   for(int pass=0; pass<a.length; pass++)
   {
    boolean flag=true;

    for(int j=0; j<a.length-pass-1; j++)
    {
     c++;
     if(a[j]>a[j+1])
     {
      int temp = a[j];
      a[j] = a[j+1];
      a[j+1] = temp;
      m+=3;
      flag=false;
     }
    }

    if(flag)
     break;
   }
   
   System.out.println("\n\nAfter Sorting: ");

   for(int i=0; i<a.length; i++)
   {   
    System.out.print(a[i]+"\t");
   }

   System.out.println("\n\nComparisons = " + c + "\tMoves = " + m);
  }
  catch (Exception e)
  {
   e.printStackTrace();
  }
 }
}

No comments:

Post a Comment

Your comments are very much valuable for us. Thanks for giving your precious time.