Please answer this in java. I have already started (implemented the sorting meth
ID: 3669191 • Letter: P
Question
Please answer this in java. I have already started (implemented the sorting methods and implemented the array). Please give the answer as an extension to my current code, as this is the way we were taught and I cannot turn something in that has pieces of codes we have learned. Thank You
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.
import java.util.Arrays;
import java.util.Random;
public class SortingComparison {
static Random r = new Random();
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array = createArray();
selectionSort(array);
bubbleSort(array);
mergeSort(array);
quickSort(array,0,array.length);
}
private static int[] createArray() {//sorts the array
int size = r.nextInt(1000);
int[] array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = r.nextInt(1000);
}
Arrays.sort(array);
return array;
}
public static int[] selectionSort(int[] a)
{
int smallestIndex=0;
for(int i=0;i<a.length-1;i++)
{
smallestIndex=i;
for(int j=i+1;j<a.length;j++)
{
if(a[smallestIndex]>a[j])
{
smallestIndex=j;
}
}
int temp;
temp=a[i];
a[i]=a[smallestIndex];
a[smallestIndex]=temp;
}
return a;
}
public static int[] bubbleSort(int[] a)
{
boolean done = false;
int n = a.length;
while(done == false)
{
done=true;
for(int i=0;i<n-1;i++)
{
if(a[i]>a[i+1])//swap
{
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
done = false;
}
}
}
return a;
}
public static void mergeSort(int[] a)
{
int size=a.length;
if(size<2)
{
return;
}
int mid=size/2;
int leftSize=mid;
int rightSize=size-mid;
int[] left=new int[leftSize];
int[] right=new int[rightSize];
//populate left array
for(int i=0;i<mid;i++)
{
left[i]=a[i];
}
for(int i=mid;i<size;i++)
{
right[i-mid]=a[i];
}
mergeSort(left);
mergeSort(right);
//merge
merge(left,right,a);
}
public static void merge(int[] left, int[] right, int[] a)
{
int leftSize=left.length;
int rightSize=right.length;
int i=0;//index for left
int j=0;//index for right
int k=0;//index for a
while(i<leftSize && j<rightSize)
{
if(left[i]<=right[j])
{
a[k]=left[i];
i++;
k++;
}
else
{
a[k]=right[j];
j++;
k++;
}
}
//Fillsimpro in the rest
while(i<leftSize)
{
a[k]=left[i];
i++;
k++;
}
while(j<rightSize)
{
a[k]=right[j];
j++;
k++;
}
}
public static void quickSort(int[] a, int left, int right)
{
int index=partition(a,left,right);
if(left<index-1)
{
quickSort(a,left,index-1);
}
if(index<right)//still things to be sorted
{
quickSort(a,index+1,right);
}
}
public static int partition(int[] a, int left, int right)
{
int i=left;
int j=right;
int pivot=a[(left+right)/2];
while(i<=j)
{
while(a[i]<pivot)
{
i++;//correct position so move foward
}
while(a[j]>pivot)
{
j--;//correct position
}
if(i<=j)
{
int temp =a[i];
a[i]=a[j];
a[j]=temp;
i++;
j--;
}
}
return i;
}
}
Explanation / Answer
Here is the solution for you:
import java.util.Arrays;
import java.util.Random;
public class SortingComparison {
static Random r = new Random();
public static void main(String[] args) {
// TODO Auto-generated method stub
//Create an array of randomly selected whole numbers of 1,000 elements.
int[] array = createArray();
//Make sure to copy the initial array into a new one so that the tests will be accurate and not be sorting sorted arrays
int[] arrayDup = CopyArray(array);
//Sort that array using each method
//Show that each method successfully sorted the array
//Count the number of checks each method had to perform before fully sorting the array
System.out.println("Before sorting: ");
printArray(array);
array = selectionSort(array);
System.out.println("After sorting: ");
printArray(array);
array = CopyArray(arrayDup);
System.out.println("Before sorting: ");
printArray(array);
array = bubbleSort(array);
System.out.println("After sorting: ");
printArray(array);
array = CopyArray(arrayDup);
System.out.println("Before sorting: ");
printArray(array);
array = mergeSort(array);
System.out.println("After sorting: ");
printArray(array);
array = CopyArray(arrayDup);
System.out.println("Before sorting: ");
printArray(array);
array = quickSort(array,0,array.length);
System.out.println("After sorting: ");
printArray(array);
}
public static void printArray(int[] a)
{
for(int i = 0; i < 1000; i++)
{
System.out.prinf("%5d ", a[i]);
if(i+1 % 10 == 0)
System.out.println();
}
System.out.println();
}
public static int[] CopyArray(int[] a)
{
int[] dup = new int[1000];
for(int i = 0; i < 1000; i++)
dup[i] = a[i];
return dup;
}
private static int[] createArray() {//sorts the array
int size = r.nextInt(1000);
int[] array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = r.nextInt(1000);
}
Arrays.sort(array);
return array;
}
public static int[] selectionSort(int[] a)
{
int smallestIndex=0;
int numOfChecks = 0;
for(int i=0;i<a.length-1;i++)
{
smallestIndex=i;
for(int j=i+1;j<a.length;j++)
{
if(a[smallestIndex]>a[j])
{
numOfChecks++;
smallestIndex=j;
}
}
int temp;
temp=a[i];
a[i]=a[smallestIndex];
a[smallestIndex]=temp;
}
System.out.println("Number of checks in selection sort is: "+numOfChecks);
return a;
}
public static int[] bubbleSort(int[] a)
{
boolean done = false;
int n = a.length;
int numOfChecks = 0;
while(done == false)
{
done=true;
for(int i=0;i<n-1;i++)
{
if(a[i]>a[i+1])//swap
{
numOfChecks++;
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
done = false;
}
}
}
System.out.println("Number of checks in bubble sort is: "+numOfChecks);
return a;
}
public static void mergeSort(int[] a)
{
int size=a.length;
if(size<2)
{
return;
}
int mid=size/2;
int leftSize=mid;
int rightSize=size-mid;
int[] left=new int[leftSize];
int[] right=new int[rightSize];
//populate left array
for(int i=0;i<mid;i++)
{
left[i]=a[i];
}
for(int i=mid;i<size;i++)
{
right[i-mid]=a[i];
}
mergeSort(left);
mergeSort(right);
//merge
merge(left,right,a);
}
public static void merge(int[] left, int[] right, int[] a)
{
int leftSize=left.length;
int rightSize=right.length;
int i=0;//index for left
int j=0;//index for right
int k=0;//index for a
int numOfChecks = 0;
while(i<leftSize && j<rightSize)
{
if(left[i]<=right[j])
{
numOfchecks++;
a[k]=left[i];
i++;
k++;
}
else
{
a[k]=right[j];
j++;
k++;
}
}
//Fillsimpro in the rest
while(i<leftSize)
{
a[k]=left[i];
i++;
k++;
}
while(j<rightSize)
{
a[k]=right[j];
j++;
k++;
}
System.out.println("Number of checks in merge sort is: "+numOfChecks);
}
public static void quickSort(int[] a, int left, int right)
{
int index=partition(a,left,right);
if(left<index-1)
{
quickSort(a,left,index-1);
}
if(index<right)//still things to be sorted
{
quickSort(a,index+1,right);
}
}
public static int partition(int[] a, int left, int right)
{
int i=left;
int j=right;
int numOfChecks = 0;
int pivot=a[(left+right)/2];
while(i<=j)
{
while(a[i]<pivot)
{
numOfChecks++;
i++;//correct position so move foward
}
while(a[j]>pivot)
{
numOfChecks++;
j--;//correct position
}
if(i<=j)
{
numOfChecks++;
int temp =a[i];
a[i]=a[j];
a[j]=temp;
i++;
j--;
}
}
System.out.println("Number of checks in quick sort is: "+numOfChecks);
return i;
}
}