http://www.lensovet.net/~sysadmin/w/index.php?action=history&feed=atom&title=Computer_Science%2F61b%2FHomework%2Fhw8%2FGRADER
Computer Science/61b/Homework/hw8/GRADER - Revision history
2026-05-03T21:06:27Z
Revision history for this page on the wiki
MediaWiki 1.31.16
http://www.lensovet.net/~sysadmin/w/index.php?title=Computer_Science/61b/Homework/hw8/GRADER&diff=24365&oldid=prev
Lensovet: Lensovet moved page CS/61b/Homework/hw8/GRADER to Computer Science/61b/Homework/hw8/GRADER
2023-02-20T03:51:35Z
<p>Lensovet moved page <a href="/~sysadmin/w/CS/61b/Homework/hw8/GRADER" class="mw-redirect" title="CS/61b/Homework/hw8/GRADER">CS/61b/Homework/hw8/GRADER</a> to <a href="/~sysadmin/w/Computer_Science/61b/Homework/hw8/GRADER" title="Computer Science/61b/Homework/hw8/GRADER">Computer Science/61b/Homework/hw8/GRADER</a></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<tr class="diff-title" lang="en">
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">Revision as of 03:51, 20 February 2023</td>
</tr><tr><td colspan="2" class="diff-notice" lang="en"><div class="mw-diff-empty">(No difference)</div>
</td></tr></table>
Lensovet
http://www.lensovet.net/~sysadmin/w/index.php?title=Computer_Science/61b/Homework/hw8/GRADER&diff=4053&oldid=prev
Lensovet: moved CS 61b/Homework/hw8/GRADER to CS/61b/Homework/hw8/GRADER: fix cs 61b hierarchy
2010-11-14T06:00:20Z
<p>moved <a href="/~sysadmin/w/CS_61b/Homework/hw8/GRADER" class="mw-redirect" title="CS 61b/Homework/hw8/GRADER">CS 61b/Homework/hw8/GRADER</a> to <a href="/~sysadmin/w/CS/61b/Homework/hw8/GRADER" class="mw-redirect" title="CS/61b/Homework/hw8/GRADER">CS/61b/Homework/hw8/GRADER</a>: fix cs 61b hierarchy</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<tr class="diff-title" lang="en">
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">Revision as of 06:00, 14 November 2010</td>
</tr><tr><td colspan="2" class="diff-notice" lang="en"><div class="mw-diff-empty">(No difference)</div>
</td></tr></table>
Lensovet
http://www.lensovet.net/~sysadmin/w/index.php?title=Computer_Science/61b/Homework/hw8/GRADER&diff=3253&oldid=prev
Lensovet: formatting
2007-09-22T07:00:05Z
<p>formatting</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 07:00, 22 September 2007</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2" >Line 2:</td>
<td colspan="2" class="diff-lineno">Line 2:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Part III==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Part III==</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Running time <del class="diffchange diffchange-inline">comparisons - all </del>tests performed on http://inst.eecs.berkeley.edu/cgi-bin/clients.cgi?choice=13&string= quasar.cs].</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Running time <ins class="diffchange diffchange-inline">comparisons – all </ins>tests performed on <ins class="diffchange diffchange-inline">[</ins>http://inst.eecs.berkeley.edu/cgi-bin/clients.cgi?choice=13&string= quasar.cs].</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">  </del>List size mergesort quicksort</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> </ins>List size <ins class="diffchange diffchange-inline"> </ins>mergesort <ins class="diffchange diffchange-inline"> </ins>quicksort</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>   10 <del class="diffchange diffchange-inline"> </del>0 <del class="diffchange diffchange-inline"> </del>0</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>   10 <ins class="diffchange diffchange-inline">          </ins>0 <ins class="diffchange diffchange-inline">        </ins>0</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>   100 <del class="diffchange diffchange-inline"> </del>3 <del class="diffchange diffchange-inline"> </del>3</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>   100 <ins class="diffchange diffchange-inline">          </ins>3 <ins class="diffchange diffchange-inline">        </ins>3</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>   1,000 <del class="diffchange diffchange-inline"> </del>42 <del class="diffchange diffchange-inline"> </del>41 <del class="diffchange diffchange-inline"> </del></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>   1,000 <ins class="diffchange diffchange-inline">        </ins>42 <ins class="diffchange diffchange-inline">        </ins>41</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>   10,000 120 <del class="diffchange diffchange-inline"> </del>83</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>   10,000 <ins class="diffchange diffchange-inline">      </ins>120 <ins class="diffchange diffchange-inline">      </ins>83</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>   100,000 665 <del class="diffchange diffchange-inline"> </del>610</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>   100,000 <ins class="diffchange diffchange-inline">      </ins>665 <ins class="diffchange diffchange-inline">      </ins>610</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>   1,000,000 12928 <del class="diffchange diffchange-inline"> </del>6947</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>   1,000,000 <ins class="diffchange diffchange-inline">    </ins>12928 <ins class="diffchange diffchange-inline">    </ins>6947</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>   10,000,000 273224 <del class="diffchange diffchange-inline"> </del>130750</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>   10,000,000 <ins class="diffchange diffchange-inline">  </ins>273224 <ins class="diffchange diffchange-inline">    </ins>130750</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Part IV==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Part IV==</div></td></tr>
</table>
Lensovet
http://www.lensovet.net/~sysadmin/w/index.php?title=Computer_Science/61b/Homework/hw8/GRADER&diff=3252&oldid=prev
Lensovet at 06:56, 22 September 2007
2007-09-22T06:56:10Z
<p></p>
<p><b>New page</b></p><div>GRADER file for Homework 8<br />
<br />
==Part III==<br />
Running time comparisons - all tests performed on http://inst.eecs.berkeley.edu/cgi-bin/clients.cgi?choice=13&string= quasar.cs].<br />
<br />
List size mergesort quicksort<br />
10 0 0<br />
100 3 3<br />
1,000 42 41 <br />
10,000 120 83<br />
100,000 665 610<br />
1,000,000 12928 6947<br />
10,000,000 273224 130750<br />
<br />
==Part IV==<br />
''Is mergesort stable?'' Yes.<br />
<br />
''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.<br />
<br />
''Is quicksort stable?'' Yes.<br />
<br />
''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.</div>
Lensovet