1,277
edits
Changes
no edit summary
GRADER file for Homework 8
==Part III==
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 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.
==Part III==
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 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.