desperately need help!!!
hi this is an assignment that i have to do and i've written some
code below. but i have to find the maximum and average of the
running time by repeating 5 times. please help me!
design an application program that performs benchmarking tests for ranking the sorting methods heapSort, mergeSort, and quickSort by their average
running time.
Each your test should involve an array of random integers. Your program should automatically search for an appropriate size of array for testing all
the three methods on any availagle PC. In so doing, it should start with a
relatively small array and use then basic ideas of a binary search for doubling or halving the array size or its increment/decrement in order to
approach the desired minimum time of sorting a single array by all the methods. the minimum time should be greater than or equal to 50 milliseconds
after finding the proper array size, your program has to repeat each test for
each sort at least 5 times using different random arrays of the fixed found size. Your application should output four text lines
1) the size of the sorted arrays and (2-4) the name of the sort and its average, minimum, and maximum running time. The lines 2-4 should be in the ascending order of the average time, for example
Size: 256700
<sort1>: average 68.6 ms: min 54.3 ms: max 87.7ms
<sort2>: average 78.2 ms: min 66.1 ms: max 99.3 ms
<sort3>: average 98.6 ms: min 74.3 ms: max 121.0ms
where<sorti> stands for a particular sort(e.g heapSort, mergeSort, quickSort)
You should measure running time with the System.currentTimeMillis() method
long startTime = System.CurrentTimeMillis();
someSort(arrayToSort);
long runTime = System.CurrentTimeMillis()-starTime;
public class Sort {
protected static long MIN_TOTAL_TIME = 500;
protected static long NUM_MEASUREMENTS=10;
public static void main(String[] args){
long startTime, endTime, totalTime=0, totalTime1=0, totalTime2=0;
int n = 50;
int a[];
int b[];
int c[];
//================================
//= Find value for array size n =
//================================
while(totalTime<MIN_TOTAL_TIME || totalTime1><MIN_TOTAL_TIME ||totalTime2><MIN_TOTAL_TIME){
n*=2;
a = new int[n];
b = new int[n];
c = new int[n];
for(int j=0; j><NUM_MEASUREMENTS; j++) {
for(int i=0; i><n; i++)
a= (int) (Math.random()*n);
startTime = System.currentTimeMillis();
quickSort(a);
endTime = System.currentTimeMillis();
totalTime+= endTime - startTime;
for(int k=0; k><n; k++)
b[k]=(int) (Math.random()*n);
startTime =System.currentTimeMillis();
mergeSort(b);
endTime = System.currentTimeMillis();
totalTime1+= endTime - startTime;
for(int l=0; l><n;l++)
c[l] =(int) (Math.random()*n);
startTime = System.currentTimeMillis();
heapSort(c);
endTime = System.currentTimeMillis();
totalTime2+= endTime - startTime;
}
}
System.out.println("size:" +Integer.toString(n));
System.out.println("quickSort::" + totalTime);
System.out.println("mergeSort:" +totalTime1);
System.out.println("heapSort" +totalTime2);
}
// cutoff threshold for quickSort
static public int CUTOFF = 10;
//
// insertion sort algorithm
// a[] an integer array to be sorted
//
public static void insertionSort(int [] a) {
int i, tempi, k;
for( i = 1; i >< a.length; i++ ) {
tempi = a[ i ];
k = i - 1;
while( k >= 0 && tempi < a[ k ] ) {
a[ k + 1 ] = a[ k ];
k--;
}
a[ k + 1 ] = tempi;
}
}
//
// Shell's sort algorithm
// a[] an integer array to be sorted
//
public static void shellSort(int [] a) {
int i, tempi, k, gap;
for( gap = a.length / 2; gap > 0;
gap = ( gap == 2 )? 1 : (int)( gap / 2.2 ) )
for( i = gap; i < a.length; i++ ) {
tempi = a[ i ];
k = i;
while( k >= gap && tempi < a[ k - gap ]) {
a[ k ] = a[ k - gap ];
k -= gap;
}
a[ k ] = tempi;
}
}
//
// merge sort algorithm
// a[] an integer array to be sorted
//
// private methods:
// mergeSort() - recursive split / merge
// of a subarray (a[left],...,a[right])
// merge() - merge two presorted subarrays
//
public static void mergeSort( int [] a ) {
int []tmpArray = new int[ a.length ];
mergeSort( a, tmpArray, 0, a.length - 1 );
}
private static void mergeSort(
int [] a,
int [] tmpArray,
int left, int right ) {
if ( left < right ) {
int centre = ( left + right ) / 2;
mergeSort( a, tmpArray, left, centre);
mergeSort( a, tmpArray, centre + 1, right);
merge( a, tmpArray, left, centre + 1, right );
}
}
private static void merge(
int [] a,
int [] tmpArray,
int leftPos, int rightPos,
int rightEnd ) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int leftBeg = leftPos;
// Main merging loop
while( leftPos <= leftEnd && rightPos <= rightEnd )
if ( a[ leftPos ] < a[ rightPos ] )
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
else
tmpArray[ tmpPos++ ] = a[ rightPos++ ];
// Copy the rest of the first half if any
while( leftPos <= leftEnd )
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
// Copy the rest of the second half if any
while( rightPos <= rightEnd )
tmpArray[ tmpPos++ ] = a[ rightPos++ ];
// Copy tmpArray back
for( tmpPos=leftBeg; tmpPos <= rightEnd; tmpPos++ )
a[ tmpPos ] = tmpArray[ tmpPos ];
}
//
// quicksort algorithm
// a[] an integer array to be sorted
//
// private methods:
// quickSort() - choose a median-of-three
// pivot for partitioning a subarray
// (a[low],...,a[high]) and recursively
// sort the parts
// swap() - swap elements of an array
// insertionSort() - insertion sort of a
// subarray
//
public static void quickSort( int [] a ) {
quickSort( a, 0, a.length - 1 );
}
private static void quickSort( int [] a,
int low, int high) {
if( low + CUTOFF > high )
insertionSort( a, low, high );
else {
// Sort low, middle, high
int middle = ( low + high ) / 2;
if ( a[ middle ] < a[ low ] )
swapElements( a, low, middle );
if ( a[ high ] < a[ low ] )
swapElements( a, low, high );
if ( a[ high ] < a[ middle ] )
swapElements( a, middle, high );
// Place pivot at position high - 1
swapElements( a, middle, high - 1 );
int pivot = a[ high - 1];
// Begin partitioning
int i, j;
for( i = low, j = high - 1; ; ) {
while( a[ ++i ] < pivot );
while( pivot < a[ --j ] );
if ( i < j )
swapElements( a, i, j );
else
break;
}
// Restore pivot
swapElements( a, i, high - 1 );
quickSort( a, low, i - 1 ); // Sort small elements
quickSort( a, i + 1, high ); // Sort large elements
}
}
private static void swapElements( int [] a,
int i, int j ) {
int temp = a[ i ];
a[ i ] = a[ j ];
a[ j ] = temp;
}
private static void insertionSort(int [] a,
int low, int high) {
int i, tempi, k;
if (low > high || low < 0 || high >= a.length ) {
low = 0;
high = a.length - 1;
}
for( i = low + 1; i <= high; i++) {
tempi = a[ i ];
k = i - 1;
while( k >= low && tempi < a[ k ] ) {
a[ k+1 ] = a[ k];
k--;
}
a[ k+1 ] = tempi;
}
}
//
// heapsort algorithm
// a[] an integer array to be sorted
//
// private methods:
// heapify() - convert a subarray to a heap
// swap() - swap elements of an array
//
public static void heapSort( int [] a ) {
int index;
// build heap
for( index = a.length / 2 - 1; index >= 0;
index-- )
heapify( a, index, a.length );
// deleteMax
for( index = a.length - 1; index >= 1;
index-- ) {
swapElements( a, 0, index );
heapify( a, 0, index );
}
}
private static void heapify( int [] a,
int index,
int size ) {
int childPos;
int parentPos = index + 1;
// position is equal to index plus 1;
for( childPos = parentPos * 2; childPos < size;
childPos = parentPos * 2 ) {
if ( a[ parentPos - 1 ] < a[ childPos - 1 ] ||
a[ parentPos - 1 ] < a[ childPos ] ) {
if ( a[ childPos - 1 ] < a[ childPos] ) {
swapElements( a, parentPos - 1, childPos );
parentPos = childPos + 1;
}
else {
swapElements( a, parentPos - 1, childPos - 1 );
parentPos = childPos;
}
}
else break;
}
if ( childPos == size &&
a[ parentPos - 1 ] < a[ childPos - 1 ] )
swapElements( a, parentPos - 1, childPos - 1 );
}
}
