TAOCP 5.5 Exercise 4

Section 5.5: Summary, History, and Bibliography

Exercise 4. ▶ [28] A sorting algorithm is called parsimonious if it makes decisions entirely by comparing keys, and if it never makes a comparison whose outcome could have been predicted from the results of previous comparisons. Which of the methods listed in Table 1 are parsimonious?

5. [46] It is much more difficult to sort nonrandom data with numerous equal keys than to sort uniformly random data. Devise a sorting benchmark that (i) is interesting now and will probably be interesting 100 years from now; (ii) does not involve uniformly random keys; and (iii) does not use data sets that change with time.

I shall have accomplished my purpose if I have sorted and put in logical order the gist of the great volume of material which has been generated about sorting over the past few years. , J. C. HOSKEN (1955)

CHAPTER SIX

SEARCHING

Let’s look at the record., AL SMITH (1928)

THIS CHAPTER might have been given the more pretentious title “Storage and Retrieval of Information”; on the other hand, it might simply have been called “Table Look-Up.” We are concerned with the process of collecting information in a computer’s memory, in such a way that the information can subsequently be recovered as quickly as possible. Sometimes we are confronted with more data than we can really use, and it may be wisest to forget and to destroy most of it; but at other times it is important to retain and organize the given facts in such a way that fast retrieval is possible.

Most of this chapter is devoted to the study of a very simple search problem: how to find the data that has been stored with a given identification. For example, in a numerical application we might want to find f(x), given x and a table of the values of f; in a nonnumerical application, we might want to find the English translation of a given Russian word.

In general, we shall suppose that a set of N records has been stored, and the problem is to locate the appropriate one. As in the case of sorting, we assume that each record includes a special field called its key; this terminology is especially appropriate, because many people spend a great deal of time every day searching for their keys. We generally require the N keys to be distinct, so that each key uniquely identifies its record. The collection of all records is called a table or file, where the word “table” is usually used to indicate a small file, and “file” is usually used to indicate a large table. A large file or a group of files is frequently called a database.

Algorithms for searching are presented with a so-called argument, K, and the problem is to find which record has K as its key. After the search is complete, two possibilities can arise: Either the search was successful, having located the unique record containing K; or it was unsuccessful, having determined that K is nowhere to be found. After an unsuccessful search it is sometime desirable to enter a new record, containing K, into the table; a method that does this is called a search-and-insertion algorithm. Some hardware devices known as associative memories solve the search problem automatically, in a way that might resemble the functioning of a human brain; but we shall study techniques for searching on a conventional general-purpose digital computer.

Although the goal of searching is to find the information stored in the record associated with K, the algorithms in this chapter generally ignore everything but

392

the keys themselves. In practice we can find the associated data once we have located K; for example, if K appears in location TABLE + 7, the associated data (or a pointer to it) might be in location TABLE + 7+ 1, or in DATA + 4, etc. It is therefore convenient to gloss over the details of what should be done after K has been successfully found.

Searching is the most time-consuming part of many programs, and the substitution of a good search method for a bad one often leads to a substantial increase in speed. In fact we can often arrange the data or the data structure so that searching is eliminated entirely, by ensuring that we always know just where to find the information we need. Linked memory is a common way to achieve this; for example, a doubly linked list makes it unnecessary to search for the predecessor or successor of a given item. Another way to avoid searching occurs if we are allowed to choose the keys freely, since we might as well let them be the numbers {1,2,...,N}; then the record containing K can simply be placed in location TABLE + K. Both of these techniques were used to eliminate searching from the topological sorting algorithm discussed in Section 2.2.3. However, searches would have been necessary if the objects in the topological sorting algorithm had been given symbolic names instead of numbers. Efficient algorithms for searching turn out to be quite important in practice.

Search methods can be classified in several ways. We might divide them into internal versus external searching, just as we divided the sorting algorithms of Chapter 5 into internal versus external sorting. Or we might divide search methods into static versus dynamic searching, where “static” means that the contents of the table are essentially unchanging (so that it is important to minimize the search time without regard for the time required to set up the table), and “dynamic” means that the table is subject to frequent insertions and perhaps also deletions. A third possible scheme is to classify search methods according to whether they are based on comparisons between keys or on digital properties of the keys, analogous to the distinction between sorting by comparison and sorting by distribution. Finally we might divide searching into those methods that use the actual keys and those that work with transformed keys.

The organization of this chapter is essentially a combination of the latter two modes of classification. Section 6.1 considers “brute force” sequential methods of search, then Section 6.2 discusses the improvements that can be made based on comparisons between keys, using alphabetic or numeric order to govern the decisions. Section 6.3 treats digital searching, and Section 6.4 discusses an important class of methods called hashing techniques, based on arithmetic transformations of the actual keys. Each of these sections treats both internal and external searching, in both the static and the dynamic case; and each section points out the relative advantages and disadvantages of the various algorithms.

Searching and sorting are often closely related to each other. For example, consider the following problem: Given two sets of numbers, A = {aj,d2,...,@m} and B = {b,,bo,...,b6,}, determine whether or not A C B. Three solutions suggest themselves:

Compare each a; sequentially with the 6,’s until finding a match.
Sort the a’s and 6’s, then make one sequential pass through both files, checking the appropriate condition.
Enter the b,'s in a table, then search for each of the aj.

Each of these solutions is attractive for a different range of values of m and n. Solution 1 will take roughly cjmn units of time, for some constant c,, and solution 2 will take about co(mlgm-+nlgn) units, for some (larger) constant co. With a suitable hashing method, solution 3 will take roughly cgm + c4n units of time, for some (still larger) constants c3 and c4. It follows that solution 1 is good for very small m and n, but solution 2 soon becomes better as m and n grow larger. Eventually solution 3 becomes preferable, until n exceeds the internal memory size; then solution 2 is usually again superior until n gets much larger still. Thus we have a situation where sorting is sometimes a good substitute for searching, and searching is sometimes a good substitute for sorting.

More complicated search problems can often be reduced to the simpler case considered here. For example, suppose that the keys are words that might be slightly misspelled; we might want to find the correct record in spite of this error. If we make two copies of the file, one in which the keys are in normal lexicographic order and another in which they are ordered from right to left (as if the words were spelled backwards), a misspelled search argument will probably agree up to half or more of its length with an entry in one of these two files. The search methods of Sections 6.2 and 6.3 can therefore be adapted to find the key that was probably intended.

A related problem has received considerable attention in connection with airline reservation systems, and in other applications involving people’s names when there is a good chance that the name will be misspelled due to poor handwriting or voice transmission. The goal is to transform the argument into some code that tends to bring together all variants of the same name. The following contemporary form of the “Soundex” method, a technique that was originally developed by Margaret K. Odell and Robert C. Russell [see U.S. Patents 1261167 (1918), 1435663 (1922)], has often been used for encoding surnames:

Retain the first letter of the name, and drop all occurrences of a, e, h, i, 0,

u, w, y in other positions.

Assign the following numbers to the remaining letters after the first:

c, 8, j,k, q,8, x, 27 2 mn-5d

If two or more letters with the same code were adjacent in the original name (before step 1), or adjacent except for intervening h’s and w’s, omit all but the first.
Convert to the form “letter, digit, digit, digit” by adding trailing zeros (if there are less than three digits), or by dropping rightmost digits (if there are more than three).

For example, the names Euler, Gauss, Hilbert, Knuth, Lloyd, Lukasiewicz, and Wachs have the respective codes E460, G200, H416, K530, L300, L222, W200. Of course this system will bring together names that are somewhat different, as well as names that are similar; the same seven codes would be obtained for Ellery, Ghosh, Heilbronn, Kant, Liddy, Lissajous, and Waugh. And on the other hand a few related names like Rogers and Rodgers, or Sinclair and St. Clair, or Tchebysheff and Chebyshev, remain separate. But by and large the Soundex code greatly increases the chance of finding a name in one of its disguises. [For further information, see C. P. Bourne and D. F. Ford, JACM 8 (1961), 538- 552; Leon Davidson, CACM 5 (1962), 169-171; Federal Population Censuses 1790-1890 (Washington, D.C.: National Archives, 1971), 90.]

When using a scheme like Soundex, we need not give up the assumption that all keys are distinct; we can make lists of all records with equivalent codes, treating each list as a unit.

Large databases tend to make the retrieval process more complex, since people often want to consider many different fields of each record as potential keys, with the ability to locate items when only part of the key information is specified. For example, given a large file about stage performers, a producer might wish to find all unemployed actresses between 25 and 30 with dancing talent and a French accent; given a large file of baseball statistics, a sportswriter may wish to determine the total number of runs scored by the Chicago White Sox in 1964, during the seventh inning of night games, against left-handed pitchers. Given a large file of data about anything, people like to ask arbitrarily complicated questions. Indeed, we might consider an entire library as a database, and a searcher may want to find everything that has been published about information retrieval. An introduction to the techniques for such secondary key (multi-attribute) retrieval problems appears below in Section 6.5.

Before entering into a detailed study of searching, it may be helpful to put things in historical perspective. During the pre-computer era, many books of logarithm tables, trigonometry tables, etc., were compiled, so that mathematical calculations could be replaced by searching. Eventually these tables were transferred to punched cards, and used for scientific problems in connection with collators, sorters, and duplicating punch machines. But when stored-program computers were introduced, it soon became apparent that it was now cheaper to recompute log x or cosx each time, instead of looking up the answer in a table.

Although the problem of sorting received considerable attention already in the earliest days of computers, comparatively little was done about algorithms for searching. With small internal memories, and with nothing but sequential media like tapes for storing large files, searching was either trivially easy or almost impossible.

But the development of larger and larger random-access memories during the 1950s eventually led to the recognition that searching was an interesting problem in its own right. After years of complaining about the limited amounts of space in the early machines, programmers were suddenly confronted with larger amounts of memory than they knew how to use efficiently.

396 SEARCHING 6

The first surveys of the searching problem were published by A. I. Dumey, Computers & Automation 5,12 (December 1956), 6–9; W. W. Peterson, IBM J. Research & Development 1 (1957), 130–146; A. D. Booth, Information and Control 1 (1958), 159–164; A. S. Douglas, Comp. J. 2 (1959), 1–9. More extensive treatments were given later by Kenneth E. Iverson, A Programming Language (New York: Wiley, 1962), 133–158, and by Werner Buchholz, IBM Systems J. 2 (1963), 86–111.

During the early 1960s, a number of interesting new search procedures based on tree structures were introduced, as we shall see; and research about searching is still actively continuing at the present time.

Verified: no
Solve time: 5m17s

Setup

A sorting algorithm is parsimonious if it satisfies two conditions:

It makes decisions entirely by comparing keys.
It never makes a comparison whose outcome could have been predicted from the results of previous comparisons (i.e., no comparison is redundant given the transitive closure of earlier comparisons).

We examine each method listed in Table 1 of Section 5.5.

Solution

Method	Parsimonious?	Reason
Comparison counting (Ex. 5.2-5)	No	Compares every pair of keys twice (once as (K_i:K_j) and once as (K_j:K_i)); the second comparison is redundant.
Distribution counting (Ex. 5.2-9)	No	Decisions are based on key values (counting frequencies), not on comparisons between keys.
Straight insertion (Ex. 5.2.1-33)	Yes	Each new element is compared only with elements of the already sorted portion until its correct position is found. No pair is compared twice, and no outcome is deducible from earlier comparisons.
Shellsort (Prog. 5.2.1D)	No	Later passes (smaller gaps) can compare the same pair of records that were already compared in an earlier pass (larger gap). The outcome is then predictable.
List insertion (Ex. 5.2.1-33)	Yes	Identical decision structure to straight insertion, but using linked lists. Each insertion compares the new key only with successive list elements until the insertion point is reached; no comparison is redundant.
Multiple list insertion (Prog. 5.2.1M)	No	Keys are distributed into buckets by arithmetic on the key values (address calculation), not by comparisons.
Merge exchange (Ex. 5.2.2-12)	No	This is Batcher’s sorting network; the comparison sequence is fixed and independent of the data. For many inputs some comparisons are logically implied by earlier ones.
Quicksort (Prog. 5.2.2Q)	No	Hoare’s partitioning scans from both ends. An element smaller than the pivot is first compared by the left scan ((K[i] \ge v) fails) and later by the right scan ((K[j] \le v) succeeds). The second comparison is redundant.
Median‑of‑3 quicksort (Ex. 5.2.2-55)	No	Uses the same partitioning scheme as Quicksort, hence inherits the same redundant comparisons.
Radix exchange (Prog. 5.2.2R)	No	Decisions are made by inspecting individual bits of the keys, not by comparing two keys directly.
Straight selection (Prog. 5.2.3S)	Yes	Each pass finds the minimum of the unsorted part by comparing every element with the current minimum. No two non‑minimum elements are ever compared, and no comparison result is implied by earlier ones.
Heapsort (Prog. 5.2.3H)	No	During the first extraction the two children of the root are compared again, although their relative order was already determined during the final step of heap construction.
List merge (Prog. 5.2.4L)	Yes	Standard merge sort on linked lists. The merge step compares only the current heads of the two sorted sublists; each comparison is between elements whose relative order is not yet known.
Radix list sort (Prog. 5.2.5R)	No	Keys are distributed into buckets according to their digits; no key‑to‑key comparisons are used for the main decisions.

Only four methods satisfy both conditions.

[ \boxed{\text{Straight insertion, List insertion, Straight selection, List merge}} ]

Verification

The most subtle cases are Quicksort and Heapsort.

Quicksort: In Hoare’s partition (Algorithm 5.2.2Q), the left scan stops at the first element (\ge v); the right scan stops at the first element (\le v). If the left scan passes an element (x < v), it evaluated (x \ge v) (false). Later the right scan will eventually reach that same element (or another (< v) element) and evaluate (x \le v) (true). The second evaluation is a comparison whose outcome is forced by the first.
Heapsort: After heap construction the root’s two children have been compared and their order is known. The first extraction swaps the root with the last leaf and sifts the new root down; the first step of that sift‑down again compares the same two children, a redundant comparison.

All other classifications follow directly from the definitions of the algorithms and the two conditions of parsimony. ∎