Quicksort

Quicksort is an efficient sorting algorithm, developed by British computer scientist Tony Hoare in 1959.

Algorithm: 

  1. find Pivot element (it may be the first, last or random value in array)
  2. put elements in order. The elements on the Left side are lesser than the pivot element. The elements on the Right side are greater than the pivot element
  3. Repeat step 2 with remaining elements
  4. Abort criteria: The pivot element equals to the first index for the Left side. The pivot element equals to the last index of elements for the Right side

Now we implement a general solution using Quicksort algorithm with Integer, Double, Float values. In this step we use following Generic methods . 

  • public static <A extends Comparable<A>> int quickpart( A[] array,int low,int high){….}
  • int compareTo(Object obj){…} return:{1 , 0 -1}
public class Quicksort {

public static void main(String[] args) {
		
Integer[] testInteger = {5,3,1,6,8,2};
Double[] testDouble = {5.2,3.1,2.5,5.6,1.5,2.7};
Float[] testFloat = {2.2f,1.4f,2.6f,1.1f};

quicksort(testInteger,0,testInteger.length-1);
quicksort(testDouble,0,testDouble.length-1);
quicksort(testFloat,0,testFloat.length-1);

for(Integer val:testInteger) {
	System.out.print(" "+val);
}
System.out.println();
for(Double val:testDouble) {
	System.out.print(" "+val);
}
System.out.println();
for(Float val:testFloat) {
	System.out.print(" "+val);
}


	}
	
	
public static <A extends Comparable<A>> void  quicksort(A[] array,int low,int high){
		int pivot;
		
		if(low < high) {
			        pivot = quickpart(array,low,high);
			
			  
		            quicksort(array,low,pivot-1);
		        
			 
		            quicksort(array,pivot+1,high);
		        
		}
	}
public static  <A extends Comparable<A>>  int  quickpart( A[] array,int low,int high) {
	
    A pivot = array[high];
    
    
	for(int cnt = low;cnt < high;cnt++) {
	   if(array[cnt].compareTo(pivot) < 0 ) {
		A temp = array[low];
		array[low] = array[cnt];
		array[cnt] = temp;
		low++;
		
	    }
	
	
	}
	A temp2 = array[low];
	array[low] = pivot;
	array[high] = temp2;
	
	return low;
}

}

Output:

  1 2 3 5 6 8
  1.5 2.5 2.7 3.1 5.2 5.6
  1.1 1.4 2.2 2.6

Full Source Code:

Leave a Reply

Your email address will not be published. Required fields are marked *