Held: Tuesday, 26 November 2013

Back to Outline 46 - Introduction to Sorting. On to Outline 48 - 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
• EBoard (Source) (HTML) (PDF)

Overview

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

Administrivia

• Note: The next time we have a fire alarm during a quiz, I'm not going to use the "everyone gets a ten" policy.
• Upcoming extra credit opportunities:
  • Tuesday, November 26, 4:15 p.m., JRC 209 a gaming event with the game [d0x3d!] Popcorn will be served.
  • Any self-care week activity during purgatory week.
  • One Grinnell rally on December 4 at 4pm.

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 isertion sort.
• Be prepared to reflect.