Lab 4 Solution

Description

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

• 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

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

10000.02.3

20000.00.4

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.

CS210 Lab 4 Swami Iyer

Spring 2015 3 of 3