-
Notifications
You must be signed in to change notification settings - Fork 36
/
Copy pathB04-rbtreesort.html
97 lines (94 loc) · 6.75 KB
/
B04-rbtreesort.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8">
<title>Bonus 04: Left-Leaning Red/Black Tree Sort</title>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css" integrity="sha384-yFRtMMDnQtDRO8rLpMIKrtPCD5jdktao2TV19YiZYWMDkUR5GQZR/NOVTdquEx1j" crossorigin="anonymous">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<link href="https://cdn.jsdelivr.net/npm/katex-copytex@latest/dist/katex-copytex.min.css" rel="stylesheet" type="text/css">
<style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
<style>
body {
font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
font-size: 14px;
line-height: 1.6;
}
</style>
<script src="https://cdn.jsdelivr.net/npm/katex-copytex@latest/dist/katex-copytex.min.js"></script>
</head>
<body>
<h1 id="bonus-04-left-leaning-redblack-tree-sort">Bonus 04: Left-Leaning Red/Black Tree Sort</h1>
<p>For this assignment you will be implementing Tree Sort using a Red/Black Tree</p>
<h2 id="the-algorithm">The Algorithm</h2>
<p>Given an array <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>A</mi><mo>=</mo><mo stretchy="false">{</mo><mi>x</mi><mo>∈</mo><mi>z</mi><mi mathvariant="normal">∣</mi><mo>−</mo><mn>100</mn><mo separator="true">,</mo><mn>000</mn><mo>≤</mo><mi>x</mi><mo>≤</mo><mn>100</mn><mo separator="true">,</mo><mn>000</mn><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">A = \{x \in \mathbb{z} | -100,000 \leq x \leq 100,000 \}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault">A</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">∈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.04398em;">z</span></span><span class="mord">∣</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8388800000000001em;vertical-align:-0.19444em;"></span><span class="mord">1</span><span class="mord">0</span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">0</span><span class="mord">0</span><span class="mord">0</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.7719400000000001em;vertical-align:-0.13597em;"></span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mord">0</span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">0</span><span class="mord">0</span><span class="mord">0</span><span class="mclose">}</span></span></span></span></p>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">treesort</span><span class="hljs-params">(A)</span> -> <span class="hljs-keyword">None</span>:</span>
tree = RBTree()
<span class="hljs-comment"># Insert all of the elements into a BST</span>
<span class="hljs-keyword">for</span> element <span class="hljs-keyword">in</span> A:
tree.insert(element)
<span class="hljs-comment"># Traverse the tree replacing elements in A</span>
i = <span class="hljs-number">0</span>
<span class="hljs-keyword">for</span> element <span class="hljs-keyword">in</span> A.traverse():
A[i] = element
i += <span class="hljs-number">1</span>
</div></code></pre>
<h2 id="instructions">Instructions</h2>
<p>This assignment will be hosted on Github Classroom.</p>
<ol>
<li>Register for the assignment on our Github Classroom using <a href="https://classroom.github.com/a/5YjTBf1O">this link</a></li>
<li>Clone the repository to your machine
<ol>
<li>Open a terminal</li>
<li>Navigate to your algorithms folder</li>
<li>Go to the parent directory (<code>cd ..</code>)</li>
<li>Clone the repository to this location (<code>git clone <your repository link here></code>)</li>
</ol>
</li>
<li>Getting things in order
<ol>
<li>Open your new folder in VS Code</li>
<li>Begin by creating a new file <code>source/Sorts/balancedtree.cpp</code>, populated with a definition for <code>sort</code></li>
<li>Check your work by compiling and running your code (<code>make balancedtree</code>)</li>
<li>Commit and push your work.</li>
</ol>
</li>
<li>Implement the Algorithm <strong>Commit and Push your work after each task</strong>
<ol>
<li>Begin by creating pseudocode for your approach in the docstring</li>
<li>Implement this pseudocode in C++</li>
<li>Analyze your work and provide the best / worst-case analysis</li>
</ol>
</li>
<li>Submit your work (<code>git add . && git commit -m "Done" && git push</code></li>
</ol>
<h2 id="grading">Grading</h2>
<table>
<thead>
<tr>
<th>Criteria</th>
<th>Points</th>
</tr>
</thead>
<tbody>
<tr>
<td>Functional Correctness</td>
<td>80</td>
</tr>
<tr>
<td>Analysis</td>
<td>10</td>
</tr>
<tr>
<td>Quality</td>
<td>10</td>
</tr>
</tbody>
</table>
<h2 id="submission">Submission</h2>
<p>Submissions are handled by Github Classroom.
Submissions after the deadline are not graded.</p>
</body>
</html>