Held: Friday, 1 November 2013
Back to Outline 32 - Merge Sort.
On to Outline 34 - An Introduction to Linear Structures.
Summary
We consider Quicksort, one of the more interesting sorting algorithms.
Related Pages
Overview
- Analyzing mergesort, revisited.
- Iterative mergesort.
- A quick introduction to Quicksort.
Administrivia
- Reminder: Redos of exam 2 are due at 10:30 p.m. tonight.
- I'll leave time for questions on HW8.
- We should discuss the project.
- There's a roundtable on the digital commons at 10 a.m.
on Tuesday, 19 November.
- Upcoming extra credit opportunities:
- CS Table, today: Ambient Belonging
- One Grinnell Prize Event next week
- Learning from Alumni, next week: Shitanshu Aggarwal '11
- CS Extra next week: Internships (I think)
- Town Hall, Wednesday, November 13, noon or 7:30 p.m.
Analyzing mergesort, revisited
- We analyzed merge sort using recurrence relations. I thought that was
useful.
- I know some of my colleagues do a more pictorial version of the analysis,
which we'll also do.
Iterative mergesort
- Merge sort, as phrased, is a recursive algorithm
- Some folks really don't like recursion. (Our visitor from Microsoft
says that it's too complicated for some programmers to read.)
- Can we write mergesort without recursion?
- Certainly. The tree even helps.
- We order pairs of elements
- We merge ordered pairs into ordered 4-tuples
- We merge ordered 4-tupels into ordered 8-tuples
- And so on and so forth.
- You'll implement this on the homework.
Quicksort
- Divide and conquer
- Using smaller/larger as the division strategy
- Randomness helps us select an approximation of the median
- I'm bad at probabilistic analysis, so we won't do it
Lab
- In the lab, you'll implement the partition portion of Quicksort over
arrays.
