Monday, November 5, 2012

Quick Sort Algorithm in Java

Here is a small example of the quick sort algorithm in Java

package com.giri.sort;

public class QuickSort {
 
 static int partition(int arr[], int left, int right)
 {
  int i = left;
  int j = right;
  int tmp;
  int pivot = arr[ (left+right)/2 ];
  
  while( i<= j )
  {
   while ( arr[i] < pivot )
   {
    i++;
   }
   
   while( arr[j] > pivot )
   {
    j--;
   }
   
   if(i<= j)
   {
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    i++;
    j--;
   }
  }
  
  return i;
 }
 
 static void quickSort(int arr[], int left, int right)
 {
  int index = partition(arr, left, right);
  
  if(left< index-1)
  {
   quickSort(arr,left,index-1);
  }
  if( index < right) 
  {
   quickSort(arr,index,right);
  }
 }
 
 public static void printArray(int[] arr){
  System.out.println("\nPrinting array contents:");
  for(int i=0; i<arr.length; i++ ) {
   System.out.print("["+arr[i]+"] ");
  }
  System.out.println("\n");
 }
 
 public static int generateRandomNumber(int Min, int Max) {
  int rand = Min + (int)(Math.random() * ((Max - Min) + 1));
  return rand;
 }

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int min = 1;
  int max = 100;
  int totalRandomNumbers = 20;
  int[] array = new int[totalRandomNumbers];
  
  for(int i=0; i<totalRandomNumbers; i++ ) {
   array[i] = generateRandomNumber(min,max);
  }
  
  System.out.println("\n Printing array contents BEFORE sorting:");
  printArray(array);
  
  int i = 0;
  int j = array.length - 1;
  
  System.out.println("\n Printing array contents AFTER sorting:");
  quickSort(array, i, j);
  
  printArray(array);
  
 }

}

Output:


 Printing array contents BEFORE sorting:

Printing array contents:
[60] [90] [65] [92] [91] [8] [94] [53] [5] [74] [17] [64] [71] [73] [58] [53] [3] [57] [76] [44] 


 Printing array contents AFTER sorting:

Printing array contents:
[3] [5] [8] [17] [44] [53] [53] [57] [58] [60] [64] [65] [71] [73] [74] [76] [90] [91] [92] [94] 

No comments :

Post a Comment