Sunday, May 13, 2012

Quick Sort Program in Java -Explanation+Complete Source Code

Quick-sort is a sorting technique commonly called divide and conquer algorithm. Quick-sort first divides a large array of items into two smaller arrays : the low items and high items(ie:all elements in first array is less than all elements in second). 
Quick sort algorithm involves three steps
  1.  An n element, called a pivot is picked from the array.Pivot is commonly the middle element of the array
  2. Rearrange the array elements such that all elements less than the pivot come before the pivot and all elements greater than the pivot come after the pivot,this step is called array partitioning
  3. Then a recursive sorting of the partitioned arrays is done individually
Following is the complete source code for Quick-sort program in Java.

 import java.io.*;  
 import java.lang.*;  
 class array  
 {  
//c-madeeasy.blogspot.com
  DataInputStream get=new DataInputStream(System.in);  
  int a[];  
  int i,n,h,l;  
  void getdata(int n,int x,int y)  
  {  
  try  
  {  
   a=new int[n];  
   System.out.println("Enter the elements");  
   for(i=0;i<n;i++)  
   a[i]=Integer.parseInt(get.readLine());  
  }  
  catch(Exception e)  
  {  
   System.out.println(e.getMessage());  
  }  
  l=x;  
  h=y;  
  }  
  void sort(int l,int h)  
  {  
  int temp,key,low,high;  
  low=l;  
  high=h;  
  key=a[(low+high)/2];  
  while(low<=high)  
  {  
   while(key>a[low])  
   {  
   low++;  
   }  
   while(key<a[high])  
   {  
   high--;  
  }  
  if(low<=high)  
   {  
   temp=a[low];  
   a[low]=a[high];  
   a[high]=temp;  
   low++;  
   high--;  
   }  
   }  
   if(l<low-1)  
   {  
   sort(l,low-1);  
   }  
   if(low<h)  
   {  
   sort(low,h);  
   }  
  }  
  void display(int n)  
  {  
  System.out.println("Asending order is");  
  for(i=0;i<n;i++)  
  System.out.println(" "+a[i]);  
  }  
  }  
  class quicksort  
  {  
  public static void main(String arg[])  
  {  
   array obj=new array();  
   DataInputStream get=new DataInputStream(System.in);  
   int n,x,y;  
   n=0;  
  try  
   {  
   System.out.println("Enter the limit");  
   n=Integer.parseInt(get.readLine());  
   }  
  catch(Exception e)  
   {  
   System.out.println(e.getMessage());  
  }  
  x=0;  
  y=n-1;  
  obj.getdata(n,x,y);  
  obj.sort(x,y);  
  obj.display(n);  
  }  
  }  

No comments:

Post a Comment

Which is the Best Photo Watermarking Software

Photo Theft is becoming more and more common in the web with the outburst of social websites like Facebook,Google Plus and Image sharing se...