Homework SourseWrite a program that obtains the execution time of selection
Solution
Hello there,
please find attached code and it\'s output.I have printed intermediate SYSOUT. You can remove those. It takes a bit longer time so wait for the final output! :-)
====O/P====
|Array |Selection |Insertion |Bubble |Merge |Quick |Radix |
|Size |Sort |Sort |Sort |Sort |Sort |Sort |
----------------------------------------------------------------------------------------------------------------------------------------------------
|50000 |855 |796 |2821 |16 |18 |21 |
|100000 |3482 |3243 |11422 |16 |0 |16 |
|150000 |7897 |7569 |26628 |25 |10 |7 |
|200000 |13683 |13360 |46701 |33 |10 |0 |
=====CODE=====
import java.util.Arrays;
import java.util.Random;
public class SortingAlgoPerformanceMeasurement {
static int[] size = { 50000, 100000, 150000, 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++;
}
}
}
===
Let me know if you have any doubts.
Thanks.
