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);  
  }  
  }  

3 comments:

Post a Comment

Subscribe

The Source Codes Published in this Blog can be used freely for Educational purposes but should not be reproduced on any other Blog or Website without the consent of the author.