Objective: Java Program Write a program that implements the following sorting al
ID: 3668681 • Letter: O
Question
Objective:
Java Program
Write a program that implements the following sorting algorithms:
Selection Sort
Bubble Sort
Merge Sort
Quick Sort
Next test the efficiency of each using the following steps:
Create an array of randomly selected whole numbers of 1,000 elements
Each value is selected from the range 0-999
Sort that array using each method
Make sure to copy the initial array into a new one so that the tests will be accurate and not be sorting sorted arrays
Show that each method successfully sorted the array
Count the number of checks each method had to perform before fully sorting the array
Keep track of the total number of checks for each algorithm
Perform this 20 times and keep track of the running average
Finally at the end give the average number of checks using each algorithm.
Explanation / Answer
import java.util.Random;
public class SortingAnalysis {
private static int doSelectionSort(int[] arr) {
int checks = 0;
for (int i = 0; i < arr.length - 1; i++) {
int index = i;
for (int j = i + 1; j < arr.length; j++) {
checks++;
if (arr[j] < arr[index])
index = j;
}
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
return checks;
}
private static int bubbleSort(int[] arr) {
int n = arr.length;
int temp = 0;
int checks = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < (n - i); j++) {
checks++;
if (arr[j - 1] > arr[j]) {
// swap the elements!
temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
return checks;
}
private static int[] generateRandomArrayWithRandomNum() {
Random random = new Random();
int[] dataArray = new int[1000];
for (int i = 0; i < 1000; i++) {
dataArray[i] = random.nextInt(1000);
}
return dataArray;
}
public static void main(String[] args) {
int[] arr = generateRandomArrayWithRandomNum();
int checksSelectionSort = 0;
int checksBubbleSort = 0;
int checksMergeSort = 0;
int checksQuickSort = 0;
int[] copyArr = new int[1000];
for (int i = 0; i < 20; i++) {
System.arraycopy(arr, 0, copyArr, 0, 1000);
checksSelectionSort += doSelectionSort(arr);
System.arraycopy(copyArr, 0, arr, 0, 1000);
checksBubbleSort += bubbleSort(copyArr);
System.arraycopy(arr, 0, copyArr, 0, 1000);
checksMergeSort += new mergeSort().sort(arr);
System.arraycopy(copyArr, 0, arr, 0, 1000);
checksQuickSort += new quickSort().sort(copyArr);
}
System.out.println("Analysis Of Sorting algorithms ");
System.out.println("Selection Sort : "+checksSelectionSort/20);
System.out.println("Bubble Sort : "+checksBubbleSort/20);
System.out.println("Merge Sort : "+checksMergeSort/20);
System.out.println("Quick Sort : "+checksQuickSort/20);
}
}
class mergeSort {
private int[] array;
private int[] tempMergArr;
private int length;
private int checks;
public int sort(int inputArr[]) {
this.array = inputArr;
this.length = inputArr.length;
this.tempMergArr = new int[length];
doMergeSort(0, length - 1);
return checks;
}
private void doMergeSort(int lowerIndex, int higherIndex) {
checks++;
if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Below step sorts the left side of the array
doMergeSort(lowerIndex, middle);
// Below step sorts the right side of the array
doMergeSort(middle + 1, higherIndex);
// Now merge both sides
mergeParts(lowerIndex, middle, higherIndex);
}
}
private void mergeParts(int lowerIndex, int middle, int higherIndex) {
for (int i = lowerIndex; i <= higherIndex; i++) {
tempMergArr[i] = array[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempMergArr[i] <= tempMergArr[j]) {
array[k] = tempMergArr[i];
i++;
} else {
array[k] = tempMergArr[j];
j++;
}
k++;
}
while (i <= middle) {
array[k] = tempMergArr[i];
k++;
i++;
}
}
}
class quickSort {
private int array[];
private int length;
private int checks;
public int sort(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
return 0;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
return checks;
}
private void quickSort(int lowerIndex, int higherIndex) {
checks++;
int i = lowerIndex;
int j = higherIndex;
int pivot = array[lowerIndex + (higherIndex - lowerIndex) / 2];
while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
i++;
j--;
}
}
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.