Question

Your running times will probably be different than these. Please do a better job with the snipping tool than I did.

Java program provided:

// Student Name Today's Date

import java.util.Arrays;
import java.util.Random;

public class SortTimer {

   // Please expand method main() to meet the lab requirements.
  
   // You have the following sorting methods available:
   // insertionSort(int[] a);
   // selectionSort(int[] a);
   // mergeSort(int[] a);
   // quickSort(int[] a);
   // The array will be in sorted order after the routines are called!
   // Be sure to re-randomize the array after each sort.
  
   public static void main(String[] args) {
       // Create and initialize arrays
       int[] a = {1, 3, 5}, b, c, d;
      
       // Check the time to sort array a
       long startTime = System.nanoTime();
       quickSort(a);
       long endTime = System.nanoTime();
      
       long duration = (endTime - startTime) / 1000l;
      
       // Output results
       System.out.println("Working on an array of length " + a.length + ".");
       System.out.println("Quick sort: " + duration + "us.");  
   }

  
  
  

  
  
  
  
  
  
   //
   // ###############################################################
   //
   // Standard implementations of sorting algorithms follow.
    //
   // Please do not include these methods in your lab submission
   //
   // ###############################################################
   //
  
   // Thanks to https://www.javatpoint.com/insertion-sort-in-java
   public static void insertionSort(int array[]) {
       int n = array.length;
       for (int j = 1; j < n; j++) {
           int key = array[j];
           int i = j - 1;
           while ((i > -1) && (array[i] > key)) {
               array[i + 1] = array[i];
               i--;
           }
           array[i + 1] = key;
       }
   }

   // Thanks to
   // http://www.java2novice.com/java-sorting-algorithms/selection-sort/
   public static void selectionSort(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;
       }
   }

   // Thanks to http://stackoverflow.com/questions/13727030/mergesort-in-java
   public static void mergeSort(int[] A) {
       if (A.length > 1) {
           int q = A.length / 2;

           // changed range of leftArray from 0-to-q to 0-to-(q-1)
           int[] leftArray = Arrays.copyOfRange(A, 0, q - 1);
           // changed range of rightArray from q-to-A.length to
           // q-to-(A.length-1)
           int[] rightArray = Arrays.copyOfRange(A, q, A.length - 1);

           mergeSort(leftArray);
           mergeSort(rightArray);

           merge(A, leftArray, rightArray);
       }
   }

   private static void merge(int[] a, int[] l, int[] r) {
       int totElem = l.length + r.length;
       // int[] a = new int[totElem];
       int i, li, ri;
       i = li = ri = 0;
       while (i < totElem) {
           if ((li < l.length) && (ri < r.length)) {
               if (l[li] < r[ri]) {
                   a[i] = l[li];
                   i++;
                   li++;
               } else {
                   a[i] = r[ri];
                   i++;
                   ri++;
               }
           } else {
               if (li >= l.length) {
                   while (ri < r.length) {
                       a[i] = r[ri];
                       i++;
                       ri++;
                   }
               }
               if (ri >= r.length) {
                   while (li < l.length) {
                       a[i] = l[li];
                       li++;
                       i++;
                   }
               }
           }
       }
       // return a;
   }

   // Thanks to: http://www.algolist.net/Algorithms/Sorting/Quicksort
   public static void quickSort(int arr[]) {
       quickSortRecurse(arr, 0, arr.length-1);
   }
  
   private static void quickSortRecurse(int arr[], int left, int right) {
       int index = partition(arr, left, right);
       if (left < index - 1)
           quickSortRecurse(arr, left, index - 1);
       if (index < right)
           quickSortRecurse(arr, index, right);
   }

   private static int partition(int arr[], int left, int right) {
       int i = left, j = right;
       int tmp;
       int pivot = arr[(left + right) / 2];

       while (i <= j) {
           while (arr[i] < pivot)
               i++;
           while (arr[j] > pivot)
               j--;
           if (i <= j) {
               tmp = arr[i];
               arr[i] = arr[j];
               arr[j] = tmp;
               i++;
               j--;
           }
       }
       ;

       return i;
   }

}

When answered could you please provide the full program!

thank you.

5. Sort comprehensive A java class is provided with standard code for four kinds of sort: insertionSort, selectionSort, mergeSort, and guickSort. Expand the main) method to do the following: 5.1. Create the following arrays of random integers. Number of random integers Array 100 1000 10,000 100,000 1,000,000 I don't care about variable names. I do care that five arrays exist and have the specified number of random integers. Please declare these arrays however best suits your program. 5.2. User the following code to measure the time a given sort needs to sort the array. randomizeArray (a); long startTime SystemnanoTime sortArrax (a) long enc me = long duration = (endTime - startTime) / 10001; system.nanoTimeC); 5.3. Measure the time it takes for: insertionSort, selectionSort, mergeSort, and guickSort each to sort the arrays. Your arrays will be sorted after you call the sort routines! Make sure to reinitialize the arrays with random values before each sort. 5.4. Output the time it takes for the sorts to run on each of the arrays. You will have to increase the size of the console pane to capture all the output. Your program output could look like: Testing an array of length 100. Quick sort: 23ms Merge sort: 67ms Insertion sort: 71ms Selection sort: 107ms Testing an array of length 1000 Quick sort: 339ms Merge sort: 429ms Insertion sort: 1790ms Selection sort: 2354ms Testing an array of length 10000 Quick sort: 1131ms Merge sort: 1154ms Insertion sort: 37014ms Selection sort: 25782ms Testing an array of length 100000 Quick sort: 8472ms Merge sort: 7437ms Insertion sort: 1010801ms Selection sort: 2361578ms resting an array of length 1000000 Quick sort: 96143ms Merge sort: 160642ms Insertion sort: 106746441ms

Answer 1

• I have pasted the code and screenshot of successful run below.
• Instead of calling randomizeArray(a) I am using calling a = copy(b,n) it ensures that every sort algorithm gets the same copy of randomized array. The array b is initialized with random integers for each array length.
• In case of any doubts just comment down.
• Please do upvote if you found this helpful.

-------------------------Screenshot-----------------------

ksmukta:16.iava ->iavac SortTimer.java && iava SortTimer Working on an array of length 100. Quick sort: 75us Merge sort: 154us Insertion sort: 117us. Selection sort: 175us. Working on an array of length 1000 Quick sort: 687us Merge sort: 1184us. Insertion sort: 4320us Selection sort: 5775us Working on an array of length 10000 Quick sort: 2323us. Merge sort: 2192us. Insertion sort: 61302us. Selection sort: 129185us. Working on an array of length 100000 Quick sort: 15895us. Merge sort: 16520us. Insertion sort: 1889288us Selection sort: 6388318us Working on an array of length 1000000 Quick sort: 184581us Merge sort: 193903us Insertion sort: 208492790us.

-------------------------Code-----------------------

// Student Name Today's Date

import java.util.Arrays;
import java.util.Random;

public class SortTimer {

// Please expand method main() to meet the lab requirements.
  
// You have the following sorting methods available:
// insertionSort(int[] a);
// selectionSort(int[] a);
// mergeSort(int[] a);
// quickSort(int[] a);
// The array will be in sorted order after the routines are called!
// Be sure to re-randomize the array after each sort.

public static int[] copy(int[] b, int n){
int[] a = new int[n];
for(int i=0;i<n;i++){
a[i] = b[i];
}
return a;
}

public static void main(String[] args) {
Random randomGenerator = new Random();
int[] sizes = {100,1000,10000,100000,1000000};
for(int n: sizes){
int[] b;
b = new int[n];
for(int i=0;i<n;i++){
b[i] = randomGenerator.nextInt();
}
System.out.println("Working on an array of length " + n + ".");
long startTime, endTime, duration;
int[] a;
// QuickSort
a = copy(b,n);
startTime = System.nanoTime();
quickSort(a);
endTime = System.nanoTime();
duration = (endTime - startTime) / 1000l;
System.out.println("Quick sort: " + duration + "us.");

a = copy(b,n);
startTime = System.nanoTime();
mergeSort(a);
endTime = System.nanoTime();
duration = (endTime - startTime) / 1000l;
System.out.println("Merge sort: " + duration + "us.");

a = copy(b,n);
startTime = System.nanoTime();
insertionSort(a);
endTime = System.nanoTime();
duration = (endTime - startTime) / 1000l;
System.out.println("Insertion sort: " + duration + "us.");

a = copy(b,n);
startTime = System.nanoTime();
selectionSort(a);
endTime = System.nanoTime();
duration = (endTime - startTime) / 1000l;
System.out.println("Selection sort: " + duration + "us.");

System.out.println();
}
}

  
  
  

  
  
  
  
  
  
//
// ###############################################################
//
// Standard implementations of sorting algorithms follow.
//
// Please do not include these methods in your lab submission
//
// ###############################################################
//
  
// Thanks to https://www.javatpoint.com/insertion-sort-in-java
public static void insertionSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j - 1;
while ((i > -1) && (array[i] > key)) {
array[i + 1] = array[i];
i--;
}
array[i + 1] = key;
}
}

// Thanks to
// http://www.java2novice.com/java-sorting-algorithms/selection-sort/
public static void selectionSort(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;
}
}

// Thanks to http://stackoverflow.com/questions/13727030/mergesort-in-java
public static void mergeSort(int[] A) {
if (A.length > 1) {
int q = A.length / 2;

// changed range of leftArray from 0-to-q to 0-to-(q-1)
int[] leftArray = Arrays.copyOfRange(A, 0, q - 1);
// changed range of rightArray from q-to-A.length to
// q-to-(A.length-1)
int[] rightArray = Arrays.copyOfRange(A, q, A.length - 1);

mergeSort(leftArray);
mergeSort(rightArray);

merge(A, leftArray, rightArray);
}
}

private static void merge(int[] a, int[] l, int[] r) {
int totElem = l.length + r.length;
// int[] a = new int[totElem];
int i, li, ri;
i = li = ri = 0;
while (i < totElem) {
if ((li < l.length) && (ri < r.length)) {
if (l[li] < r[ri]) {
a[i] = l[li];
i++;
li++;
} else {
a[i] = r[ri];
i++;
ri++;
}
} else {
if (li >= l.length) {
while (ri < r.length) {
a[i] = r[ri];
i++;
ri++;
}
}
if (ri >= r.length) {
while (li < l.length) {
a[i] = l[li];
li++;
i++;
}
}
}
}
// return a;
}

// Thanks to: http://www.algolist.net/Algorithms/Sorting/Quicksort
public static void quickSort(int arr[]) {
quickSortRecurse(arr, 0, arr.length-1);
}
  
private static void quickSortRecurse(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1)
quickSortRecurse(arr, left, index - 1);
if (index < right)
quickSortRecurse(arr, index, right);
}

private static int partition(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];

while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
;

return i;
}

}