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);
}
}