Objective: IN JAVA Write a program that implements the following search algorith
ID: 3724591 • Letter: O
Question
Objective:
IN JAVA
Write a program that implements the following search 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
Finally at the end give the average number of checks using each algorithm.
Explanation / Answer
JAVA PROGRAMME :
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.