In this project you are asked to implement the following four sorting algorithms
ID: 652987 • Letter: I
Question
In this project you are asked to implement the following four sorting algorithms: Insertion Sort, Quick Sort, Merge Sort, and Heap sort. To test your program, generate a file of 20,000 random numbers, and then use the System.currentTimeMillis() method to measure the execution time of each algorithm implemented in Java.
Remarks:
You need to implement your own version of the sorting algorithms, and cannot use existing programs provided by Java library.
Please submit your program along with the measured execution time for each sorting alogrithm.
Explanation / Answer
package com.testing;
import com.sorting.InsertionSort;
import com.sorting.MergeSort;
import com.sorting.ModifiedMergeSort;
import com.sorting.RandomizedQuickSort;
public class Main
{
private static final int R = 50; // # of tests
private static int N = 0; // Input size
private static int[] array; // Tests array
private static int[] temp; // Tests array
private static long InsertionSort_best = -1;
private static long InsertionSort_worst = -1;
private static double InsertionSort_average = -1.0;
private static long MergeSort_best = -1;
private static long MergeSort_worst = -1;
private static double MergeSort_average = -1.0;
private static long ModifiedMergeSort_V3_best = -1;
private static long ModifiedMergeSort_V3_worst = -1;
private static double ModifiedMergeSort_V3_average = -1.0;
private static long ModifiedMergeSort_V4_best = -1;
private static long ModifiedMergeSort_V4_worst = -1;
private static double ModifiedMergeSort_V4_average = -1.0;
private static long ModifiedMergeSort_V5_best = -1;
private static long ModifiedMergeSort_V5_worst = -1;
private static double ModifiedMergeSort_V5_average = -1.0;
private static long RandomizedQuickSort_best = -1;
private static long RandomizedQuickSort_worst = -1;
private static double RandomizedQuickSort_average = -1.0;
public static void main(String args[])
{
StringBuilder InsertionSort_text = new StringBuilder(
"Version 1 - Insertion Sort: Run-Times over 50 test runs ");
StringBuilder MergeSort_text = new StringBuilder(
"Version 2 - Merge Sort: Run-Times over 50 test runs ");
StringBuilder ModifiedMergeSort_V3_text = new StringBuilder(
"Version 3 - Merge Sort and Insertion Sort on 15 elements: Run-Times over 50 test runs ");
StringBuilder ModifiedMergeSort_V4_text = new StringBuilder(
"Version 4 - Merge Sort and Insertion Sort on 30 elements: Run-Times over 50 test runs ");
StringBuilder ModifiedMergeSort_V5_text = new StringBuilder(
"Version 5 - Merge Sort and Insertion Sort on 45 elements: Run-Times over 50 test runs ");
StringBuilder RandomizedQuickSort_text = new StringBuilder(
"Version 6 - Quick Sort: Run-Times over 50 test runs ");
InsertionSort_text.append("Input Size "
+ "Best-Case Worst-Case Average-Case ");
MergeSort_text.append("Input Size "
+ "Best-Case Worst-Case Average-Case ");
ModifiedMergeSort_V3_text.append("Input Size "
+ "Best-Case Worst-Case Average-Case ");
ModifiedMergeSort_V4_text.append("Input Size "
+ "Best-Case Worst-Case Average-Case ");
ModifiedMergeSort_V5_text.append("Input Size "
+ "Best-Case Worst-Case Average-Case ");
RandomizedQuickSort_text.append("Input Size "
+ "Best-Case Worst-Case Average-Case ");
// Case N = 10000
N = 10000;
fillArray();
testing_InsertionSort();
testing_MergeSort();
testing_ModifiedMergeSort(15);
testing_ModifiedMergeSort(30);
testing_ModifiedMergeSort(45);
testing_RandomizedQuickSort();
InsertionSort_text.append("N = " + N + " " + InsertionSort_best
+ " " + InsertionSort_worst + " "
+ InsertionSort_average + " ");
MergeSort_text.append("N = " + N + " " + MergeSort_best
+ " " + MergeSort_worst + " "
+ MergeSort_average + " ");
ModifiedMergeSort_V3_text.append("N = " + N + " " + ModifiedMergeSort_V3_best
+ " " + ModifiedMergeSort_V3_worst + " "
+ ModifiedMergeSort_V3_average + " ");
ModifiedMergeSort_V4_text.append("N = " + N + " " + ModifiedMergeSort_V4_best
+ " " + ModifiedMergeSort_V4_worst + " "
+ ModifiedMergeSort_V4_average + " ");
ModifiedMergeSort_V5_text.append("N = " + N + " " + ModifiedMergeSort_V5_best
+ " " + ModifiedMergeSort_V5_worst + " "
+ ModifiedMergeSort_V5_average + " ");
RandomizedQuickSort_text.append("N = " + N + " " + RandomizedQuickSort_best
+ " " + RandomizedQuickSort_worst + " "
+ RandomizedQuickSort_average + " ");
// Case N = 20000
N = 20000;
fillArray();
testing_InsertionSort();
testing_MergeSort();
testing_ModifiedMergeSort(15);
testing_ModifiedMergeSort(30);
testing_ModifiedMergeSort(45);
testing_RandomizedQuickSort();
InsertionSort_text.append("N = " + N + " " + InsertionSort_best
+ " " + InsertionSort_worst + " "
+ InsertionSort_average + " ");
MergeSort_text.append("N = " + N + " " + MergeSort_best
+ " " + MergeSort_worst + " "
+ MergeSort_average + " ");
ModifiedMergeSort_V3_text.append("N = " + N + " " + ModifiedMergeSort_V3_best
+ " " + ModifiedMergeSort_V3_worst + " "
+ ModifiedMergeSort_V3_average + " ");
ModifiedMergeSort_V4_text.append("N = " + N + " " + ModifiedMergeSort_V4_best
+ " " + ModifiedMergeSort_V4_worst + " "
+ ModifiedMergeSort_V4_average + " ");
ModifiedMergeSort_V5_text.append("N = " + N + " " + ModifiedMergeSort_V5_best
+ " " + ModifiedMergeSort_V5_worst + " "
+ ModifiedMergeSort_V5_average + " ");
RandomizedQuickSort_text.append("N = " + N + " " + RandomizedQuickSort_best
+ " " + RandomizedQuickSort_worst + " "
+ RandomizedQuickSort_average + " ");
// Case N = 40000
N = 40000;
fillArray();
testing_InsertionSort();
testing_MergeSort();
testing_ModifiedMergeSort(15);
testing_ModifiedMergeSort(30);
testing_ModifiedMergeSort(45);
testing_RandomizedQuickSort();
InsertionSort_text.append("N = " + N + " " + InsertionSort_best
+ " " + InsertionSort_worst + " "
+ InsertionSort_average + " ");
MergeSort_text.append("N = " + N + " " + MergeSort_best
+ " " + MergeSort_worst + " "
+ MergeSort_average + " ");
ModifiedMergeSort_V3_text.append("N = " + N + " " + ModifiedMergeSort_V3_best
+ " " + ModifiedMergeSort_V3_worst + " "
+ ModifiedMergeSort_V3_average + " ");
ModifiedMergeSort_V4_text.append("N = " + N + " " + ModifiedMergeSort_V4_best
+ " " + ModifiedMergeSort_V4_worst + " "
+ ModifiedMergeSort_V4_average + " ");
ModifiedMergeSort_V5_text.append("N = " + N + " " + ModifiedMergeSort_V5_best
+ " " + ModifiedMergeSort_V5_worst + " "
+ ModifiedMergeSort_V5_average + " ");
RandomizedQuickSort_text.append("N = " + N + " " + RandomizedQuickSort_best
+ " " + RandomizedQuickSort_worst + " "
+ RandomizedQuickSort_average + " ");
System.out.println(InsertionSort_text);
System.out.println(MergeSort_text);
System.out.println(ModifiedMergeSort_V3_text);
System.out.println(ModifiedMergeSort_V4_text);
System.out.println(ModifiedMergeSort_V5_text);
System.out.println(RandomizedQuickSort_text);
}
private static void fillArray()
{
// (re)creating the array
array = new int[N];
// filling the array with random numbers
// using for-loop and the given random generator instruction
for(int i = 0; i < array.length; i++)
{
array[i] = (int)(1 + Math.random() * (N-0+1));
}
}
private static void testing_InsertionSort()
{
// run-times arrays
long [] run_times = new long[R];
// start/finish times
long start;
long finish;
for(int i = 0; i < R; i++) {
copyArray();
// recording start time
start = System.currentTimeMillis();
// testing the algorithm
InsertionSort.sort(temp);
// recording finish time
finish = System.currentTimeMillis();
run_times[i] = finish-start;
}
InsertionSort_best = findMin(run_times);
InsertionSort_worst = findMax(run_times);
InsertionSort_average = findAverage(run_times);
}
private static void testing_MergeSort()
{
// run-times arrays
long [] run_times = new long[R];
// start/finish times
long start;
long finish;
for(int i = 0; i < R; i++) {
copyArray();
// recording start time
start = System.currentTimeMillis();
// testing the algorithm
MergeSort.sort(temp);
// recording finish time
finish = System.currentTimeMillis();
run_times[i] = finish-start;
}
MergeSort_best = findMin(run_times);
MergeSort_worst = findMax(run_times);
MergeSort_average = findAverage(run_times);
}
private static void testing_ModifiedMergeSort(int bound)
{
// run-times arrays
long [] run_times = new long[R];
// setting the bound
ModifiedMergeSort.bound = bound;
// start/finish times
long start;
long finish;
for(int i = 0; i < R; i++)
{
copyArray();
// recording start time
start = System.currentTimeMillis();
// testing the algorithm
ModifiedMergeSort.sort(temp);
// recording finish time
finish = System.currentTimeMillis();
run_times[i] = finish-start;
}
if(bound == 15)
{
ModifiedMergeSort_V3_best = findMin(run_times);
ModifiedMergeSort_V3_worst = findMax(run_times);
ModifiedMergeSort_V3_average = findAverage(run_times);
}
if(bound == 30)
{
ModifiedMergeSort_V4_best = findMin(run_times);
ModifiedMergeSort_V4_worst = findMax(run_times);
ModifiedMergeSort_V4_average = findAverage(run_times);
}
if(bound == 45)
{
ModifiedMergeSort_V5_best = findMin(run_times);
ModifiedMergeSort_V5_worst = findMax(run_times);
ModifiedMergeSort_V5_average = findAverage(run_times);
}
}
private static void testing_RandomizedQuickSort()
{
// run-times arrays
long [] run_times = new long[R];
// start/finish times
long start;
long finish;
for(int i = 0; i < R; i++)
{
copyArray();
// recording start time
start = System.currentTimeMillis();
// testing the algorithm
RandomizedQuickSort.sort(temp);
// recording finish time
finish = System.currentTimeMillis();
run_times[i] = finish-start;
}
RandomizedQuickSort_best = findMin(run_times);
RandomizedQuickSort_worst = findMax(run_times);
RandomizedQuickSort_average = findAverage(run_times);
}
private static long findMax(long[] times)
{
long max = times[0];
for(int i = 1; i < times.length; i++)
{
if(max < times[i])
{
max = times[i];
}
}
return max;
}
private static long findMin(long[] times)
{
long min = times[0];
for(int i = 1; i < times.length; i++)
{
if(min > times[i])
{
min = times[i];
}
}
return min;
}
private static double findAverage(long[] times)
{
long sum = 0;
double avg;
for(int i = 0; i < times.length; i++)
{
sum += times[i];
}
avg = (double)sum/(double)times.length;
return avg;
}
private static void copyArray()
{
temp = new int[N];
System.arraycopy(array, 0, temp, 0, array.length);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.