Write a Java program that obtains the execution time of selection sort, insertio

Question

Write a Java program that obtains the execution time of selection sort, insertion sort, bubble sort, merge sort, quick sort, and radix sort. Your program should test all sort methods for input sizes of 10000, 20000, 30000, 40000, 50000, and 60000. The selection sort, bubble sort, and radix sort should also be tested for input sizes 100000 and 200000. Your program should create the data that is sorted from randomly generated integers and should output the results in a table identical to the one below. Pay particular attention to how the headings and results are aligned left justified. The number of spaces between columns is not specific, but there should be enough room for each column to be clearly identified. Make the code simple and short not too long.

To obtain exceution time use the following code template:

long startTime = System.currentTimeMillis();

perform the task;

long endTime = System.currentTimeMillis();

long executionTime = endTime - startTime;

Explanation / Answer

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class timesel {
public static void main(String args[])
{
System.out.println("|Array |Selection |Insertion |Bubble |Merge |Quick |Radix");
System.out.println("|Size |Sort |Sort |Sort |Sort |Sort |Sort ");
for (int size=10000; size <= 60000; size=size+10000)
{
  
int[] array = createArray(size); // generate random array
System.out.print("|"+size+" ");
long start = System.currentTimeMillis();
// sort array
SelSort(array);
long end = System.currentTimeMillis();
long time_in_ms = (end-start);
System.out.print("|"+time_in_ms+" ");
start = System.currentTimeMillis();
// sort array
InsertSort(array);
end = System.currentTimeMillis();
time_in_ms = (end-start);
System.out.print("|"+time_in_ms+" ");
start = System.currentTimeMillis();
// sort array
BubbleSort(array);
end = System.currentTimeMillis();
time_in_ms = (end-start);
System.out.print("|"+time_in_ms+" ");
start = System.currentTimeMillis();
// sort array
MergeSort(array,0,array.length);
end = System.currentTimeMillis();
time_in_ms = (end-start);
System.out.print("|"+time_in_ms+" ");
start = System.currentTimeMillis();
// sort array
QuickSort(array,0,array.length-1);
end = System.currentTimeMillis();
time_in_ms = (end-start);
System.out.print("|"+time_in_ms+" ");
start = System.currentTimeMillis();
// sort array
BubbleSort(array);
end = System.currentTimeMillis();
time_in_ms = (end-start);
System.out.print("|"+time_in_ms+" ");
System.out.println();
}
int[] array = createArray(100000);
System.out.print("|100000 ");
long start = System.currentTimeMillis();
// sort array
SelSort(array);
long end = System.currentTimeMillis();
long time_in_ms = (end-start);
System.out.print("|"+time_in_ms+" ");
System.out.print("|0 ");
start = System.currentTimeMillis();
// sort array
BubbleSort(array);
end = System.currentTimeMillis();
time_in_ms = (end-start);
System.out.print("|"+time_in_ms+" ");
System.out.print("|0 ");
System.out.print("|0 ");
start = System.currentTimeMillis();
// sort array
BubbleSort(array);
end = System.currentTimeMillis();
time_in_ms = (end-start);
System.out.print("|"+time_in_ms+" ");
System.out.println();
int[] array1 = createArray(200000);
System.out.print("|200000 ");
start = System.currentTimeMillis();
// sort array
SelSort(array1);
end = System.currentTimeMillis();
time_in_ms = (end-start);
System.out.print("|"+time_in_ms+" ");
System.out.print("|0 ");
start = System.currentTimeMillis();
// sort array
BubbleSort(array1);
end = System.currentTimeMillis();
time_in_ms = (end-start);
System.out.print("|"+time_in_ms+" ");
System.out.print("|0 ");
System.out.print("|0 ");
start = System.currentTimeMillis();
// sort array
BubbleSort(array1);
end = System.currentTimeMillis();
time_in_ms = (end-start);
System.out.print("|"+time_in_ms+" ");
System.out.println();
}

//function to create array with random values
private static int[] createArray(int size) {
int i;
//declare array
int a[] = new int[size];
Random r = new Random();
//insert random values
for(i=0;i<size;i++)
a[i]=r.nextInt();
return a;
}
//selection sort code
private static void SelSort(int[] r) {
for (int n=0; n<r.length; n++)
{
// find the minimum for posiition n
int mindex=n;
for (int i=n+1; i<r.length; i++)
{
if (r[i] < r[mindex])
{
mindex=i;
}
}
if (mindex != n)
{
// swap
int tmp = r[n];
r[n]=r[mindex];
r[mindex]=tmp;
}
}
}
//insertion sort code

private static void InsertSort(int[] array) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j-1;
while ( (i > -1) && ( array [i] > key ) ) {
array [i+1] = array [i];
i--;
}
array[i+1] = key;
}

}
//bubblesort code
private static void BubbleSort(int[] array) {
int n = array.length;
int temp = 0;

for(int i=0; i < n; i++){
for(int j=1; j < (n-i); j++){

if(array[j-1] > array[j]){
//swap the elements!
temp = array[j-1];
array[j-1] = array[j];
array[j] = temp;
}

}
}
}
//mergesort code
private static void MergeSort(int[] a, int low, int high)
{
int N = high - low;   
if (N <= 1)
return;
int mid = low + N/2;
// recursively sort
MergeSort(a, low, mid);
MergeSort(a, mid, high);
// merge two sorted subarrays
int[] temp = new int[N];
int i = low, j = mid;
for (int k = 0; k < N; k++)
{
if (i == mid)
temp[k] = a[j++];
else if (j == high)
temp[k] = a[i++];
else if (a[j]<a[i])
temp[k] = a[j++];
else
temp[k] = a[i++];
}
for (int k = 0; k < N; k++)
a[low + k] = temp[k];   
}
//quick sort code
private static void QuickSort(int arr[], int low, int high)
{
int i = low, j = high;
int temp;
int pivot = arr[(low + high) / 2];

/** partition **/
while (i <= j)
{
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j)
{
/** swap **/
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

i++;
j--;
}
}

/** recursively sort lower half **/
if (low < j)
QuickSort(arr, low, j);
/** recursively sort upper half **/
if (i < high)
QuickSort(arr, i, high);
}
//radix sort code
private static void RadixSort(int[] input) {
final int RADIX = 10;
// declare and initialize bucket[]
List<Integer>[] bucket = new ArrayList[RADIX];
for (int i = 0; i < bucket.length; i++) {
bucket[i] = new ArrayList<Integer>();
}

// sort
boolean maxLength = false;
int tmp = -1, placement = 1;
while (!maxLength) {
maxLength = true;
// split input between lists
for (Integer i : input) {
tmp = i / placement;
bucket[tmp % RADIX].add(i);
if (maxLength && tmp > 0) {
maxLength = false;
}
}
// empty lists into input array
int a = 0;
for (int b = 0; b < RADIX; b++) {
for (Integer i : bucket[b]) {
input[a++] = i;
}
bucket[b].clear();
}
// move to next digit
placement *= RADIX;
}

}
}

output:
|Array    |Selection    |Insertion    |Bubble    |Merge    |Quick    |Radix
|Size |Sort |Sort |Sort        |Sort        |Sort        |Sort   
|10000 |141 |0 |39 |0 |0 |31       
|20000 |500 |0 |109 |0 |0 |110       
|30000 |594 |0 |234 |0 |0        |250       
|40000 |1040 |0 |437        |16 |0        |437       
|50000 |1765 |0 |667 |0 |16        |663       
|60000 |2344 |0 |969        |0 |0        |975       
|100000 |6523        |0 |2694        |0 |0        |2713       
|200000 |26027        |0 |10905        |0 |0        |11027

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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