Write a program in Java that obtains the execution time of selection sort, inser
ID: 3691400 • Letter: W
Question
Write a program in Java 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. (Hint: You can use the code template below to obtain the execution time.) long startTime = System.currentTimeMillis(); perform the task; long endTime = System.currentTimeMillis(); long executionTime = endTime - startTime;
| Array | Selection | Insertion | Bubble | Merge | Quick | Radix
| Size | Sort | Sort | Sort | Sort | Sort | Sort
---------------------------------------------------------------------------------------------------------------------
| 10000 | 116 | 15 | 216 | 0 | 16 | 0
| 20000 | 419 | 65 | 847 | 0 | 20 | 2
| 30000 | 379 | 170 | 1319 | 0 | 15 | 0
| 40000 | 1604 | 303 | 2385 | 0 | 0 | 0
| 50000 | 2491 | 470 | 3769 | 0 | 15 | 16
| 60000 | 3612 | 672 | 5439 | 10 | 12 | 6
| 100000 | 10301 | 0 | 15091 | 0 | 0 | 15
| 200000 | 40017 | 0 | 60516 | 0 | 0 | 20
Explanation / Answer
Hello there ,
Please find your code below and it's O/P.
I have printed arrays as well with the desired O/P. So that you can have trace of what is happening .I hope that you do not mind.
At the end , It will print desiered table.
If you want to remove other sysout , you can except printInTabularFormat(time);
printInTabularFormat(time); will print tabel. Kindly wait till the the progrma finishes execution and then and then you will have table. :-)
import java.util.Arrays;
import java.util.Random;
public class SortingAlgoPerformanceMeasurement {
static int[] size = { 10000, 20000, 30000, 40000, 50000, 60000, 100000, 200000 };
static String format = "|%1$-20s|%2$-20s|%3$-20s|%4$-20s|%5$-20s|%6$-20s|%7$-20s| ";
public static void main(String args[]) {
int max = 5000;
long startTime, endTime, executionTime;
long[][] time = new long[size.length][6];
Random generator = new Random();
for (int i = 0; i < size.length; i++) { // For getting size of different
int indexForAlgo = 0;
// array to be created
int[] array = new int[size[i]];
int[] unSortedArray = new int[size[i]];
for (int j = 0; j < size[i]; j++) { // For creating that many random
// numbers.
array[j] = generator.nextInt(max); // Prepare an array for all
// size
}
System.out.println("Unsorted array of length: " + array.length + " ");
System.out.println(Arrays.toString(array));
System.arraycopy(array, 0, unSortedArray, 0, size[i]); // Retaining
// the copy
// of
// unsorted
// array
startTime = System.currentTimeMillis();
selectionSort(array);
endTime = System.currentTimeMillis();
executionTime = endTime - startTime;
time[i][indexForAlgo] = executionTime;
indexForAlgo++;
System.out.println("O/P:selectionSort");
System.out.println(Arrays.toString(array));
System.arraycopy(unSortedArray, 0, array, 0, size[i]); // Again
// make
// it
// unsorted
if (array.length != 100000 && array.length != 200000) {
startTime = System.currentTimeMillis();
insertionSort(array);
endTime = System.currentTimeMillis();
executionTime = endTime - startTime;
time[i][indexForAlgo] = executionTime;
System.out.println("O/P:insertionSort");
System.out.println(Arrays.toString(array));
System.arraycopy(unSortedArray, 0, array, 0, size[i]);
}
indexForAlgo++;
startTime = System.currentTimeMillis();
bubbleSort(array);
endTime = System.currentTimeMillis();
executionTime = endTime - startTime;
time[i][indexForAlgo] = executionTime;
indexForAlgo++;
System.out.println("O/P:bubbleSort");
System.out.println(Arrays.toString(array));
System.arraycopy(unSortedArray, 0, array, 0, size[i]);
if (array.length != 100000 && array.length != 200000) {
startTime = System.currentTimeMillis();
mergeSort(array);
endTime = System.currentTimeMillis();
executionTime = endTime - startTime;
time[i][indexForAlgo] = executionTime;
System.out.println("O/P:mergeSort");
System.out.println(Arrays.toString(array));
System.arraycopy(unSortedArray, 0, array, 0, size[i]);
}
indexForAlgo++;
if (array.length != 100000 && array.length != 200000) {
startTime = System.currentTimeMillis();
quickSort(array, 0, array.length - 1);
endTime = System.currentTimeMillis();
executionTime = endTime - startTime;
time[i][indexForAlgo] = executionTime;
System.out.println("O/P:quickSort");
System.out.println(Arrays.toString(array));
System.arraycopy(unSortedArray, 0, array, 0, size[i]);
}
indexForAlgo++;
// unsorted
startTime = System.currentTimeMillis();
radixSort(array);
endTime = System.currentTimeMillis();
executionTime = endTime - startTime;
time[i][indexForAlgo] = executionTime;
indexForAlgo++;
System.out.println("O/P:radixSort");
System.out.println(Arrays.toString(array));
System.arraycopy(unSortedArray, 0, array, 0, size[i]);
}
// Print table.
printInTabularFormat(time);
}
/**
* Implements Selection Sort.
*
* @param arr
*/
public static void selectionSort(int arr[]) {
int N = arr.length;
int i, j, pos, temp;
for (i = 0; i < N - 1; i++) {
pos = i;
for (j = i + 1; j < N; j++) {
if (arr[j] < arr[pos]) {
pos = j;
}
}
/* Swap arr[i] and arr[pos] */
temp = arr[i];
arr[i] = arr[pos];
arr[pos] = temp;
}
}
/**
* Implements Insertion Sort.
*
* @param arr
*/
public static void insertionSort(int[] arr) {
int temp;
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
}
/**
* Implements Bubble Sort.
*
* @param arr
*/
public static void bubbleSort(int[] arr) {
int n = arr.length;
int temp = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < (n - i); j++) {
if (arr[j - 1] > arr[j]) {
// swap the elements!
temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
}
/**
* Implements Merge Sort.
*
* @param arr
*/
public static void mergeSort(int[] arr) {
if (arr.length <= 1) {
return;
}
// Split the array in half
int[] first = new int[arr.length / 2];
int[] second = new int[arr.length - first.length];
System.arraycopy(arr, 0, first, 0, first.length);
System.arraycopy(arr, first.length, second, 0, second.length);
// Sort each half
mergeSort(first);
mergeSort(second);
// Merge the halves together, overwriting the original array
merge(first, second, arr);
}
private static void merge(int[] first, int[] second, int[] result) {
// Merge both halves into the result array
// Next element to consider in the first array
int iFirst = 0;
// Next element to consider in the second array
int iSecond = 0;
// Next open position in the result
int j = 0;
// As long as neither iFirst nor iSecond is past the end, move the
// smaller element into the result.
while (iFirst < first.length && iSecond < second.length) {
if (first[iFirst] < second[iSecond]) {
result[j] = first[iFirst];
iFirst++;
} else {
result[j] = second[iSecond];
iSecond++;
}
j++;
}
// copy what's left
System.arraycopy(first, iFirst, result, j, first.length - iFirst);
System.arraycopy(second, iSecond, result, j, second.length - iSecond);
}
/**
* Implements Quick Sort.
*
* @param arr
*/
public static void quickSort(int[] arr, int low, int high) {
if (arr == null | arr.length == 0)
return;
if (low >= high)
return;
// pick the pivot
int middle = low + (high - low) / 2;
int pivot = arr[middle];
// make left < pivot and right > pivot
int i = low, j = high;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// recursively sort two sub parts
if (low < j)
quickSort(arr, low, j);
if (high > i)
quickSort(arr, i, high);
}
private static int getMax(int arr[], int n) {
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
// A function to do counting sort of arr[] according to
// the digit represented by exp.
private static void countSort(int arr[], int n, int exp) {
int output[] = new int[n]; // output array
int i;
int count[] = new int[10];
Arrays.fill(count, 0);
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
// Change count[i] so that count[i] now contains
// actual position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to curent digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}
/**
* Implements Radix Sort.
*
* @param arr
*/
static void radixSort(int arr[]) {
// Find the maximum number to know number of digits
int m = getMax(arr, arr.length);
// Do counting sort for every digit. Note that instead
// of passing digit number, exp is passed. exp is 10^i
// where i is current digit number
for (int exp = 1; m / exp > 0; exp *= 10)
countSort(arr, arr.length, exp);
}
public static void printInTabularFormat(long[][] time) {
System.out.println(" ");
System.out.format(format, "Array", "Selection", "Insertion", "Bubble", "Merge", "Quick", "Radix");
System.out.format(format, "Size", "Sort", "Sort", "Sort", "Sort", "Sort", "Sort");
System.out
.println("----------------------------------------------------------------------------------------------------------------------------------------------------");
int sizeIndex = 0;
for (long[] arr : time) {
System.out.format(format, size[sizeIndex], arr[0], arr[1], arr[2], arr[3], arr[4], arr[5]);
sizeIndex++;
}
}
}
====Partial O/P==== I will not print 10000 size array here. You will have in proper format ! Do no worry !
|Array |Selection |Insertion |Bubble |Merge |Quick |Radix |
|Size |Sort |Sort |Sort |Sort |Sort |Sort |
----------------------------------------------------------------------------------------------------------------------------------------------------
|10000 |41 |42 |102 |6 |4 |4 |
|20000 |152 |137 |421 |3 |2 |1 |
|30000 |310 |295 |1004 |6 |3 |2 |
|40000 |566 |537 |1808 |6 |3 |2 |
|50000 |879 |818 |2860 |7 |4 |3 |
|60000 |1231 |1180 |4142 |9 |4 |5 |
|100000 |3550 |0 |11719 |0 |0 |6 |
|200000 |13666 |0 |46973 |0 |0 |17 |
Let me know if you have any doubts.
Thanks.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.