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

• Code (tbd)
• EBoard 26 (Source 26) (HTML 26)

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)