QuestionQuestion

Transcribed TextTranscribed Text

Homework Assignment The goal of this assignment is to give students an opportunity to compare and observe how running times of sorting algorithms grow as the input size (which is the number of elements to be sorted) grows. Since it is not possible to measure an accurate running time of an algorithm, you will use an elapsed time as an approximation. How to calculate the elapsed time of an algorithm is described later. You will use four sorting algorithms for this experiment: insertion-sort, merge-sort, quick-sort and heap-sort. A code of insertion-sort is in page 111 of our textbook. An array-based implementation of merge-sort is shown in pages 537 and 538 of our textbook. An array-based implementation of quick-sort is in page 553 of our textbook. You can use these codes, with some modification if needed, for this assignment. For heap-sort, our textbook does not have a code. You can implement it yourself or you may use any implementation you can find on the internet or any code written by someone else. If you use any material (pseudocode or implementation) that is not written by yourself, you must clearly show the source of the material in your report. A high-level pseudocode is given below: for n = 10,000, 20,000, . . ., 100,000 (for ten different sizes) Create an array of n random integers between 1 and 1,000,000 Run insertionsort and calculate the elapsed time // make sure you use the initial, unsorted array Run mergesort and calculate the elapsed time // make sure you use the initial, unsorted array Run quicksort and calculate the elapsed time // make sure you use the initial, unsorted array Run heapsort and calculate the elapsed time You can generate n random integers between 1 and 1,000,000 in the following way: Random r = new Random( ); for i = 1 to n a[i] = r.nextInt(1000000) + 1 You can also use the Math.random( ) method. Refer to a Java tutorial or reference manual on how to use this method. Note that it is important that you use the initial, unsorted array for each sorting algorithm. So, you may want to keep the original array and use a copy when you run each sorting algorithm. You can calculate the elapsed time of the execution of a sorting algorithm in the following way: long startTime = System.currentTimeMillis(); call a sorting algorithm long endTime = System.currentTimeMillis(); long elapsedTime = endTime ‐ startTime; Collect all elapsed times and show the result (1) as a table and (2) as a line graph. The table should look like: n Algorithm 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000 insertion merge quick heapsort Entries in the table are elapsed times in milliseconds. The line graph shows the same information but as a graph with four lines, one for each sorting algorithm. The x-axis of the graph is the input size n and the y-axis of the graph is the elapsed time in milliseconds. The following is an example graph: Input size Elapsed time 10K 20K . . . 100K Algorithm 1 Algorithm 2 Algorithm 3 Algorithm 4

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

public class SortingComparison {

public static void main(String[] args) {
    int[] sizes = {10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000, 100000};
   
    for (int size: sizes) {
      System.out.println("SIZE = " + size + " elements");
      
      int[] array = Utility.randomArray(size);
      int[] arrayCopy;
      int startTime, endTime, duration;
      
      
      
      arrayCopy = Utility.copyArray(array);
      startTime = (int) System.currentTimeMillis();
      InsertionSort.sort(arrayCopy);
      endTime = (int) System.currentTimeMillis();
      duration = endTime - startTime;
      System.out.println("Insertion Sort duration: " + duration + " ms");
      
      arrayCopy = Utility.copyArray(array);
      startTime = (int) System.currentTimeMillis();
      MergeSort.sort(arrayCopy);
      endTime = (int) System.currentTimeMillis();
      duration = endTime - startTime;
      System.out.println("Merge Sort duration: " + duration + " ms");
      
      arrayCopy = Utility.copyArray(array);
      startTime = (int) System.currentTimeMillis();
      QuickSort.sort(arrayCopy);
      endTime = (int) System.currentTimeMillis();
      duration = endTime - startTime;
      System.out.println("Quick Sort duration: " + duration + " ms");
      
      arrayCopy = Utility.copyArray(array);
      startTime = (int) System.currentTimeMillis();
      HeapSort.sort(arrayCopy);
      endTime = (int) System.currentTimeMillis();
      duration = endTime - startTime;
      System.out.println("Heap Sort duration: " + duration + " ms");
    }
   
}

}

/*
* Utility class
*/
class Utility {

// Helper method to construct random array
static int[] randomArray(int size) {
    int[] array = new int[size];
    for (int i = 0; i < size; i++) {
      array[i] = 1 + (int) (Math.random() * 1000000);
    }
    return array;
}

static int[] copyArray(int[] array) {
    int[] copy = new int[array.length];
    for (int i = 0; i < array.length; i++) {
      copy[i] = array[i];
    }
    return copy;
}

}

/*
* Insertion Sort Implementation
*/
class InsertionSort {

public static void sort(int arr[])
{
    int n = arr.length;
    for (int i=1; i<n; ++i)
    {
      int key = arr[i];
      int j = i-1;
      
      /* Move elements of arr[0..i-1], that are
       greater than key, to one position ahead
       of their current position */
      while (j>=0 && arr[j] > key)
      {
       arr[j+1] = arr[j];
       j = j-1;
      }
      arr[j+1] = key;
    }
}

}

/*
* Merge Sort Implementation
*/
class MergeSort {

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
static void merge(int arr[], int l, int m, int r)
{
    // Find sizes of two subarrays to be merged
    int n1 = m - l + 1;
    int n2 = r - m;
   
    /* Create temp arrays */
    int L[] = new int [n1];
    int...

By purchasing this solution you'll be able to access the following files:
Solution.docx, Solution.xlsx and Solution.java.

50% discount

Hours
Minutes
Seconds
$60.00 $30.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats