Difference between revisions of "CSC212 Homework 8 Solution 2014"
(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 /> |