Sorting Comparison Objective: Write a program that implements the following sort

Question

Sorting Comparison

Objective:

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, I have written all sorting algo, you can testt.. I have wriiten code for selectioSort testing..

package chegg;

import java.util.Random;

public class Sorting {

   public static void doSelectionSort(int[] arr) {

       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;

           int smallerNumber = arr[index];
           arr[index] = arr[i];
           arr[i] = smallerNumber;
       }
   }
  
   // logic to sort the elements
   public static void bubble_srt(int array[]) {
       int n = array.length;
       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);
               }
           }
       }
   }
  
   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
       printNumbers(copy);
       doSelectionSort(copy);
       printNumbers(copy);
   }
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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