2.1 Three Ways, One Quicksort
You must submit this in an archive named "qsort3.zip".
Flavor text: Link and Zelda are retired from their royal and knightly duties after one too many abductions. They now run an independent cocoa store. Unfortunately, with no one to kidnap, Ganon has become a business mogul with his "Ganon-bucks" franchise of faux high-end hot chocolate. Zelda and Link must improve the efficiency of the way they sort their receipts. Using the Ocarina of Time, Link has traveled to our future to consult computer scientists on sorting algorithms.
You must implement the Quicksort algorithm for integers in three ways:
The standard way with a single pivot element.
A two pivot method where you divide the list into three parts and do each separately.
A three pivot method where you divide the list into four parts and recur into each.
You must test each algorithm on lists of at least 1.5 million random integers (between 1 and 100.)
You may write one program with a mechanism for selecting the algorithm (GUI drop-down or command line switch) or three programs: one for each algorithm. The rest of this text assumes you write one program.
Your program must accept a space ( ) separated list of integers. (Perhaps by naming a file or from standard input.) (You may want to write a program to generate such inputs.)
Your program must have the option to output the sorted list, but must not do this by default.
Your program must output the time it took to solve the problem (not read in the input and solve the problem.)
If the sorted list is outputted, the timing should be outputted after the list.
If you want to, follow these directions instead.