[Solved] Comp352-QuickSort

Submit source code and running instructions to EAS^[1]. Do it in Java. Do not use javas search methods! Do not use Javas Collections or Subclasses, code your own. Place textual responses for 2, 3 and 4 in block comments in your code.

Grade: 5%

1. Quicksort

• Implement a generic Quicksort algorithm that takes an array as input, it should use trivial pivot selection.
  1. This file should be called QSNormal.java
  2. This class should have a sort method: void sort(int[] input)
• Implement a Quicksort algorithm that uses a Median of Three pivot selection.
  1. This file should be called QSMedian.java
  2. The class should have a sort method: void sort(int[] input)
• Write classes that generate test inputs of size 10, 100, 10000, 1000000.
  1. One file should be RandomGen.java
  2. One file should be FixedGen.java

• RandomGen should generate uniformly random integers.

1. FixedGen should always generate a fixed input.

• Make a driver that sorts values from your input
  1. This file should be called QSDriver.java
  2. This file should output the run-time in either ns or s

• it should accept command-line as follows:

java QSDriver <sort> <gen> <length> <seed>

1. <sort> is either QSNormal or QSMedian B. <gen> is either RandomGen or FixedGen
   1. <length> is the number of ints to be sorted in the input array
   2. <seed> is an optional argument that lets you repeat the random seed for RandomGen (but is ignored by FixedGen)

1

(e) 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.
   • 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 trivial Quicksort defined in 1a. The FixedGen.java file should produce this pathological input.
   • This textual response should be no more than 8 lines / 80 words.
4. In clear, natural language, describe how the pathological case performs given the Median of Three Quicksort. Reference performance tests that you run and your understanding of what makes that input a pathological case. 1a.
   • This textual response should be no more than 10 lines / 100 words.

2

[1] https://fis.encs.concordia.ca/eas/