Outline 26: An Introduction to Sorting
Held: Monday, 13 October 2014
Back to Outline 25 - Using Java from the Command Line.
On to Outline 27 - Quadratic Sorts.
Summary
We consider the well-known problem of sorting. Along the way, we consider
some issues in testing and object-oriented design.
Related Pages
Overview
- The problem of sorting.
- An object-oriented approach.
- Testing our sorting algorithm.
Administrivia
- New lab partners (although it won't matter so much today)!
- Office hours
- Normal this week (MThF 1:45-3:15; walking 1:15-1:45)
- I may be hanging out by the Grill during class prep times
- I've added a variety of questions and answers to the exam. (Yes, it
takes time to do so. I think it's worthwhile.)
- I've slightly cleaned up the eboards from Wednesday and Friday since
so many people could not attend those classes.
Upcoming Work
- Exam 1 due Thursday.
- Required prologue due tonight!
- Yes, I can send you your prologue.
- Required epilogue due Friday night.
- Reading for Tuesday:
- Sorting Basics
- The reading recaps and extends what we'll discuss in class today.
Notes from the Prologues
- Please don't write "suck up" answers on the prologues. E.g., "Oh, this
question will give me the opportunity to learn much more about an important
topic." (paraphrased)
- Many of you are saying that you should write
average
before
writing the tests. But that's backwards. If you write the tests first,
and think about the corner cases, you'll be much more likely to
understand likely problems.
- You should have learned from an early homework that you can't just add
up the values and then divide for the averaging problem; integer (or
long) overflow will kill you.
- Loop invariants are a way to think more carefully about the state of the
program while it is running. (They are also useful for proving things
correct.) In general, we'll use pictorial loop invariants for arrays,
but also try to write them formally.
- When describing the values in an array, we may use a series of
question marks to indicate that we know nothing about the values
in the part of the array.
- In general, Big-O should be intuitive if you think about how algorithms
work.
- If you have to shift the elements in an array, that shifting will
generally take O(n) steps
- If you have to get the ith element of a linked list, that will take
O(i) steps.
Extra Credit
Academic
- BCC Faculty Chat, Tuesday, October 14, 7pm
- Thursday Extras, 4:30 p.m. Thursday, October 16, Grad School in CS
- CS Table Friday (Day PDR): TBD
Peer Support
- Ajuna's Radio show Mondays at 8pm. Listen to African music
- Ezra's Radio show Thursdays at midnight. Radio melodrama.
Project Planning
Question: In the second half of the semester, you will do a project. There
are three possibilities right now.
- Set up Ushahidi for someone else on campus.
- Write a JSON parser.
- Build something that creates sport schedules. (We even have a
client for this one.)
We'll do a quick discussion and then come back to the question immediately
after break.
The problem of sorting
- Goal: Given a collection of values, put them in order.
- How do you decide what order?
- Sometimes we use the natural ordering.
- Sometimes we use a comparator.
An object-oriented approach
- We'll build a
Sorter
interface.
- Will the individual objects ever need more than one copy?
Probably not. We'll see how to handle that issue later.
- The basic method: Sort an array of T's using an appropriate comparator.
- I'll ask you to fill in the blanks (preconditions, postconditions,
etc.)
Testing sorters
- How do we test a sorter?
- Three basic approaches:
- Systematically generate a lot of samples and see that it works
on all of them
- Randomly generate a lot of samples and see that it works on
all of them
- Perhaps do a few special cases
- How do we know that a sort method has succeeded?
- The result is in order
- The result is a permutation of the original array
- We can check these by writing
inOrder
and isPermutation
predicates, but those are a pain.
- A better strategy:
- Start with a sorted array.
- Make a copy.
- Permute the copy.
- Sort the permuted copy.
- Compare to the original array.
- For the random samples approach, we just need a "randomly permute"
method.
- For the systematic approach, we might want to make all permutations.
But how?
Sam's favorite permutation algorithm
- Assumptions:
- You have an action you want to do with each permutation of an array.
- Once you've done the action, we can re-permute the array.
- The action can be specified as a function. (We might even use a
Functional Interface in Java.)
- We can treat all values as independent. (E.g., if we get the permtuations
of [2,2,3], we will get six permutations: [2a,2b,3], [2b,2a,3],
[2a,3,2b], [2b,3,2a], [3,2a,2b], and [3,2b,2a])
we will see each v
- Inputs: Array, Function.
- Key idea: You want to do a lot of swapping. You can do that more
systematically using recursion.
- Helper function Inputs: Array, Function, Upper index of subarray to
permute.
Here's the algorithm in pseudocode
// Apply fun to every permutation of values
useAllPermutations(values, fun)
useAllPermutations(values, fun, values.length)
// Apply fun to all permutations of values in which the
// elements at position pos and higher are not changed
useAllPermutations(values, fun, pos)
// Base case: No elements to change
if (pos == 0)
fun(values)
// Normal case: Lots of work!
// Every value has to appear in position pos-1 for some set
// of permutations
for i from 0 to pos-1
// So put it in that position
values.swap(i,pos-1)
// We then need every permutation of the remaining elements
useAllPermutations(values, fun, pos-1)
// Swap it back for the next round
values.swap(i,pos-1)