Project #40427 - Quick Sort Algorithms

DO NOT PLAGURIZE. I RUN IT THROUGH A PLAGURIZE FOUNDER.

 

Quick Sort Optimizations through Hybridization

1. Project Specification

Consider the QuickSort algorithm for sorting arrays (McAllistar Section 8.3.5 or Liang, Algorithm 25.7) and two algorithm optimization proposals QuickSortOpt1 and QuickSortOpt2, described below. 
QuickSortOpt1 executes QuickSort until partitions size gets lower than a given cutoff value (usually 10) and then, executes Insertion Sort for sorting the small partitions. 
QuickSortOpt2 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
Design and implement a program to test the QuickSortOpt1 and QuickSortOpt2 algorithms. Define an array of size 100, randomly populated with Integer or int values in the range 1 .. 999 and sort the array in increasing order by using the QuickSort algorithm followed by QuickSortOpt1 and then by QuickSortOpt2. Display the array content before sorting and then after invoking each sorting method.

Part 2
Design, implement and test a program which uses System.nanoTime() method to measure the execution time of the three sorting algorithms, for each of the array sizes specified in the table below, and display the average execution time values for 100 runs. 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. Consider the arrays as being randomly populated with Integer or int values in the range 1 .. MAX as specified in the table below for each SIZE value. 

Table 1 - Measured 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

 

 

 

QuickSortOpt1

 

 

 

QuickSortOpt2

 

 

 

Notes. 

1. The array contents should not be displayed for Part 2.  
2. For Part 2, the algorithms should be executed and their execution time should be displayed within one run, without modifying the source code and recompiling the project file(s).

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 all .java of Part 2.
2. A document file including relevant screenshots showing program execution as a result of test cases.
3. A document file describing your solution which should include the following elements: (3.1) a short problem analysis, (3.2) main design decisions, (3.3) assumptions, (3.4) short description of classes, (3.5) user interface, (3.6) test plan, (3.7) error handling, (3.8) lessons learned and (3.9) possible future developments. The size of the document should be of 3 pages, single spaced, font size 12.

Subject Computer
Due By (Pacific Time) 09/18/2014 12:00 am
Report DMCA
TutorRating
pallavi

Chat Now!

out of 1971 reviews
More..
amosmm

Chat Now!

out of 766 reviews
More..
PhyzKyd

Chat Now!

out of 1164 reviews
More..
rajdeep77

Chat Now!

out of 721 reviews
More..
sctys

Chat Now!

out of 1600 reviews
More..
sharadgreen

Chat Now!

out of 770 reviews
More..
topnotcher

Chat Now!

out of 766 reviews
More..
XXXIAO

Chat Now!

out of 680 reviews
More..
All Rights Reserved. Copyright by AceMyHW.com - Copyright Policy