( Execution time for sorting ) Write a program that obtains the execution time o

Question

(Execution time for sorting) Write a program that obtains the execution time of

selection sort, bubble sort, merge sort, quick sort, heap sort, and radix sort for

input size 50,000, 100,000, 150,000, 200,000, 250,000, and 300,000. The pro-

gram should create data randomly and print a table like this:

(Hint: You can use the following code template to obtain the execution time.)

First Correct Answer Will Be Rated! :)

Array Selection Insertion Bubble Merge Quickt Heap Radix size Sort Sort Sort Sort Sort Sort Sort 10000 38 33 107 10 20000 142 121 463 13 30000 121 91 1073 40000 217 161 1924 50000 330 255 3038 11 60000 479 374 4403 18 14 x 033576 L r 11 do as pt477934 ar2 eo HS k rt 22 tt222356 CO is et346918 gr 11 ro eS et733483 r06723 b 014090 bS 113 nt31-154 0 r329657 "Z O 123 tS nt82-709 0 r342-37 "Z O 11234 tS ye000000 z000000 r*z 0 0 0 0 0 0 rs000000 123456

Explanation / Answer

import java.security.SecureRandom;
import java.util.ArrayList;
public class SortingTimeCalc {
public static void main(String[] args) {
// TODO Auto-generated method stub
SecureRandom Random=new SecureRandom();
  
for(int i = 1; i <= 6; i++)
{
ArrayList <Integer> RandomArray=new ArrayList<Integer>();
RandomArray=RandomNumber(10000 * i);
System.out.printf("%8d ", 10000*i);
TimeConsumeSelection(RandomArray);
RandomArray=RandomNumber(10000 * i);
TimeConsumeInsertion(RandomArray);
RandomArray=RandomNumber(10000 * i);
TimeConsumeMerge(RandomArray);
RandomArray=RandomNumber(10000 * i);
TimeConsumeQuick(RandomArray);
System.out.println();
}
/*ArrayList <Integer> RandomArray50=new ArrayList<Integer>();
RandomArray50=RandomNumber(10);
ArrayList <Integer> RandomArray500=new ArrayList<Integer>();
RandomArray500=RandomNumber(500);
ArrayList <Integer> RandomArray5000=new ArrayList<Integer>();
RandomArray5000=RandomNumber(5000);
System.out.println("50 numbers:");
TimeConsumeSelection(RandomArray50);
System.out.println("500 numbers:");
TimeConsumeSelection(RandomArray500);
System.out.println("5000 numbers:");
TimeConsumeSelection(RandomArray5000);
  
RandomArray50=RandomNumber(10);
RandomArray500=RandomNumber(500);
RandomArray5000=RandomNumber(5000);
System.out.println("50 numbers:");
TimeConsumeInsertion(RandomArray50);
System.out.println("500 numbers:");
TimeConsumeInsertion(RandomArray500);
System.out.println("5000 numbers:");
TimeConsumeInsertion(RandomArray5000);
  
RandomArray50=RandomNumber(10);
RandomArray500=RandomNumber(500);
RandomArray5000=RandomNumber(5000);
System.out.println("50 numbers:");
TimeConsumeMerge(RandomArray50);
System.out.println("500 numbers:");
TimeConsumeMerge(RandomArray500);
System.out.println("5000 numbers:");
TimeConsumeMerge(RandomArray5000);
  
RandomArray50=RandomNumber(10);
RandomArray500=RandomNumber(500);
RandomArray5000=RandomNumber(5000);
System.out.println("50 numbers:");
TimeConsumeQuick(RandomArray50);
System.out.println("500 numbers:");
TimeConsumeQuick(RandomArray500);
System.out.println("5000 numbers:");
TimeConsumeQuick(RandomArray5000);*/
  
}
public static void TimeConsumeSelection (ArrayList<Integer> RandomArray)
{
long startTime=System.nanoTime();
SelectionSort(RandomArray);
long endTime=System.nanoTime();
long totalTime=(endTime-startTime)/1000;
//System.out.println("SelectionSort took "+totalTime+" miliseconds to sort numbers");
System.out.printf("%8d ", totalTime);
}
  
public static void TimeConsumeInsertion (ArrayList<Integer> RandomArray)
{
long startTime=System.nanoTime();
InsertionSort(RandomArray);
long endTime=System.nanoTime();
long totalTime=(endTime-startTime)/1000;
//System.out.println("InsertionSort took "+totalTime+" miliseconds to sort numbers");
System.out.printf("%8d ", totalTime);
}
  
public static void TimeConsumeMerge (ArrayList<Integer> RandomArray)
{
long startTime=System.nanoTime();
MergeSort(RandomArray);
long endTime=System.nanoTime();
long totalTime=(endTime-startTime)/1000;
//System.out.println("MergeSort took "+totalTime+" miliseconds to sort numbers");
System.out.printf("%8d ", totalTime);
}
  
public static void TimeConsumeQuick (ArrayList<Integer> RandomArray)
{
long startTime=System.nanoTime();
QuickSort(RandomArray);
long endTime=System.nanoTime();
long totalTime=(endTime-startTime)/1000;
//System.out.println("QuickSort took "+totalTime+" miliseconds to sort numbers");
System.out.printf("%8d ", totalTime);
}
  
public static ArrayList<Integer> RandomNumber(int num)
{
SecureRandom Random=new SecureRandom();
ArrayList <Integer> RandomArray=new ArrayList<Integer>();
for (int i=0;i<num;i++)
{
int number=Random.nextInt(5001)-2500;
if(!RandomArray.contains(number))
RandomArray.add(number);
}
// System.out.println("Original array");
// for (int j=0;j<num;j++)
// {
// System.out.print(RandomArray.get(j)+" ");
// }
// System.out.println();
return RandomArray;
}
public static void SelectionSort(ArrayList<Integer> list)
{ int min;
int temp;
for(int i = 0; i < list.size() - 1; i++) {
min = i;
for(int j = i + 1; j < list.size(); j++)
if( list.get(j) < list.get(min) )
min = j;
temp = list.get(i);
list.set(i,list.get(min));
list.set(min,temp);
}
  
//System.out.println("The sorted array: ");
// for (int k=0;k<list.size();k++)
// {
// System.out.print(list.get(k)+" ");
// }
// System.out.println();
}
public static void InsertionSort(ArrayList<Integer> list){
for(int i = 1; i < list.size(); i++)
{
int temp = list.get(i);
int j;
for(j = i-1; j >= 0 && list.get(j) > temp; j--)
list.set(j+1, list.get(j));
list.set(j+1, temp);
}
}
  
public static ArrayList<Integer> MergeSort(ArrayList<Integer> list) {
ArrayList<Integer> left = new ArrayList<Integer>();
ArrayList<Integer> right = new ArrayList<Integer>();
int center;

if (list.size() == 1) {
return list;
} else {
center = list.size()/2;
// copy the left half of list into the left.
for (int i=0; i<center; i++) {
left.add(list.get(i));
}

//copy the right half of list into the new arraylist.
for (int i=center; i<list.size(); i++) {
right.add(list.get(i));
}

// Sort the left and right halves of the arraylist.
left = MergeSort(left);
right = MergeSort(right);

// Merge the results back together.
merge(left, right, list);
}
return list;
}
private static void merge(ArrayList<Integer> left, ArrayList<Integer> right, ArrayList<Integer> list) {
int leftIndex = 0;
int rightIndex = 0;
int listIndex = 0;

// As long as neither the left nor the right ArrayList has
// been used up, keep taking the smaller of left.get(leftIndex)
// or right.get(rightIndex) and adding it at both.get(bothIndex).
while (leftIndex < left.size() && rightIndex < right.size()) {
if ( (left.get(leftIndex).compareTo(right.get(rightIndex))) < 0) {
list.set(listIndex, left.get(leftIndex));
leftIndex++;
} else {
list.set(listIndex, right.get(rightIndex));
rightIndex++;
}
listIndex++;
}

ArrayList<Integer> rest;
int restIndex;
if (leftIndex >= left.size()) {
// The left ArrayList has been use up...
rest = right;
restIndex = rightIndex;
} else {
// The right ArrayList has been used up...
rest = left;
restIndex = leftIndex;
}

// Copy the rest of whichever ArrayList (left or right) was not used up.
for (int i=restIndex; i<rest.size(); i++) {
list.set(listIndex, rest.get(i));
listIndex++;
}
}

public static void QuickSort( ArrayList<Integer> list )
{
quickSort( list, 0, list.size()-1 );
}
public static void quickSort( ArrayList<Integer> list, int lo, int hi )
{
int pivot;

if( lo >= hi )
return;

pivot = partition( list, lo, hi );
quickSort( list, lo, pivot-1 );
quickSort( list, pivot+1, hi );
}
public static int partition( ArrayList<Integer> list, int lo, int hi )
{
int pivotVal = list.get( lo );
int right = hi;
int left = lo + 1;

while( left <= right )
{
// move left toward the right until it gets to the first value
// greater than pivot
while( left <= hi && list.get(left) <= pivotVal )
left++;

// move right toward the left until it gets to the first value
// less than or equal to the pivot
while( list.get(right) > pivotVal )
right--;

// if left and right haven't crossed, swap the elements and increment/decrement
// left and right
if( left < right )
{
swap( list, left, right );
left++;
right--;
}
}

// the pivit position is where right points right now, so swap the pivot value there
swap( list, lo, right );
  
// right contains the pivot value
return right;
}

/**
* Swaps two elements of an ArrayList
*/
private static void swap( ArrayList<Integer> list, int i, int j )
{
int temp = list.get(i);
list.set( i, list.get(j) );
list.set( j, temp );
}   
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.