-
Notifications
You must be signed in to change notification settings - Fork 32
Expand file tree
/
Copy pathcs3003mergeSortLectureGuideLine.md.html
More file actions
229 lines (215 loc) · 14.6 KB
/
cs3003mergeSortLectureGuideLine.md.html
File metadata and controls
229 lines (215 loc) · 14.6 KB
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>cs3003mergeSortLectureGuideLine</title>
<link rel="stylesheet" href="https://stackedit.io/style.css" />
</head>
<body class="stackedit">
<div class="stackedit__left">
<div class="stackedit__toc">
<ul>
<li><a href="#merge-sort">Merge Sort</a></li>
<li><a href="#context-setting">Context setting</a></li>
<li><a href="#agenda">Agenda</a></li>
<li><a href="#pre-req-quiz">Pre-req quiz</a>
<ul>
<li><a href="#interactive-coding">Interactive Coding</a></li>
<li><a href="#stage---1">Stage - 1</a></li>
<li><a href="#stage-2">Stage 2</a></li>
<li><a href="#merge-sort-description">Merge Sort Description</a></li>
<li><a href="#algorithm">Algorithm</a></li>
<li><a href="#source-code">Source code</a></li>
<li><a href="#part-2">Part 2</a></li>
<li><a href="#summary">Summary</a></li>
<li><a href="#last-2-minute">Last 2 Minute</a></li>
<li><a href="#program-file-for-demo">Program File for Demo</a></li>
<li><a href="#solve-the-million-element-merge-sort">Solve the Million Element Merge Sort</a></li>
</ul>
</li>
</ul>
</div>
</div>
<div class="stackedit__right">
<div class="stackedit__html">
<h1 id="merge-sort">Merge Sort</h1>
<p><em>Lecture Guidelines</em></p>
<h1 id="context-setting">Context setting</h1>
<p>Unit 4 -> Lists, Tuples and Dictionaries -> Illustrative Programs</p>
<ul>
<li>It is very important to use a data type in a real-world case, to understand its true value and benefit.</li>
<li>We are covering three types of sorts
<ul>
<li><strong>Comparison</strong> Algorithms - Insertion Sort and Selection Sort</li>
<li><strong>Divide and Conquer</strong> Algorithms - Merge Sort, Quick Sort</li>
</ul>
</li>
</ul>
<h1 id="agenda">Agenda</h1>
<ul>
<li>Over the next 20 minutes, we shall see how lists can be used to implement <strong>Merge Sort</strong></li>
</ul>
<h1 id="pre-req-quiz">Pre-req quiz</h1>
<ul>
<li>
<p>Are you ready?</p>
<ul>
<li>Known to Unknown</li>
</ul>
</li>
<li>
<p>Best practice of a engineering student is to come prepared for the class.</p>
<ul>
<li>You must spend at least 2 hours reviewing the material taught in class, and preparing for the class</li>
</ul>
</li>
<li>
<p>Quiz</p>
<ul>
<li>44+ MCQ in Online Socrative portal
<ul>
<li>Immediate feedback</li>
</ul>
</li>
<li>Paper based<br>
- Show of hands? How many completed it? Attempted it?</li>
</ul>
</li>
<li>
<p><a href="http://j.mp/mergeListCC">http://j.mp/mergeListCC</a></p>
</li>
</ul>
<h2 id="interactive-coding">Interactive Coding</h2>
<h2 id="stage---1">Stage - 1</h2>
<ul>
<li>How to divide a sorted list into equal halves?</li>
<li>How to merge the list back into original form?</li>
</ul>
<hr>
<h2 id="stage-2">Stage 2</h2>
<ul>
<li>How to merge (combine) sorted list?</li>
<li>How to merge odd number list and even number list?</li>
<li>Use <a href="http://PythonAnywhere.com">PythonAnywhere.com</a> to zoom in and out of a <code>mergesort</code> verbose run</li>
</ul>
<p>Notice that at each level we divide the array into two halves until we get bunch of single element arrays. This is the divide portion of the divide and conquer method. Then, we start merging and sorting the smaller arrays in a series of steps which is the conquer portion of divide and conquer.</p>
<p><img src="http://bit.ly/mergeVerbose" alt="merge"></p>
<h2 id="merge-sort-description">Merge Sort Description</h2>
<p>tl;dr<img src="http://bit.ly/tamilMerge" alt="tldr"></p>
<ul>
<li>
<p>InsertSort and SelectionSort are examples of <strong>comparison</strong> sorts</p>
</li>
<li>
<p>However, MergeSort, is an example of the <strong>Divide-and-Conquer</strong> algorithm sorts</p>
<ul>
<li><strong>Divide</strong> means portioning the n-element array to be sorted into two sub-arrays of n/2 elements. If A is an array containing zero or one element, then it is already sorted. However, if there are more elements in the array, divide A into two sub-arrays, A1 and A2, each containing about half of the elements of A.</li>
<li><strong>Conquer</strong> means sorting the two sub-arrays recursively using merge sort. Combine means merging the two sorted sub-arrays of size n/2 to produce the sorted array of n elements.</li>
</ul>
</li>
</ul>
<h2 id="algorithm">Algorithm</h2>
<ul>
<li>In <code>mergesort</code>, a divide-and-conquer partitioning algorithm (which more often requires extra memory), the input array is divided in two halves, calls itself recursively for the two halves and then merges the two sorted halves. The <code>merge()</code> function is used for merging two halves.</li>
</ul>
<p>The basic steps in the recursive MergeSort Algorithm is as follows:</p>
<pre><code>Func MERGESORT:
input (unsorted list of elements) `ulist`
output (sorted list of elements) `slist`
- TERMINAL CASE:
- if size of list is 0 or 1, return (since it is sorted)
- Split the unsorted list (`ulist`) into equal sublists: left sublist and right sublist
- Recursively call MergeSort on the left sublist (`leftA`)
- Recursively call MergeSort on the right sublist (`leftB`)
- Merge the sorted left and sorted right sublists to form one sorted list
- Return the sorted list (`slist`)
</code></pre>
<h2 id="source-code">Source code</h2>
<p>Visualize at <a href="http://tinyurl.com/visualMerge">http://tinyurl.com/visualMerge</a></p>
<pre class=" language-python"><code class="prism language-python"><span class="token comment"># a helper function for the mergesort function</span>
<span class="token comment"># function to merge already sorted lists</span>
<span class="token keyword">def</span> <span class="token function">merge</span><span class="token punctuation">(</span>A<span class="token punctuation">,</span> B<span class="token punctuation">)</span><span class="token punctuation">:</span>
C <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
<span class="token keyword">while</span> A <span class="token operator">and</span> B<span class="token punctuation">:</span>
candidate <span class="token operator">=</span> <span class="token punctuation">(</span>A <span class="token keyword">if</span> A<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator"><</span> B<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token keyword">else</span> B<span class="token punctuation">)</span><span class="token punctuation">.</span>pop<span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span>
C<span class="token punctuation">.</span>append<span class="token punctuation">(</span>candidate<span class="token punctuation">)</span>
<span class="token comment"># pick up the residual elements in A or B </span>
<span class="token keyword">return</span> C <span class="token operator">+</span> A <span class="token operator">+</span> B
<span class="token keyword">def</span> <span class="token function">mergesort</span><span class="token punctuation">(</span>ulist<span class="token punctuation">)</span><span class="token punctuation">:</span>
<span class="token keyword">if</span> <span class="token builtin">len</span><span class="token punctuation">(</span>ulist<span class="token punctuation">)</span> <span class="token operator"><=</span> <span class="token number">1</span><span class="token punctuation">:</span>
<span class="token keyword">return</span> ulist
mid <span class="token operator">=</span> <span class="token builtin">len</span><span class="token punctuation">(</span>ulist<span class="token punctuation">)</span><span class="token operator">//</span><span class="token number">2</span>
leftA <span class="token operator">=</span> ulist<span class="token punctuation">[</span><span class="token punctuation">:</span>mid<span class="token punctuation">]</span>
rightB <span class="token operator">=</span> ulist<span class="token punctuation">[</span>mid<span class="token punctuation">:</span><span class="token punctuation">]</span>
sortedA <span class="token operator">=</span> mergesort<span class="token punctuation">(</span>leftA<span class="token punctuation">)</span>
sortedB <span class="token operator">=</span> mergesort<span class="token punctuation">(</span>rightB<span class="token punctuation">)</span>
slist <span class="token operator">=</span> merge<span class="token punctuation">(</span>sortedA<span class="token punctuation">,</span> sortedB<span class="token punctuation">)</span>
<span class="token keyword">return</span> slist
<span class="token comment"># test cases</span>
<span class="token keyword">assert</span> <span class="token punctuation">(</span>merge<span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">10</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">10</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
alist <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">6</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">8</span><span class="token punctuation">,</span> <span class="token number">7</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">]</span>
<span class="token keyword">print</span><span class="token punctuation">(</span>mergesort<span class="token punctuation">(</span>alist<span class="token punctuation">)</span><span class="token punctuation">)</span>
<span class="token comment"># [1, 2, 3, 4, 5, 6, 7, 8]</span>
</code></pre>
<h2 id="part-2">Part 2</h2>
<p><em>Break Activity for the 20th min</em> which also helps students review what was covered until now.</p>
<ul>
<li>Lead with the question: <strong>Can you improve on the above logic?</strong> How can you do it? Please discuss with your immediate neighbour.
<ul>
<li>Refer to the last question of the Pre-requisite Quiz
<ul>
<li>Ask your faculty for more clues</li>
</ul>
</li>
</ul>
</li>
</ul>
<h2 id="summary">Summary</h2>
<ol>
<li>We incrementally developed MergeSort in a “demo mode”</li>
<li>We arrived at the pseudo code</li>
<li>We wrote the equivalent code for MergeSort</li>
</ol>
<p>The beauty of MergeSort is that regardless of the list and how badly it is sorted, O(n) is <code>nlog(n)</code> which is favourable among almost most sorting algorithms.</p>
<h2 id="last-2-minute">Last 2 Minute</h2>
<ul>
<li>
<p>respond to Questions from Students</p>
<ul>
<li>review the relevant Question Paper snippets</li>
<li>Ask 1 or more students questions from Pre-requisites</li>
<li>Practice your MergeSort code on <a href="http://j.mp/mergeSortCC">http://j.mp/mergeSortCC</a></li>
</ul>
</li>
<li>
<p>Review Pre-requisites for Histogram (next class)</p>
</li>
</ul>
<h2 id="program-file-for-demo">Program File for Demo</h2>
<p>Modify this file as you deem fit to demonstrate on <a href="http://PythonAnywhere.com">PythonAnywhere.com</a> or on the mu editor</p>
<ul>
<li><a href="http://j.mp/mergePAW">http://j.mp/mergePAW</a></li>
<li>This is the script I use in my sample video <a href="http://bit.ly/mergeVideo">http://bit.ly/mergeVideo</a></li>
</ul>
<h2 id="solve-the-million-element-merge-sort">Solve the Million Element Merge Sort</h2>
<ul>
<li>Use <a href="http://ras.am/">http://ras.am</a> (yes, RASAM!) to get to the CyberDojo server.
<ul>
<li>Use <strong>elzm6m</strong> as the session ID.</li>
<li>Use <a href="http://KG.id">KG.id</a> file to claim the Avatar that is assigned to you.</li>
</ul>
</li>
</ul>
<pre class=" language-python"><code class="prism language-python"><span class="token keyword">def</span> <span class="token function">test_a_million_mostly_sorted_elements</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
<span class="token triple-quoted-string string">'''1_000_000 number of elements, mostly sorted'''</span>
alist <span class="token operator">=</span> <span class="token builtin">list</span><span class="token punctuation">(</span><span class="token builtin">range</span><span class="token punctuation">(</span>950_000<span class="token punctuation">)</span><span class="token punctuation">)</span>
sublist <span class="token operator">=</span> <span class="token builtin">list</span><span class="token punctuation">(</span><span class="token builtin">range</span><span class="token punctuation">(</span>950_000<span class="token punctuation">,</span> 1_000_000<span class="token punctuation">)</span><span class="token punctuation">)</span>
random<span class="token punctuation">.</span>shuffle<span class="token punctuation">(</span>sublist<span class="token punctuation">)</span>
alist <span class="token operator">+=</span> sublist
<span class="token keyword">assert</span> mergesort<span class="token punctuation">(</span>alist<span class="token punctuation">,</span> <span class="token boolean">True</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token builtin">list</span><span class="token punctuation">(</span><span class="token builtin">range</span><span class="token punctuation">(</span>1_000_000<span class="token punctuation">)</span><span class="token punctuation">)</span>
</code></pre>
</div>
</div>
</body>
</html>