-
Notifications
You must be signed in to change notification settings - Fork 36
/
Copy pathA04-advanced-sort.html
131 lines (126 loc) · 4.31 KB
/
A04-advanced-sort.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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8">
<title>Assignment 04: Advanced Sorting</title>
<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">
<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>
</head>
<body>
<h1 id="assignment-04-advanced-sorting">Assignment 04: Advanced Sorting</h1>
<p>For this assignment you must implement and analyze one advanced sorting algorithm of your choosing.
Your algorithm cannot be the same as the one used in the previous assignment.</p>
<p>You may select any algorithm from the following list:</p>
<h2 id="distribution-sorts">Distribution Sorts</h2>
<ul>
<li>Spreadsort</li>
<li>Radix Sort</li>
<li>Flashsort</li>
<li>Pigeonhole Sort</li>
<li>Bucket Sort</li>
<li>Postman Sort</li>
</ul>
<h2 id="comparison-sorts">Comparison Sorts</h2>
<ul>
<li>In-place MergeSort</li>
<li>Introsort</li>
<li>TimSort</li>
<li>CubeSort</li>
<li>ShellSort</li>
<li>CycleSort</li>
<li>Library Sort</li>
<li>Patience Sorting</li>
<li>SmoothSort</li>
<li>StrandSort</li>
<li>Block Sort</li>
<li>Topological Sort</li>
<li>Curve sort</li>
</ul>
<p>The student with the fastest sorting algorithm will receive 50 bonus points, second fastest will receive 30, third will receive 20.</p>
<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/0-TyqToY">this link</a>
<ol>
<li>Be sure to select your name from the list to link your Github to the class roster!</li>
</ol>
</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>)
<ol>
<li>Be sure to use the link for <strong>your copy</strong> of the repository for the assignment</li>
</ol>
</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/advanced.cpp</code>.
<ol>
<li>Within this file, create the definition for your advanced sorting algorithm: <code>void sort(int*, int) {}</code></li>
</ol>
</li>
<li>Check your work by compiling and running your code (<code>make advanced</code>)</li>
<li>Make sure the code compiled and ran, and that the unit tests for your function failed.</li>
<li>Commit and push these changes (<code>git add . && git commit -m "<message>" && git push</code>)</li>
<li>Check the online copy of your repository to make sure these changes were actually pushed</li>
</ol>
</li>
<li>Implement your algorithm (80 points)
<ol>
<li>Write pseudocode for your algorithm in the docstring.</li>
<li>Commit and push this pseudocode (<code>git add . && git commit -m "<message>" && git push</code>)</li>
<li>Implement your pseudocode in C++</li>
<li>Pass all unit tests</li>
<li>Commit and push your code (<code>git add . && git commit -m "Done" && git push</code>)</li>
</ol>
</li>
<li>Analyze your work (10 points)
<ol>
<li>Provide your algorithms' Big-Oh, Omega, and Theta notation</li>
</ol>
</li>
</ol>
<h2 id="grading">Grading</h2>
<table>
<thead>
<tr>
<th>Criteria</th>
<th>Points</th>
</tr>
</thead>
<tbody>
<tr>
<td>Functionality</td>
<td>70</td>
</tr>
<tr>
<td>Analysis</td>
<td>10</td>
</tr>
<tr>
<td>Quality</td>
<td>20</td>
</tr>
</tbody>
</table>
<h2 id="submission">Submission</h2>
<p>To submit this assignment, simply commit and push your work to your assignment repository.
Your last submission before the deadline will be graded.</p>
</body>
</html>