pythonFDP/notes/selectSortLectureGuide.md.html at master · kgisl/pythonFDP

History

253 lines (246 loc) · 16.3 KB

Raw

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

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

<!DOCTYPE html>

<html>

<head>

<title>cs3003selectSortLectureGuide</title>

</head>

<ul>

<li><a href="#selection-sort">Selection Sort</a></li>

<li><a href="#context-setting">Context setting</a></li>

<li><a href="#agenda">Agenda</a></li>

<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="#selection-sort-description">Selection Sort Description</a></li>

<li><a href="#pseudo-code">Pseudo Code</a></li>

<li><a href="#a-more-efficient-selection-sort">A More Efficient Selection Sort</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>

</ul>

</li>

</ul>

</div>

<h1 id="selection-sort">Selection Sort</h1>

Lecture outline

<h1 id="context-setting">Context setting</h1>

Unit 4 -> Lists, Tuples and Dictionaries -> Illustrative Programs

<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>Comparison Algorithms - Insertion Sort and Selection Sort</li>

<li>Divide and Conquer Algorithms - Merge Sort, Quick Sort</li>

</ul>

</li>

<li>

We have already seen the power of Lists when we covered InsertionSort

<ul>

<li>Select a <code>value</code> from the unsorted sub-list</li>

<li>Decide where to insert it in the already_sorted sub-list</li>

<li>Right shift all the values and then insert the <code>value</code></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 SelectionSort

</li>

<li>

SHOW and TELL - Show Example, And Tell Theory

<ul>

<li>versus Tell Theory, Show Example</li>

<li>a more effective style to create engagement

<ul>

<li>VERY VERY effective when you students participate</li>

<li>Even more effective when students KNOW something already</li>

</ul>

</li>

</ul>

</li>

</ul>

<pre><code>- Are you ready?

- Do you know something already

- Known to Unknown

</code></pre>

<ul>

<li><a href="http://j.mp/indexMinCC">http://j.mp/indexMinCC</a> - is the best way to be prepared for SelectionSort</li>

<li>how do you iterate over all the elements in a list, except the last one? Write the python code to do this</li>

<li>What is the value of <code>[1, 2, 3, 4][0:]</code> and <code>[1, 2, 3, 4][1:]</code> and <code>[1, 2, 3, 4][2:]</code>?</li>

<li>What is the built-in function which is used to find the minimum value of a list of numbers? Create a list containing 10 random numbers. Write the python code to find the minimum value in the list.</li>

<li>What is the list method to find out the index of a value in a list?

<ul>

<li>How many arguments does the method accept?</li>

<li>What is the second argument for?</li>

</ul>

</li>

<li>What are the ways you can swap the value in two variables?

<ul>

<li>What is the most pythonic way to do this?

<ul>

<li>Word count - Python beats Java, like crazy!</li>

</ul>

</li>

</ul>

</li>

</ul>

Show of hands as to many of you students reviewed all the above questions and have answers written down in your notebooks?

- best practice of a engineering student is to come prepared for the class. You must spend at least 2 hours reviewing the material taught in class, and preparing for the class

<h2 id="interactive-coding">Interactive Coding</h2>

<h2 id="stage---1">Stage - 1</h2>

<ol>

<li>

Example of list containing <code>[1, 2, 3, 5, 6, 4]</code>

<li>Already sorted list, except the number 4</li>

</ol>

</li>

<li>

Select the minimum value in all of the unsorted list

<li><code>1</code> is the minimum - place it in index <code>0</code></li>

<li><code>2</code> is the minimum - place it in index <code>1</code></li>

<li><code>3</code> is the minimum - place it in index <code>2</code></li>

<li><code>4</code> is the minimum - prepare to swap with 5

</ol>

</li>

<li><code>5</code> is the minimum - prepare to swap with 6

</ol>

</li>

</ol>

</li>

<li>

If necessary (<code>i != min_i</code>) swap the minimum value from the unsorted sublist with the element in the sorted sub-list

</li>

</ol>

<hr>

<h2 id="stage-2">Stage 2</h2>

<li>Define an iteration through the list, and do this for every element in the list</li>

<li>Initialize the right variables and execute the code</li>

<li>Place the entire code inside inside a function definition and call it <code>selectionsort</code></li>

</ol>

<h2 id="selection-sort-description">Selection Sort Description</h2>

<ul>

<li>In <code>selectionsort</code>, the position of the update is pre-determined, starting from the beginning of the list. We then go select the minimum value among the unsorted elements of the list, and swap it with the element in the pre-determined location.</li>

</ul>

<h2 id="pseudo-code">Pseudo Code</h2>

Have seen the example, it becomes very easy to define the pseudo code for SelectionSort

<pre><code>repeat (numOfElements - 1) times

for each of the unsorted elements

select the minimum value among them

swap minimum with first unsorted position

</code></pre>

The Python code to implement the pseudo code above:

<pre class=" language-python"><code class="prism language-python"> def selectionsort(alist):

n = len(alist)

for i in range(n-1):

unsorted = alist[i:]

smallest = min(unsorted)

min_i = alist.index(smallest, i)

alist[i],alist[min_i] = alist[min_i], alist[i]

print("intermediary", alist)

return alist

</code></pre>

Break Activity for the 20th min which also helps students review what was covered until now.

<ul>

<li>Lead with the question: Can you improve on the above logic? How can you do it? Please discuss with your immediate neighbour.

<ul>

<li>if you know how to code it, write down the code in Python as well</li>

<li>Go back and improve the pseudo code as well</li>

</ul>

</li>

</ul>

<pre class=" language-python"><code class="prism language-python">def selectionsort(alist):

n = len(alist)

# STEP 0 - iterate through the list

min_i = i

# STEP 1 - update mini_i with index

# of min value in unsorted alist[i+1:]

for j in range(i+1, n):

if alist[j] < alist[min_i]:

min_i = j

# STEP 2 - swap it with element at index 'i'

if min_i != i:

alist[i], alist[min_i] = alist[min_i], alist[i]

return alist

</code></pre>

<ul>

<li>OPTIONAL - generate a list containing tuples, where each tuple contains both the element and the index of the element in the list</li>

<li>OPTIONAL - use a built-in function to find out the tuple containing the least value in the list</li>

</ul>

<h2 id="a-more-efficient-selection-sort">A More Efficient Selection Sort</h2>

<ul>

<li>uses <code>tuples</code> and <code>list comprehension</code> to make the code very efficient and eminently readable.</li>

</ul>

<pre class=" language-python"><code class="prism language-python">def selectsort(alist):

n = len(alist)

unsorted = alist[i:]

(minval, min_i) = min((v, i) \

for i, v in enumerate(unsorted))

alist[i], alist[min_i+i] = alist[min_i+i], alist[i]

return alist

tlist = [85, 69, 12, 12, 54, 36, 45, 5]

print("unsorted", tlist)

print("sorted:", selectsort(tlist))

</code></pre>

<h2 id="summary">Summary</h2>

<ol>

<li>We incrementally developed SelectionSort in a “manual mode”</li>

<li>We arrived at the pseudo code</li>

<li>We wrote the equivalent code for SelectionSort</li>

</ol>

In reflection, SelectionSort is just the opposite of InsertionSort. The worst case complexity of this SelectionSort is <code>O(n^2)</code>

<h2 id="last-2-minute">Last 2 Minute</h2>

<ul>

<li>

respond to Questions from Students

<ul>

<li>review the relevant Question Paper snippets</li>

<li>Ask 1 or more students questions from Pre-requisites</li>

</ul>

</li>

<li>

<a href="http://j.mp/selectionSortCC">http://j.mp/selectionSortCC</a> and <a href="http://j.mp/indexMinCC">http://j.mp/indexMinCC</a>

</li>

<li>

Review <a href="http://j.mp/mergeVisual">http://j.mp/mergeVisual</a> for the next class

</li>

</ul>

<h2 id="program-file-for-demo">Program File for Demo</h2>

Modify this file as you deem fit to demonstrate on <a href="http://PythonAnywhere.com">PythonAnywhere.com</a> or on the mu editor

<ul>

<li><a href="http://j.mp/selectPAW">http://j.mp/selectPAW</a></li>

<li>This is the script I use in my sample video <a href="http://bit.ly/selectionVideo2">http://bit.ly/selectionVideo2</a></li>

</ul>

</div>

</body>

</html>

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

FilesExpand file tree

selectSortLectureGuide.md.html

Latest commit

History

selectSortLectureGuide.md.html

File metadata and controls