Quick Sort Evaluation

1. Quicksort

(a) Implement a generic Quicksort algorithm that takes an array as input

• This file should be called QSNormal.java
• This class should have a sort method:
  public static void sort(int[] input)

(b) Implement a Quicksort algorithm that uses diversion to Insertion Sort.

• This file should be called QSInsertion.java
• The class should have a sort method:
  public static void sort(int[] input)

(c) Write classes that are able to generate test inputs of size 10, 100, 10000, 1000000.

• One file should be RandomGen.java
• One file should be FixedGen.java
• RandomGen should generate random integers of a uniform dis- tribution.
• FixedGen should always generate a fixed ascending input.

(d) Make a driver that sorts values from your input

• This file should be called QSDriver.java
• This file should output the run-time in either ns or us
• it should accept command-line as follows:
  java QSDriver < sort> < gen> < length> < seed>
  • < sort> is either QSNormal or QSInsertion
  • < gen> is either RandomGen or FixedGen
  • < length> is the number of ints to be sorted in the input array
  • < seed> is an optional argument (it might not be passed) that lets you repeat the random seed for RandomGen (but is ignored by FixedGen)
• Record performance times of runs for each input size specified in 1c for Quicksorts implemented in 1a and 1b using RandomGen.

2. In clear, natural language, describe the performance differences between the two sorts. Try to correlate this with the underlying mechanism. Iden- tify how you picked your diversion threshold.

• This textual response should be no more than 8 lines / 80 words.

3. In clear, natural language, describe a pathological input (one that yields a worst-case) for your Quicksorts defined in 1a. If FixedGen is not a pathological case, describe how pivot selection in your Quicksorts would lead to it becoming a pathological case.

• This textual response should be no more than 8 lines / 80 words.