• Create BookmarkCreate Bookmark
• Create Note or TagCreate Note or Tag
• PrintPrint

In the Real World—Computer-Based Sorting and Searching

Donald E. Knuth's Sorting and Searching, volume 3 of his The Art of Computer Programming series, is the seminal work on computer algorithms (programs) to perform sorts and searches. Dr. Knuth is Professor Emeritus of The Art of Computer Programming at Stanford University, and is equally well known in the computer-based publishing industry for his TeX and METAFONT type design and typesetting programs. Addison-Wesley published the first edition of Sorting and Searching in 1973. There's a good probability that every student who was granted a computer science degree during and after the mid-1970s has a well worn copy of Knuth's classic text. Knuth updated Sorting and Searching with a second edition in mid-1998; the book remains required reading for assembly-language programmers, but you need a good foundation in combinatorial mathematics and set theory to fully understand the contents.

The Influence of Computer Power on Knuth's Approach

As Knuth points out in the first page of the chapter on sorting, a better term to describe the process is "ordering." (The 724-page book has only two chapters—Chapter 6, "Sorting," and Chapter 7, "Searching"). Structured Query Language (SQL) takes Knuth's advice and uses ORDER BY clauses to define sort sequences. One of the dictionary definitions of the verb "to sort" is "to arrange according to characteristics," and the definition of "order" includes "arrange" as a synonym. Both sort and order infer that the process physically moves records; this was the case in the 1970s, a period when punched cards were the dominant means of computer data entry and storage. The advent of magnetic tape drives eliminated the need for punched card sorting and collating machines, but sorting still required individual records be rewritten to tape in the chosen order. Decks of punched cards and magnetic tape use sequential access, so sorting by merging expedites searching—assuming that records matching your search criteria appear early in the deck or tape. Thus the "Sorting" chapter precedes "Searching."

PREVIEW

Not a subscriber?

Start A Free Trial

• Create BookmarkCreate Bookmark
• Create Note or TagCreate Note or Tag
• PrintPrint