I am having trouble with this program. I am trying to record the fastest, slowest, and average time each sorting method takes to execute in a trial run of 10. The only one that looks like it is working is the first sorting method (Selection). The program uses 50000 random integers in an array. Can anyone help me find out why the time only works for one method and not the other 5? Each trial code for the other sorting methods are the same as the first one, but it doesn't seem to work out the way it should.
import java.util.Random;
import java.util.Arrays;
import java.util.concurrent.TimeUnit;
public class Sorting
{
public static void main(String[] args)
{
int N = 50000;
int randNum[] = new int[N];
long total = 0;
long min = Integer.MAX_VALUE;
long max = Integer.MIN_VALUE;
Random rand = new Random();
for(int i = 0; i < N; i++)
{
randNum[i] = rand.nextInt(N);
}
System.out.println("_____Selection Sort_____");
for(int trial = 1; trial <= 10; trial++)
{
long start = System.nanoTime();
SelectionSort(randNum);
long end = System.nanoTime();
long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
total = total + time;
if(time < min)
{
min = time;
}
if(time > max)
{
max = time;
}
}
System.out.println("The fastest time: " + min + " nanoseconds");
System.out.println("The slowest time: " + max + " nanoseconds");
System.out.println("The average time: " + (total/10) + " nanoseconds");
System.out.println("\n_____Insertion Sort_____");
for(int trial = 1; trial <= 10; trial++)
{
long start = System.nanoTime();
InsertionSort(randNum);
long end = System.nanoTime();
long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
total = total + time;
if(time < min)
{
min = time;
}
if(time > max)
{
max = time;
}
}
System.out.println("The fastest time: " + min + " nanoseconds");
System.out.println("The slowest time: " + max + " nanoseconds");
System.out.println("The average time: " + (total/10) + " nanoseconds");
System.out.println("\n_____Bubble Sort_____");
for(int trial = 1; trial <= 10; trial++)
{
long start = System.nanoTime();
BubbleSort(randNum);
long end = System.nanoTime();
long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
total = total + time;
if(time < min)
{
min = time;
}
if(time > max)
{
max = time;
}
}
System.out.println("The fastest time: " + min + " nanoseconds");
System.out.println("The slowest time: " + max + " nanoseconds");
System.out.println("The average time: " + (total/10) + " nanoseconds");
System.out.println("\n_____Merge Sort_____");
for(int trial = 1; trial <= 10; trial++)
{
long start = System.nanoTime();
MergeSort(randNum); long end = System.nanoTime();
long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
total = total + time;
if(time < min)
{
min = time;
}
if(time > max)
{
max = time;
}
}
System.out.println("The fastest time: " + min + " nanoseconds");
System.out.println("The slowest time: " + max + " nanoseconds");
System.out.println("The average time: " + (total/10) + " nanoseconds");
System.out.println("\n_____Quick Sort_____");
for(int trial = 1; trial <= 10; trial++)
{
long start = System.nanoTime();
QuickSort(randNum, 0, randNum.length - 1);
long end = System.nanoTime();
long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
total = total + time;
if(time < min)
{
min = time;
}
if(time > max)
{
max = time;
}
}
System.out.println("The fastest time: " + min + " nanoseconds");
System.out.println("The slowest time: " + max + " nanoseconds");
System.out.println("The average time: " + (total/10) + " nanoseconds");
System.out.println("\n_____No Comparison Sort_____");
for(int trial = 1; trial <= 10; trial++)
{
long start = System.nanoTime();
NoComparisonSort(randNum, 0, randNum.length - 1);
long end = System.nanoTime();
long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
total = total + time;
if(time < min)
{
min = time;
}
if(time > max)
{
max = time;
}
}
System.out.println("The fastest time: " + min + " nanoseconds");
System.out.println("The slowest time: " + max + " nanoseconds");
System.out.println("The average time: " + (total/10) + " nanoseconds");
}
public static int[] SelectionSort(int num[])
{
int i, j, first, temp;
for (i = num.length - 1; i > 0; i-- )
{
first = 0;
for(j = 1; j <= i; j ++)
{
if(num[j] < num[first] )
first = j;
}
temp = num[first];
num[first] = num[i];
num[i] = temp;
}
return num;
}
public static void InsertionSort(int [] num)
{
int j;
int key;
int i;
for (j = 1; j < num.length; j++)
{
key = num[j];
for(i = j - 1; (i >= 0) && (num[ i ] < key); i--)
{
num[i+1] = num[i];
}
num[i+1] = key;
}
}
public static void BubbleSort(int [] num)
{
int j;
boolean flag = true;
int temp;
while (flag)
{
flag = false;
for(j = 0; j < num.length -1; j++)
{
if (num[j] < num[j+1])
{
temp = num[j];
num[j] = num[j+1];
num[j+1] = temp;
flag = true;
}
}
}
}
public static void QuickSort(int[] num, int low, int high)
{
if (num == null || num.length == 0)
return;
if (low >= high)
return;
int middle = low + (high - low) / 2;
int pivot = num[middle];
int i = low, j = high;
while (i <= j) {
while (num[i] < pivot)
{
i++;
}
while (num[j] > pivot)
{
j--;
}
if (i <= j)
{
int temp = num[i];
num[i] = num[j];
num[j] = temp;
i++;
j--;
}
}
if (low < j)
QuickSort(num, low, j);
if (high > i)
QuickSort(num, i, high);
}
public static void MergeSort(int[] array)
{
if (array.length > 1)
{
int[] left = leftHalf(array);
int[] right = rightHalf(array);
MergeSort(left);
MergeSort(right);
merge(array, left, right);
}
}
public static int[] leftHalf(int[] array)
{
int size1 = array.length / 2;
int[] left = new int[size1];
for (int i = 0; i < size1; i++)
{
left[i] = array[i];
}
return left;
}
public static int[] rightHalf(int[] array)
{
int size1 = array.length / 2;
int size2 = array.length - size1;
int[] right = new int[size2];
for (int i = 0; i < size2; i++)
{
right[i] = array[i + size1];
}
return right;
}
public static void merge(int[] result, int[] left, int[] right)
{
int i1 = 0;
int i2 = 0;
for (int i = 0; i < result.length; i++)
{
if (i2 >= right.length || (i1 < left.length && left[i1] <= right[i2]))
{
result[i] = left[i1];
i1++;
}
else
{
result[i] = right[i2];
i2++;
}
}
}
public static void NoComparisonSort(int[] a, int low, int high)
{
int[] counts = new int[high - low + 1];
for (int x : a)
counts[x - low]++;
int current = 0;
for (int i = 0; i < counts.length; i++)
{
Arrays.fill(a, current, current + counts[i], i + low);
current += counts[i];
}
}
}
The output shows as: _____Selection Sort_____ The fastest time: 3307 nanoseconds The slowest time: 7117 nanoseconds The average time: 6399 nanoseconds
_____Insertion Sort_____ The fastest time: 0 nanoseconds The slowest time: 7117 nanoseconds The average time: 6399 nanoseconds
_____Bubble Sort_____ The fastest time: 0 nanoseconds The slowest time: 7117 nanoseconds The average time: 6400 nanoseconds
_____Merge Sort_____ The fastest time: 0 nanoseconds The slowest time: 7117 nanoseconds The average time: 6412 nanoseconds
_____Quick Sort_____ The fastest time: 0 nanoseconds The slowest time: 7117 nanoseconds The average time: 6416 nanoseconds
_____No Comparison Sort_____ The fastest time: 0 nanoseconds The slowest time: 7117 nanoseconds The average time: 6419 nanoseconds
Aucun commentaire:
Enregistrer un commentaire