The program [login to view URL] can automatically test a sorting algorithm, that can be specified by a command line argument:
java Lab1 quicksort
(the other possibilities for command line argument the program understands are insertionsort and mergesort)
In order to run this program you need to download [login to view URL] and compile all the classes.
The program generates 5 random arrays of each size 500, 1000, 1500, ..., 10000 and records the average execution time for each size. The partial results and the averages are printed to the screeen and to a file [login to view URL] (this file has most of the lines commented away for the program gnuplot you will be using. The only interesting lines are the ones registering the averages.)
You can warm up for the lab by using Lab1 as above and then plotting the results with gnuplot:
Start gnuplot by choosing gnuplot from the programs menu. It starts a window where you can give commands to gnuplot. To exit just type exit.
Go to the directory where your data files are by typing
gnuplot> cd 'dirname'
Plot the datafiles by typing
gnuplot> plot "[login to view URL]" with lines
This will make gnuplot go fullscreen. To return to normal mode press the ESC key and then do Alt-Enter.
1)
Define a class [login to view URL] with a little main to test QuickSort for big arrays. Your program should run QuickSort for sizes 50000, 100000, 200000, 400000, 800000. You will then get in the file [login to view URL] values for T(50000), T(100000), T(200000), T(400000), T(800000). You should find out what approximation of O(N), O(N log(N)), O(N^2) fits your experiments better. This can be done by calculating T(N)/N, T(N)/Nlog(N), T(N)/N^2 for the given sizes and examining which one converges better.
Your class Experiment should extend Lab1 so that in your main you can use all the protected fields and methods (you only have to redefine main!)
2)
In this exercise you will use [login to view URL] as it is to get values for Insertion Sort, Merge Sort and Quick Sort (you will have to run the program three times, once for each algorithm).
a)Plot each of the files [login to view URL], [login to view URL] and [login to view URL] using gnuplot as indicated above
b)Plot merge and quick sort together doing
gnuplot> plot "[login to view URL]" with lines, "[login to view URL]" with lines
c)Plot all three experiments together doing
gnuplot> plot "[login to view URL]" with lines, "[login to view URL]" with lines, "[login to view URL]"
3)
Predict what the best case for insertion sort is (by analyzing the algorithm). Program an experiment to explore the execution time for insertion sort for its best case and report the results. Does the experimet confirm your prediction?
Submission:
Submission should have the following attachments:
(For Exercise 1)
Your [login to view URL]
a text file including your calculations (please, an ascii file!)
your conclusion as to what curve approximates execution time best
(For Exercise 2) The files "[login to view URL]", "[login to view URL]", and "[login to view URL]". Include also a text file explaining what you see in all the plots.
(For Exercise 3) The program and the conclusions you can draw on O(F(N)) for your data..