QuestionQuestion

1. Project Specification
Consider the QuickSort algorithm for sorting arrays and two algorithm optimization proposals QSopt1 and QSopt2, described below. QSopt1 executes QuickSort for the partitions of size larger than a given cutoff value (usually 10) and executes Insertion Sort for sorting the partitions of size less than or equal to the cutoff value. QSopt2 executes QuickSort until all partitions size gets lower than a given cutoff value (usually 10) and then, executes the improved Bubble Sort algorithm upon the whole "almost sorted" array. This project requires writing two Java programs detailed below in Part 1 (testing the functionality of the proposed algorithms) and Part 2 (measuring and comparing their execution time).

Part 1 (Testing algorithms functionality)
Design and implement a program to test the QSopt1 and QSopt2 algorithms. Define an array of size 100, populated with randomly generated Integer or int values in the range 1 .. 999 and sort the array in increasing order by using the QuickSort algorithm followed by QSopt1 and then by QSopt2. Display the array content before sorting and then after invoking each sorting method.

Part 2 (Measuring execution time)
Design, implement and test a program which uses System.nanoTime() method to (1) measure the execution time of the three sorting algorithms and (2) display the average execution time values for 100 runs. Do this for each of the array sizes specified in the table below. Consider the arrays as being randomly populated with Integer or int values in the range 1 .. MAX as specified for each SIZE in the table below.
Note that due to the behavior of the JIT compiler, the execution time of the algorithms is much slower the first times they are run and therefore make sure to discard the measured values for the initial 5 runs.

Table 1 - Average Execution Time
Average execution time for 100 runs
SIZE = 100 MAX = 999 SIZE = 1000 MAX = 9,999 SIZE = 10,000 MAX = 99,999
QuickSort
QSopt1
QSopt2

Notes.
1. The array contents should not be displayed for Part 2.
2. For Part 2, the three algorithms should be executed and their execution time should be displayed for the required array sizes within the same program execution.
2. Submission Requirements
Submit the following before the due date listed in the Calendar:
1. Part1.zip including all .java of Part 1 and Part2.zip including table of average execution time and results discussion

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

public static void main(String[] args) {
       Random ra = new Random();
       int size = 100;
       int cutoff = 10;
       int range = 1000;
       int [] qsort1 = new int[size];
       int [] qsort2 = new int[size];
       int [] qsort = new int[size];
      
       System.out.println("Original array");
       for (int i = 0; i < size; i++) {
            qsort1[i] = ra.nextInt(range);
            qsort2[i] = qsort1[i];
            qsort[i] = qsort1[i];
            System.out.print(qsort1[i] + " ");
       }
       System.out.println("");
      
       QuickSort q = new QuickSort();...
$60.00 for this solution

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

Find A Tutor

View available Java Programming 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