Objective: Java Program Write a program that implements the following sorting al
ID: 3669060 • 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
Program:
import java.util.Scanner;
public class a {
static int q=0,m=0,b=0,s=0;static int[] p;
public static void main(String args[]) {
int n;int k=0;int l=20;
int num[];int sq=0,sm=0,sb=0,ss=0;
Scanner scan = new Scanner(System.in);
System.out.println("Quick Sort");
System.out.println(" Enter 'n' value :");
n = Integer.parseInt(scan.nextLine());
num = new int[n];
p = new int[n];
while(k<l)
{
k++;
for (int i = 0; i < n; i++) {
num[i] = (int)(Math.random()*1000);
for (int j = 0; j < i; j++) {
if (num[i] == num[j]) {
i--; //if a[i] is a duplicate of a[j], then run the outer loop on i again
break;
}
}
}
for(int i=0; i<n; i++) {
p[i]=num[i];
}
MergeSort(num, 0, n-1);
for(int i=0; i<n; i++) {
num[i]=p[i];
}
// Quick Sort Event..
QuickSort(num, 0, n-1);
for(int i=0; i<n; i++) {
num[i]=p[i];
}
BubbleSort(num,n);
for(int i=0; i<n; i++) {
num[i]=p[i];
}
SelectionSort(num,n);
sq=sq+q;
sm=sm+m;
sb=sb+b;
ss=ss+s;
//System.out.print(" main q= " + q+" main m= " + m+" main b= " + b+" main s= " + s);
}
System.out.print(" average iteration for quick sort = " + (sq/20)+" average iteration for merge sort= " + (sm/20)+" average iteration for bubble sort= " + sb/20+" average iteration for selection sort= " + ss/20);
}
public static void SelectionSort(int num[],int n) {
/* Selection Sort Code Start */
for(int i=0; i<n; i++) {
int index_of_min = i;
for(int j=i; j<n; j++) {
if(num[index_of_min] > num[j]) {
index_of_min = j;
}
}
int temp = num[i];
num[i] = num[index_of_min];
num[index_of_min] = temp;s=s+1;
}
}
private static void MergeSort(int[] num, int i, int j) {
int low = i;
int high = j;
if (low >= high) {
return;
}
int middle = (low + high) / 2;
MergeSort(num, low, middle);
MergeSort(num, middle + 1, high);
int end_low = middle;
int start_high = middle + 1;
while ((low <= end_low) && (start_high <= high)) {
if (num[low] < num[start_high]) {
low++;
}
else {
int Temp = num[start_high];
for (int k = start_high- 1; k >= low; k--) {
num[k+1] = num[k];
}
num[low] = Temp;m=m+1;
low ++;
end_low ++;
start_high ++;
}
}
}
public static void BubbleSort(int num[],int n) {
/* Bubble Sort Code Start */
for(int i = 0; i < n; i++) {
for(int j = 1; j < (n-i); j++) {
if(num[j-1] > num[j]) {
int temp = num[j-1];
num[j-1] = num[j];
num[j] = temp;b=b+1;
}
}
}
}
private static void QuickSort(int[] num, int i, int j) {
int low = i;
int high = j;
if (low >= j) {
return;
}
int mid = num[(low + high) / 2];
while (low < high) {
while (low<high && num[low] < mid) {
low++;
}
while (low<high && num[high] > mid) {
high--;
}
if (low < high) {
int T = num[low];
num[low] = num[high];
num[high] = T;
q=q+1;
}
}
if (high < low) {
int T = high;
high = low;
low = T;
}
QuickSort(num, i, low);
QuickSort(num, low == i ? low+1 : low, j);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.