JAVA JAVA JAVA JAVA PLEASE INCLUDE COMMENTS AND OUTPUT!! Write a program that im

Question

JAVA JAVA JAVA JAVA

PLEASE INCLUDE COMMENTS AND OUTPUT!!

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

Hi, You can add a loop to get average running time. I have done everything. Just go through code and add exatra functionality of your need.

import java.util.Random;

public class Sorting {

   public static int doSelectionSort(int[] arr) {

       int count = 0;
       for (int i = 0; i < arr.length - 1; i++) {
           int index = i;
           for (int j = i + 1; j < arr.length; j++)
               if (arr[j] < arr[index]){
                   index = j;
                   count++;
               }

           int smallerNumber = arr[index];
           arr[index] = arr[i];
           arr[i] = smallerNumber;
       }
       return count;
   }
  
   // logic to sort the elements
   public static int bubble_srt(int array[]) {
       int n = array.length;
       int count=0;
       int k;
       for (int m = n; m >= 0; m--) {
           for (int i = 0; i < n - 1; i++) {
               k = i + 1;
               if (array[i] > array[k]) {
                   swapNumbers(i, k, array);
                   count++;
               }
           }
       }
       return count;
   }
  
   private static void swapNumbers(int i, int j, int[] array) {

       int temp;
       temp = array[i];
       array[i] = array[j];
       array[j] = temp;
   }

   private static void printNumbers(int[] input) {

       for (int i = 0; i < input.length; i++) {
           System.out.print(input[i] + ", ");
       }
       System.out.println(" ");
   }
  
   /* Merge Sort function */
   public static void mergeSort(int[] a, int low, int high) {
       int N = high - low;
       if (N <= 1)
           return;
       int mid = low + N / 2;
       // recursively sort
       mergeSort(a, low, mid);
       mergeSort(a, mid, high);
       // merge two sorted subarrays
       int[] temp = new int[N];
       int i = low, j = mid;
       for (int k = 0; k < N; k++) {
           if (i == mid)
               temp[k] = a[j++];
           else if (j == high)
               temp[k] = a[i++];
           else if (a[j] < a[i])
               temp[k] = a[j++];
           else
               temp[k] = a[i++];
       }
       for (int k = 0; k < N; k++)
           a[low + k] = temp[k];
   }

   /** Quick Sort function **/
   public static void quickSort(int[] arr) {
       quickSort(arr, 0, arr.length - 1);
   }
  
   /** Quick sort function **/
   private static void quickSort(int arr[], int low, int high) {
       int i = low, j = high;
       int temp;
       int pivot = arr[(low + high) / 2];

       /** partition **/
       while (i <= j) {
           while (arr[i] < pivot)
               i++;
           while (arr[j] > pivot)
               j--;
           if (i <= j) {
               /** swap **/
               temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;

               i++;
               j--;
           }
       }

       /** recursively sort lower half **/
       if (low < j)
           quickSort(arr, low, j);
       /** recursively sort upper half **/
       if (i < high)
           quickSort(arr, i, high);
   }
  
   public static void main(String[] args) {
       int[] src = new int[1000];
       int[] copy = new int[1000];
      
       Random random = new Random(); // reading 1000 elements
       for(int i=0; i<1000;i++){
           src[i] = random.nextInt(1000);
       }

       System.arraycopy( src, 0, copy, 0, src.length );// it will copy elements from src to copy
       //selectioSort
       System.out.println("Using selection Sort: ");
       printNumbers(copy);
       doSelectionSort(copy);
       printNumbers(copy);
      
       System.arraycopy( src, 0, copy, 0, src.length );// it will copy elements from src to copy
       //selectioSort
       System.out.println("Using Bubble Sort: ");
       printNumbers(copy);
       bubble_srt(copy);
       printNumbers(copy);
      
       System.arraycopy( src, 0, copy, 0, src.length );// it will copy elements from src to copy
       //selectioSort
       System.out.println("Using Quick Sort: ");
       printNumbers(copy);
       quickSort(copy, 0, copy.length-1);
       printNumbers(copy);
      
       System.arraycopy( src, 0, copy, 0, src.length );// it will copy elements from src to copy
       //selectioSort
       System.out.println("Using Merge Sort: ");
       printNumbers(copy);
       mergeSort(copy, 0, copy.length);
       printNumbers(copy);
   }
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.