Lab 4 Solution

Section Readings: 2.1, 2.2




Problem 1. (Sort Timer Data Type) Implement the comparable data type SortTimer that can be used to compare sorting algorithms, and has the following API:







public class S or tT i me r i m p l e m e n t s Comparable < SortTimer




Co ns tr uc t a So rt Ti me r object given the name of the sorting



algorithm , an input array , and the number of times to sort .



public So rt Ti me r ( String alg , C o m p a r a b l e [] a , int T )




// Sort a fresh copy of a[] for each of T times and record the




average time . public void sort ()



Compare this object to the other by the average time to sort . public int co mp ar eT o ( So rt Ti me r other )



Return a string r e p r e s e n t a t i o n of this object .



public String toString ()







$ java S or tT im er




Shell , 0 . 0 1 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 1




Selection , 0 . 2 1 1 8 9 9 9 9 9 9 9 9 9 9 9 9 8




Insertion , 0.2253




Problem 2. (Doubling Ratio Experiment) Write a program DoublingRatio that takes the name of a sorting algorithm as a command-line argument and performs doubling ratio experiment for the algorithm, using arrays of random Double values as inputs. Start at N = 1000 and go all the way up to N = 64000 (i.e., consider six doublings), and print N, the time in seconds, and the ratio of current versus previous time as N doubles. Hint: See DoublingRatio from Section 1.4. Your program must support eight sorting algorithms: Insertion, Selection, Shell, Merge, Quick, Quick3way, Heap, and System. Use your program to verify the claim that insertion sort and selection sort are quadratic for random inputs.







$ java D o u b l i n g R a t i o I ns er ti on




1000
0.0
0.6






2000
0.1
2.7
4000
0.1
2.2
8000
0.2
1.6
16000
0.5
2.9
32000
2.0
3.8
64000
8.1
4.0









java D o u b l i n g R a t i o S el ec ti on



10000.00.8




20000.14.0




40000.11.6




8000 0.2 1.5




16000 0.7 3.6




32000 2.8 3.9







Spring 2015 1 of 3


CS210
Lab 4
Swami Iyer






64000
11.04.0





java D o u b l i n g R a t i o System



10000.02.3




20000.00.4




4000
0.0
2.3
8000
0.0
2.4






16000
0.1
3.8
32000
0.1
1.9
64000
0.1
0.9









Problem 3. (Compare Sorting Algorithms) Implement a program CompareSorts that takes the name of the le containing data (integers) to sort and the number of times (per algorithm) to sort as command-line arguments, and uses SortTimer from Problem 2 to instrument each of the eight sorting algorithms. The program should print the name of the algorithm and the average time it takes to sort, ordered by the latter. Hint: Study the code in SortTimer.main().







$ java C o m p a r e S o r t s random . txt 10 out . txt




cat out . txt



Heap , 0 . 0 0 2 1 9 9 9 9 9 9 9 9 9 9 9 9 9 9 7




Quick3way , 0 . 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1




Quick , 0 . 0 0 5 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9




Merge , 0 . 0 1 1 1 9 9 9 9 9 9 9 9 9 9 9 9 9 8




Shell , 0 . 0 1 3 6 9 9 9 9 9 9 9 9 9 9 9 9 9 9




System , 0 . 0 3 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 6




Insertion , 0.1711




Selection , 0 . 2 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 3




Problem 4. (Compare Sorting Algorithms Visually) We want to visualize the num-bers we obtain from CompareSorts on di erent input les (let’s x the number of sorts per algorithm, i.e., the second argument, to 10): random.txt containing random num-bers, fewkeys.txt containing few unique numbers, equal.txt containing equal numbers, sorted.txt containing sorted numbers, and rsorted.txt containing reverse-sorted num-bers. A plot of the numbers from out.txt from Problem 3 is shown below. Use a program of your choice to generate similar plots for each of the ve input les mentioned above and save them in PDF format with names random.pdf, fewkeys.pdf, equal.pdf, sorted.pdf, and rsorted.pdf.


























































Spring 2015 2 of 3
CS210 Lab 4 Swami Iyer































time in seconds










0.25







0.20







0.15







0.10







0.05




0.00




Heap



































































Quick3way







random























































Quick
Merge
Shell
System
Insertion Selection



sorting algorithm






Feel free to use the supplied plot.py le to generate the plots, which can be done as follows:







$ java C o m p a r e S o r t s random . txt 10 | python plot . py random




But to use plot.py, you will have to install Python, NumPy, and Matplotlib on your computer, which is straightforward on the VM | you just have to run the following on the command line:







$ sudo apt - get install python - numpy python - m a t p l o t l i b python - tk




Files to Submit:




SortTimer.java



DoublingRatio.java



CompareSorts.java



random.pdf



fewkeys.pdf



equal.pdf



sorted.pdf



rsorted.pdf























Spring 2015 3 of 3