# Class 46: An Introduction to Sorting

Back to Approximate String Matching. On to Pause for Breath.

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:

Assignments

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.

Back to Approximate String Matching. On to Pause for Breath.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Tue May 9 08:31:54 2006.
The source to the document was last modified on Thu Jan 12 14:58:07 2006.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2006S/Outlines/outline.46.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu