write a java program that calculates the running time of variouos sorting algori
ID: 3686655 • Letter: W
Question
write a java program that calculates the running time of variouos sorting algorithms like heap sort, in-place quick sort and merge sort for 10,000 randomly generated integer no.
Since you are using random numbers, you need to repeat your experiments 10 times to be able to compute the average running time. So you are required to generate 10,000 integers, and compute the minimum, maxi and avge time required to sort the data. Your generated random data should be between 0 to 100,000.
Hint :
Heap sort, in-place quick sort and merge sort algorithms are available in the book and the companion website of the book.
You are NOT required to implement the algorithm with a generic type. It is enough for this assignment that your sorting algorithms work for integer data only.
Use the following code to compute the running time:
long startTIme = System.currentTimeMillis();
long endTime = System.currentTimeMillis();
long elapsed = endTime - startTime;
Please provide a working java code, would appreciate if you can attach the .java file here, Thanks!
Explanation / Answer
package firstweek2;
import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
public class Sorts {
static int SIZE = 10000;
static int[] values;
static void initValues() {
Random rand = new Random();
for (int index = 0; index < SIZE; index++)
values[index] = rand.nextInt(SIZE+1); // range 0 t0 10000
}
static public void swap(int index1, int index2)
// Precondition: index1 and index2 are >= 0 and < SIZE.
//
// Swaps the integers at locations index1 and index2 of the values array.
{
int temp = values[index1];
values[index1] = values[index2];
values[index2] = temp;
}
static public void printValues()
// Prints all the values integers.
{
int value;
DecimalFormat fmt = new DecimalFormat("00");
System.out.println("The values array is:");
for (int index = 0; index < SIZE; index++) {
value = values[index];
if (((index + 1) % 10) == 0)
System.out.println(fmt.format(value));
else
System.out.print(fmt.format(value) + " ");
}
System.out.println();
}
// ///////////////////////////////////////////////////////////////
//
// Merge Sort
static void merge(int leftFirst, int leftLast, int rightFirst, int rightLast)
// Preconditions: values[leftFirst]..values[leftLast] are sorted.
// values[rightFirst]..values[rightLast] are sorted.
//
// Sorts values[leftFirst]..values[rightLast] by merging the two subarrays.
{
int[] tempArray = new int[SIZE];
int index = leftFirst;
int saveFirst = leftFirst; // to remember where to copy back
while ((leftFirst <= leftLast) && (rightFirst <= rightLast)) {
if (values[leftFirst] < values[rightFirst]) {
tempArray[index] = values[leftFirst];
leftFirst++;
} else {
tempArray[index] = values[rightFirst];
rightFirst++;
}
index++;
}
while (leftFirst <= leftLast)
// Copy remaining items from left half.
{
tempArray[index] = values[leftFirst];
leftFirst++;
index++;
}
while (rightFirst <= rightLast)
// Copy remaining items from right half.
{
tempArray[index] = values[rightFirst];
rightFirst++;
index++;
}
for (index = saveFirst; index <= rightLast; index++)
values[index] = tempArray[index];
}
static void mergeSort(int first, int last)
// Sorts the values array using the merge sort algorithm.
{
if (first < last) {
int middle = (first + last) / 2;
mergeSort(first, middle);
mergeSort(middle + 1, last);
merge(first, middle, middle + 1, last);
}
}
// ///////////////////////////////////////////////////////////////
//
// Quick Sort
static int split(int first, int last) {
int splitVal = values[first];
int saveF = first;
boolean onCorrectSide;
first++;
do {
> while (onCorrectSide)
// move first toward last
if (values[first] > splitVal)
> else {
first++;
<= last);
}
<= last);
while (onCorrectSide)
// move last toward first
if (values[last] <= splitVal)
> else {
last--;
<= last);
}
if (first < last) {
swap(first, last);
first++;
last--;
}
} while (first <= last);
swap(saveF, last);
return last;
}
static void quickSort(int first, int last) {
if (first < last) {
int splitPoint;
splitPoint = split(first, last);
// values[first]..values[splitPoint - 1] <= splitVal
// values[splitPoint] = splitVal
// values[splitPoint+1]..values[last] > splitVal
quickSort(first, splitPoint - 1);
quickSort(splitPoint + 1, last);
}
}
// ///////////////////////////////////////////////////////////////
//
// Heap Sort
static int newHole(int hole, int lastIndex, int item)
// If either child of hole is larger than item this returns the index
// of the larger child; otherwise it returns the index of hole.
{
int left = (hole * 2) + 1;
int right = (hole * 2) + 2;
if (left > lastIndex)
// hole has no children
return hole;
else if (left == lastIndex)
// hole has left child only
if (item < values[left])
// item < left child
return left;
else
// item >= left child
return hole;
else
// hole has two children
if (values[left] < values[right])
// left child < right child
if (values[right] <= item)
// right child <= item
return hole;
else
// item < right child
return right;
else
// left child >= right child
if (values[left] <= item)
// left child <= item
return hole;
else
// item < left child
return left;
}
static void reheapDown(int item, int root, int lastIndex)
// Precondition: Current root position is "empty".
//
// Inserts item into the tree and ensures shape and order properties.
{
int hole = root; // current index of hole
int newhole; // index where hole should move to
newhole = newHole(hole, lastIndex, item); // find next hole
while (newhole != hole) {
values[hole] = values[newhole]; // move value up
hole = newhole; // move hole down
newhole = newHole(hole, lastIndex, item); // find next hole
}
values[hole] = item; // fill in the final hole
}
static void heapSort()
// Sorts the values array using the heap sort algorithm.
{
int index;
// Convert the array of values into a heap.
for (index = SIZE / 2 - 1; index >= 0; index--)
reheapDown(values[index], index, SIZE - 1);
// Sort the array.
for (index = SIZE - 1; index >= 1; index--) {
swap(0, index);
reheapDown(values[0], 0, index - 1);
}
}
// ///////////////////////////////////////////////////////////////
//
// Main
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
values = new int[SIZE];
initValues(); // filling array with random integer
// getting a copy of this
int original[] = Arrays.copyOf(values, SIZE);
if (SIZE <= 100) // size is less than 101, print it
printValues();
System.out.println();
long startTime = 0;
long endTIme = 0;
long total = 0;
// calling Merge sort
System.out.println("Merge Sort: ");
for(int i=0; i<10; i++){
// copy original array value into values array
values = Arrays.copyOf(original, SIZE);
startTime = System.currentTimeMillis();
mergeSort(0, SIZE-1);
endTIme = System.currentTimeMillis();
total = total + (endTIme-startTime);
}
System.out.println("Average Time taken: " + total/10);
System.out.println();
total = 0;
// calling Quick sort
System.out.println("Quick Sort: ");
for(int i=0; i<10; i++){
// copy original array value into values array
values = Arrays.copyOf(original, SIZE);
startTime = System.currentTimeMillis();
quickSort(0, SIZE-1);
endTIme = System.currentTimeMillis();
total = total + (endTIme-startTime);
}
System.out.println("Average Time taken: " + total/10);
System.out.println();
total = 0;
// calling Heap sort
System.out.println("Heap Sort: ");
for(int i=0; i<10; i++){
// copy original array value into values array
values = Arrays.copyOf(original, SIZE);
startTime = System.currentTimeMillis();
heapSort();
endTIme = System.currentTimeMillis();
total = total + (endTIme-startTime);
}
System.out.println("Average Time taken: " + total/10);
System.out.println();
System.out.println();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.