quicksort2.java

bubble sort quick sort selection sort developed to measure time performance of each sorting an

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Harikrushna V
 */


public class QuickSort2 {
    private static long comparisons = 0;
    private static long exchanges   = 0;

  
    public static void quicksort(double[] a) {
        shuffle(a);                        
        quicksort(a, 0, a.length - 1);
    }

    // quicksort a[left] to a[right]
    public static void quicksort(double[] a, int left, int right) {
        if (right <= left) return;
        int i = partition(a, left, right);
        quicksort(a, left, i-1);
        quicksort(a, i+1, right);
    }

    // partition a[left] to a[right], assumes left < right
    private static int partition(double[] a, int left, int right) {
        int i = left - 1;
        int j = right;
        while (true) {
            while (less(a[++i], a[right]));      
                                          		
            while (less(a[right], a[--j]))     
                if (j == left) break;           
            if (i >= j) break;                  
            exch(a, i, j);                      
        }
        exch(a, i, right);                      
        return i;
    }
    // is x < y ?
    private static boolean less(double x, double y) {
        comparisons++;
        return (x < y);
    }
    // exchange a[i] and a[j]
    private static void exch(double[] a, int i, int j) {
        exchanges++;
        double swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
    // shuffle the array a[]
    private static void shuffle(double[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int r = i + (int) (Math.random() * (N-i));   // between i and N-1
            exch(a, i, r);
        }
    }
    // test client
    public static void main(String[] args) {
        for(int N=100;N<=1000000000;N*=10)
        {
	    	
	        long start;
	        long stop;
	        double elapsed;
	        double[] a = new double[N];
	        for (int i = 0; i < N; i++)
	        {
	        		a[i] = i;
	        }
	        // sort them
	        start = System.currentTimeMillis();
	        quicksort(a);
	        stop = System.currentTimeMillis();
	        
	        elapsed = (stop - start) ;
	        System.out.println("Quicksort:   " + elapsed + " miliseconds");
        }
    }
}