Difference between revisions of "Computer Science/61b/Homework/hw8/GRADER"
< Computer Science | 61b | Homework | hw8
m (formatting) |
|||
| Line 2: | Line 2: | ||
==Part III== | ==Part III== | ||
| − | Running time | + | Running time comparisons – all tests performed on [http://inst.eecs.berkeley.edu/cgi-bin/clients.cgi?choice=13&string= quasar.cs]. |
| − | + | List size mergesort quicksort | |
| − | 10 | + | 10 0 0 |
| − | 100 | + | 100 3 3 |
| − | 1,000 | + | 1,000 42 41 |
| − | 10,000 120 | + | 10,000 120 83 |
| − | 100,000 665 | + | 100,000 665 610 |
| − | 1,000,000 12928 | + | 1,000,000 12928 6947 |
| − | 10,000,000 273224 | + | 10,000,000 273224 130750 |
==Part IV== | ==Part IV== | ||
Revision as of 07:00, 22 September 2007
GRADER file for Homework 8
Part III
Running time comparisons – all tests performed on quasar.cs.
List size mergesort quicksort 10 0 0 100 3 3 1,000 42 41 10,000 120 83 100,000 665 610 1,000,000 12928 6947 10,000,000 273224 130750
Part IV
Is mergesort stable? Yes.
Why or why not? When we have two equal keys, we always first insert the key from the left, which came from the left side of the original list. As a result, the key that came from the left stays on the left.
Is quicksort stable? Yes.
Why or why not? We remove keys one by one from left to right. Equivalent keys get inserted in the same order, one by one, into the qEquals queue, which remains untouched after this. When we append qSmall, qEquals, and qLarger, we again work from left to right, and the order is maintained.
