Class 46: An Introduction to Sorting

Held: Tuesday, April 25, 2006

Summary: Today we begin to consider the problem of Sorting, putting elements of a collection in order. Sorting is one of the fundamental problems of computing.

Related Pages:

• EBoard.
• Sample Code.

Assignments

• Homework 16: Approximate String Matching.

Notes:

• We'll try the mini-Titular Head again today.

Overview:

• The Problem of Sorting.
• Carefully Specifying Sorting Methods.
• Testing Sorting Methods.

Sorting

• Sorting is the problem of putting the elements of a collection in order.
• There are a variety of ways to express the problem of sorting. These given different kinds of sorting algorithms.
• What kind of collections do we sort?
  • Arrays
  • Vectors
  • Sequenced Lists
• Do we return a new, sorted, collection, or do we sort in place (changing the parameter collection)?
• How do we compare elements?
  • Using the "normal order" for the objects (as governed by the compareTo method)
  • Using an external comparator
• It is sometimes useful to ask whether a sort is stable. In a stable sort, if A precedes B in the original collection and A is less than or equal to B, then A precedes B in the sorted collection.

Specifying Sorting

• How do we specify the problem of sorting? We'll look at some of your answers.

Testing

• How would we test a sorter? We'll develop an answer in class.