Held: Tuesday, 28 April 2015

Back to Outline 48 - An Introduction to Sorting. On to Outline 50 - Merge Sort.

Summary

We move from our general exploration of sorting to the implementation of a particular sorting algorithm, insertion sort. We also explore how the running time for that algorithm varies based on the number of values we are sorting.

Related Pages

• Reading: Sorting
• Lab: Insertion Sort
• Morning EBoard 49 (Source a.m. 49)
• Afternoon EBoard 49 (Source p.m. 49)

Overview

• Insertion sort basics.
• Four questions about insertion sort.
• Analyzing insertion sort.

Administrivia

• Continue partners!
• Don't forget to grab a yellow card.
• Review sessions Thursday at 1:15pm and 8pm

Upcoming Work

• Projects due tonight. Read the instructions!
• Exam 4 prologue due Friday night!
• Exam 4 due Monday night.
• Lab Writeup: Exercises 2e and 4f. http://bit.ly/151-2015S-lab49
• Reading for Wednesday: Merge Sort

Extra Credit Opportunities

Academic

• PBK Convo, Wednesday.
• CS Extras Thursday, Brooks Davis on Unix stuff
• CS Table Friday, Last CS Table of the Year: Planning for next year

Peer Support (Morning Section)

• KY's radio show, "We Think We're Funny", 9-10pm Mondays
• Julia's radio show, "The Hot Box". Wednesday night/Thursday morning 1:00-2:00 a.m.
• Baseball, Saturday, Noon and 2:30, Sunday 10:00 and 12:30.

Peer Support (Afternoon Section)

• Baseball, Saturday, Noon and 2:30, Sunday 10:00 and 12:30.

Miscellaneous

• Donate to support Nepal. (List of agencies available via NYTimes)

Other Good Things (no extra credit)

Notes on the Project

• Code for saving files distributed last night.
• irgb->hsv is buggy. If you give it an inexact hue, it gives you no result.

Preparation: A Few Questions on Insertion Sort

• What is the key idea in insertion sort?
• How does insertion sort differ in lists and vectors?
• Why do we provide you with three different kinds of list-based insertion sort (and four kinds of insertion sort)?

Lab

• Do the lab on insertion sort.
• Be prepared to reflect.