Difference between revisions of "CSC212 Homework 8 Solution 2014"

From dftwiki3
Jump to: navigation, search
(Created page with "--~~~~ ---- <br /> <onlydft> =Program #1= <br /> <source lang="java"> </source> <br /> =Program #2= <br /> <source lang="java"> import java.io.File; import java.io.FileNotFoun...")
 
 
Line 6: Line 6:
 
<br />
 
<br />
 
<source lang="java">
 
<source lang="java">
 +
import java.util.Random;
 +
import java.util.PriorityQueue;
 +
 +
public class Hw8_1 {
 +
   
 +
    static Random randomGenerator = null;
 +
   
 +
    static public void displayArray(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 void displayPartition(int[] A, int low, int high,
 +
                                        int partitionIndex) {
 +
        for (int i = 0; i < A.length; i++) {
 +
            if (i < low || i > high) {
 +
                System.out.print("X ");
 +
                continue;
 +
            }
 +
            if (i == low)
 +
                System.out.print("[");
 +
           
 +
            if (i == partitionIndex)
 +
                System.out.print("(" + A[i] + ") ");
 +
            else
 +
                System.out.print(A[i] + " ");
 +
            if (i == high)
 +
                System.out.print("]");
 +
            if (i > high)
 +
                System.out.print("X ");
 +
        }
 +
        System.out.println();
 +
    }
 +
   
 +
    /**
 +
    * 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) {
 +
        if ( randomGenerator == null )
 +
        randomGenerator = new Random();
 +
 +
        int pivot = A[low + randomGenerator.nextInt( high-low )];
 +
        int i = low - 1;
 +
        int j = high + 1;
 +
       
 +
       
 +
        while (true) {
 +
            i++;
 +
            while (i < high && A[i] < pivot)
 +
                i++;
 +
            j--;
 +
            while (j > low && A[j] > pivot)
 +
                j--;
 +
           
 +
            if (i < j)
 +
                swap(A, i, j);
 +
            else
 +
                return j;
 +
        }
 +
    }
 +
   
 +
    public static void quickQuickSort(int[] A, int low, int high, int NN ) {
 +
    if ( low > NN )
 +
    return;
 +
        if (low < high ) {
 +
       
 +
            int pivotIndex = partition(A, low, high);
 +
           
 +
            //displayPartition(A, low, high, pivotIndex);
 +
            quickQuickSort(A, low, pivotIndex, NN );
 +
            quickQuickSort(A, pivotIndex + 1, high, NN );
 +
        }
 +
    }
 +
   
 +
    private static int[] initArray(int N, String arrayOrder) {
 +
        int[] A = new int[N];
 +
        if (arrayOrder.contains( "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 boolean isSortedBelowAndUnsortedAbove( int[] A, int NN ) {
 +
    for ( int i=1; i<NN; i++)
 +
    if ( A[i] < A[i-1] ) {
 +
    System.out.println( "ERROR: your array is not sorted below N" );
 +
    return false;
 +
    }
 +
   
 +
    boolean sorted = true;
 +
    for ( int i=NN; i<A.length; i++ )
 +
    if ( A[i] > A[i-1] )
 +
    sorted = false;
 +
    if  ( sorted && NN < A.length ) {
 +
    System.out.println( "ERROR: your array is sorted above N" );
 +
    return false;
 +
    }
 +
   
 +
    return true;
 +
    }
 +
 
 +
    public static void main(String[] args) {
 +
        int N;
 +
        int NN;
 +
        String arrayOrder;
 +
        boolean display = false;
 +
 +
        if (true || args.length == 0) {
 +
            N = 30;
 +
            NN = 30;
 +
            arrayOrder = "decreasing";
 +
            display = true;
 +
        } else {
 +
            N = Integer.parseInt( args[0] );
 +
            arrayOrder = args[1].toLowerCase();
 +
            NN = Integer.parseInt( args[2] );
 +
            display = args.length==4;
 +
        }
 +
       
 +
        int[] A = initArray(N, arrayOrder);
 +
       
 +
        if ( display )
 +
            displayArray( arrayOrder, A);
 +
 +
 +
        long start = System.nanoTime();
 +
        quickQuickSort(A, 0, A.length - 1, NN );
 +
        long end  = System.nanoTime();
 +
        System.out.println( String.format( 
 +
                                "quickSort( %d ) in %s order --> %1.3f msec", N,
 +
                                arrayOrder,  (end-start)/1000000.0f ) );
 +
       
 +
        isSortedBelowAndUnsortedAbove( A, NN );
 +
       
 +
        if ( display )
 +
            displayArray("sorted A", A);
 +
       
 +
    }
 +
   
 +
}
 +
 
</source>
 
</source>
 
<br />
 
<br />

Latest revision as of 18:51, 15 November 2014

--D. Thiebaut (talk) 15:41, 14 November 2014 (EST)



...


Retrieved from "http://dominiquethiebaut.com/dftwiki3/index.php?title=CSC212_Homework_8_Solution_2014&oldid=24283"