Lab 4 Solution

$30.00

Category: Tag:

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

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:

  1. SortTimer.java

  1. DoublingRatio.java

  1. CompareSorts.java

  1. random.pdf

  1. fewkeys.pdf

  1. equal.pdf

  1. sorted.pdf

  1. rsorted.pdf

Spring 2015 3 of 3


error: Content is protected !!