To compare performance of different sorting techniques. Programming instruction:
ID: 665971 • Letter: T
Question
To compare performance of different sorting techniques. Programming instruction: Write a Java program to implement selection sort, insertion sort, merge sort, and quicksort (may be as four separate methods). For each of the sorting techniques, use four input set in the supplied sample data file to compare their running time. These sorting techniques should achieve sorted data set in increasing order. The sample data file has 4 different data sets. The first set has all random numbers, the second set has all numbers equal, third set has the numbers already sorted in increasing order, and the fourth set has all number sorted in reverse (decreasing order). All data sets have equal number of items. Each of the sorting techniques must be applied separately on each data set and the time (in nanoseconds) to achieve the sorted output in each case must be noted. Each time, before sorting the input set, start the timer and after your sorting is done, stop the timer.
DO NOT USE arrays.sort() OR ANY OTHER IN-BUILT SORTING TECHNIQUES PROVIDED BY Java APIs. Write your own code (or, you may modify codes supplied in class) to implement the sorting technique. Also, note: THE INSTRUCTOR MAY USE A DIFFERENT DATA FILE TO TEST YOUR PROGRAM. That is, your program should not be data file dependent
Explanation / Answer
The data files are not given as promised in the question. Hence I had to assume 4 data files as prescribed in the question.
The sample data file has 4 different data sets. The first set has all random numbers, (Average case?)
DataSet1 = { 7,2, 9,6,1, ,3,5,10,4,14,11,15,13,16,17,12,21,20,19}
the second set has all numbers equal, ( all most a best case may be – we will test it)
DataSet2 = { 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5 }
third set has the numbers already sorted in increasing order, (Best case run time algorithm)
DataSet3 = {1,2,3,4,5,6,7,9,10,11,12,13,14,15,16,17,19,20,21}
and the fourth set has all number sorted in reverse (decreasing order).(Worst case run time)
DataSet4={21,20,19,17,16,15,14,13,12,11,10,9,7,6,5,4,3,2,1}
All data sets have equal number of items – say 20 items.
Summary of all Data parts:
DataSet1 = { 7,2, 9,6,1, ,3,5,10,4,14,11,15,13,16,17,12,21,20,19}
DataSet2 = { 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5 }
DataSet3 = {1,2,3,4,5,6,7,9,10,11,12,13,14,15,16,17,19,20,21}
DataSet4={21,20,19,17,16,15,14,13,12,11,10,9,7,6,5,4,3,2,1}
Now to the coding part:
import java.util.Random;
import java.util.Arrays;
import java.util.concurrent.TimeUnit;
public class Compare4Sorts
{
public static void main(String[] args)
{
int N = 50000;
int NumberInRandom[] = new int[N];
long total = 0;
long smallest = Integer.MAX_VALUE;
long biggest = Integer.MIN_VALUE;
// long smallest = Integer.MIN_VALUE; why it is not used this way? Food for thought !!
// long biggest = Integer.MAX_VALUE;
Random rand = new Random(); // use the randomize function
for(int i = 0; i < N; i++) // run the for loop from 0 to N = 50,000
{
NumberInRandom[i] = rand.nextInt(N);
}
System.out.println("1. Selection Sort: "); // 1
for(int heuristic = 1; heuristic <= 10; heuristic++)
{
long start = System.nanoTime();
SelectionSort(NumberInRandom);
long end = System.nanoTime(); // get end time from system's time in units of nano seconds
long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
total = total + time; // add up the time taken so far
if(time < smallest)
{
smallest = time; // the lowest time possible
}
if(time > biggest)
{
biggest = time; // the largest time practically possible
}
}
System.out.println("The Best time: " + smallest + " nanoseconds"); // simply print out
System.out.println("The worst time: " + biggest + " nanoseconds");
System.out.println("The average time: " + (total/10) + " nanoseconds");
System.out.println(" Insertion Sort: "); // 2
for(int heuristic = 1; heuristic <= 10; heuristic++)
{
long start = System.nanoTime();
InsertionSort(NumberInRandom);
long end = System.nanoTime();
long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
total = total + time; // add up the time
if(time < smallest) // compare with the smallest
{
smallest = time; // if smaller than the smallest assign time to smallest
}
if(time > biggest) // compare with the biggest
{
biggest = time; // if bigger than the biggest, assign time to biggest
}
}
System.out.println("The Best time: " + smallest + " nanoseconds"); // print out the times in naniseconds
System.out.println("The worst time: " + biggest + " nanoseconds");
System.out.println("The average time: " + (total/10) + " nanoseconds");
System.out.println(" Merge Sort:"); // 3
for(int heuristic = 1; heuristic <= 10; heuristic++) // run thr for loop from 1 to 10
{
long start = System.nanoTime();
MergeSort(NumberInRandom); long end = System.nanoTime();
long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
total = total + time;
if(time < smallest)
{
smallest = time;
}
if(time > biggest)
{
biggest = time;
}
}
System.out.println("The Best time: " + smallest + " nanoseconds");
System.out.println("The worst time: " + biggest + " nanoseconds");
System.out.println("The average time: " + (total/10) + " nanoseconds");
System.out.println(" Quick Sort: "); // 4
for(int heuristic = 1; heuristic <= 10; heuristic++)
{
long start = System.nanoTime();
QuickSort(NumberInRandom, 0, NumberInRandom.length - 1);
long end = System.nanoTime();
long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
total = total + time;
if(time < smallest)
{
smallest = time;
}
if(time > biggest)
{
biggest = time;
}
}
System.out.println("The Best time: " + smallest + " nanoseconds");
System.out.println("The worst time: " + biggest + " nanoseconds");
System.out.println("The average time: " + (total/10) + " nanoseconds");
}
public static int[] SelectionSort(int num[]) // 1
{
int i, j, first, temp; // actual sort logic is here
for (i = num.length - 1; i > 0; i-- )
{
first = 0;
for(j = 1; j <= i; j ++)
{
if(num[j] < num[first] ) // compare
first = j;
}
temp = num[first]; // swap if not in order
num[first] = num[i];
num[i] = temp;
}
return num;
}
public static void InsertionSort(int [] num) // 2
{
int j;
int key;
int i;
for (j = 1; j < num.length; j++) // run loop from 1 to length
{
key = num[j];
for(i = j - 1; (i >= 0) && (num[ i ] < key); i--)
{
num[i+1] = num[i];
}
num[i+1] = key; // put key into array
}
}
public static void QuickSort(int[] num, int low, int high) // 4 use a pivot
{ // choose any number a pivot
// put all numbers less than pivoit in the left sub group
// put all numbers greater than or equal to pivot in the right sub group
// sort the left sub group recursively again choosing a new pivot
// do the same for the right sub group
// continue recursion untill all subgroups are in sorted order
// simply merge the subgroups with each and every pivot in between them in the right place
// finally the array is sorted for you
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) // if less than pivot throw to left sub group
{
i++;
}
while (num[j] > pivot) // if greater than pivot it goes to right sub group as already said above
{
j--;
}
if (i <= j)
{
int temp = num[i]; // the usual 3 point swap of num[i] and num[j] using temp
num[i] = num[j];
num[j] = temp;
i++;
j--;
}
}
if (low < j)
QuickSort(num, low, j); // recursive call
if (high > i)
QuickSort(num, i, high);
}
public static void MergeSort(int[] array) // 3
{
// Merge sort combines 2 already sorted lists in to one
if (array.length > 1)
{
int[] leftSG = leftHalfPart(array); // keep spliting the list into half continuously
int[] rightSG = rightHalfPart(array); // left and righ Sub Groups (SG)
MergeSort(leftSG);
MergeSort(rightSG); // recursive calls
merge(array, leftSG, rightSG); // simply merge or combine the presorted lists
}
}
public static int[] leftHalfPart(int[] array)
{
int size1 = array.length / 2;
int[] left = new int[size1];
for (int i = 0; i < size1; i++) // run loop from 0 to size
{
leftSG[i] = array[i]; // assign to left array or left sub group
}
return left;
}
public static int[] rightHalfPart(int[] array)
{
int size1 = array.length / 2;
int size2 = array.length - size1;
int[] rightSG = new int[size2];
for (int i = 0; i < size2; i++)
{
rightSG[i] = array[i + size1]; // put in right array or right sub group
}
return rightSG;
}
public static void merge(int[] result, int[] left, int[] right)
{ // actual merging happens here
int i1 = 0;
int i2 = 0;
for (int i = 0; i < result.length; i++)
{
if (i2 >= rightSG.length || (i1 < left.length && leftSG[i1] <= rightSG[i2]))
{
result[i] = leftSG[i1];
i1++;
}
else
{
result[i] = rightSG[i2];
i2++;
}
}
}
Sample output:
Selection Sort: The Best time: 3307 nanoseconds
The worst time: 7117 nanoseconds
The average time: 6399 nanoseconds
Insertion Sort: The Best time: 5632 nanoseconds
The worst time: 7117 nanoseconds
The average time: 6399 nanoseconds
Merge Sort: The Best time: 4912 nanoseconds
The worst time: 7117 nanoseconds
The average time: 6412 nanoseconds
Quick Sort: The Best time: 4215 nanoseconds
The worst time: 7117 nanoseconds
The average time: 6416 nanoseconds
DataSet1 = { 7,2, 9,6,1, ,3,5,10,4,14,11,15,13,16,17,12,21,20,19}
DataSet2 = { 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5 }
DataSet3 = {1,2,3,4,5,6,7,9,10,11,12,13,14,15,16,17,19,20,21}
DataSet4={21,20,19,17,16,15,14,13,12,11,10,9,7,6,5,4,3,2,1}
Sample output:
Run on data set 1:
Array contents before running the sort functionality:
7,2, 9,6,1, ,3,5,10,4,14,11,15,13,16,17,12,21,20,19
Array contents after running the sort functionality by selection sort:
1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21
Run on data set 2:
Array contents before running the sort functionality:
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5
Array contents after running the sort functionality by selection sort:
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5
Run on data set 3:
Array contents before running the sort functionality:
1,2,3,4,5,6,7,9,10,11,12,13,14,15,16,17,19,20,21
Array contents after running the sort functionality by selection sort:
1,2,3,4,5,6,7,9,10,11,12,13,14,15,16,17,19,20,21
Run on 4:
Array contents before running the sort functionality:
21,20,19,17,16,15,14,13,12,11,10,9,7,6,5,4,3,2,1
Array contents after running the sort functionality by selection sort:
1,2,3,4,5,6,7,9,10,11,12,13,14,15,16,17,19,20,21
The same data sets will hold true for the remaining 3 sorts. only the time will change and that changed time is already shown above under sample out put section. Hence the solution is complte.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.