CSC212 Lab 12 Solution Programs 2014

--D. Thiebaut (talk) 16:47, 30 November 2014 (EST)

---

import java.util.Random;

/**
 * Some sorting algorithms
 * @author D. Thiebaut
 *
 */
public class Lab12_3 {

    static Random randomGenerator = new Random();
    
    /**
     * partitions the array around its first element (the pivot) 
     * @param A: the array
     * @param low: the lower bound
     * @param high: the upper bound
     * @return the index of the pivot
     */
    private static int partition(int[] A, int low, int high) {
        // pick first element as pivot
	
        int index = low + randomGenerator.nextInt( high-low + 1);
        swap( A, index, low );
        //index = low;
        int pivot = A[low];
        //System.out.println( "partition( A, " + low + ", " + high + ") pivot = " + pivot );
	
        int i=low;
        int j=high;
        while ( i < j ) {
            while ( i < high && A[i] < pivot ) i++;
            while ( j > low && A[j] >= pivot ) j--;
            if ( i < j )
                swap( A, i, j );
        }
        return j;
    }
    
	public static void quicksort(int[] A, int low, int high) {
            if (low < high) {
                
                int pivotIndex = partition(A, low, high);
                quicksort(A, low, pivotIndex );
                quicksort(A, pivotIndex+1, high);
            }
	}
    
    static public void display(String caption, int[] A) {
        System.out.print(caption + " = ");
        for (int i = 0; i < A.length - 1; i++)
            System.out.print(A[i] + ", ");
        System.out.println(A[A.length - 1]);
    }
    
    private static void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
    
    private static int[] initArray(int N, String arrayOrder) {
        int[] A = new int[N];
        if (arrayOrder == "random") {
            Random randomGenerator = new Random();
            for (int i = 0; i < N; i++)
                A[i] = randomGenerator.nextInt(N + 1);
        }
        if (arrayOrder.contains("increasing")) {
            for (int i = 0; i < N; i++)
                A[i] = i;
        }
        if (arrayOrder.contains("decreasing")) {
            for (int i = 0; i < N; i++) 
                A[i] = N-i;
        }
        return A;
    }
    
    public static void main(String[] args) {
        int N;
        String arrayOrder;
        Integer x;
        
        if (args.length == 0) {
            N = 20000000;
            arrayOrder = "increasing";
        } else {
            N = Integer.parseInt(args[0]);
            arrayOrder = args[1].toLowerCase();
        }
        
        int[] A = initArray(N, arrayOrder);
        
        //display("A in " + arrayOrder+ " order", A);
        
        // QUICKSORT
        long start = System.nanoTime();
        quicksort(A, 0, A.length - 1);
        long end = System.nanoTime();
        System.out.println( String.format( "Quicksort (%s order) --> %1.3f sec", 
                                           arrayOrder, (end-start)/1E9 ) );
        //display("sorted A", A);
        
    }
    
}