4 CHAPTER 1INTRODUCTION
• and between the diﬀerent implementation characteristics of algorithms when
we move beyond a “theoretical” description of the algorithm and actually write
a program that runs on a real computer.
1.1.4 Maintaining Sorted Order
Change is a constant fact of life. No matter how careful one is to anticipate all
possibilities, something unanticipated will also happen. In the case of data, we
know that change will happen. As soon as we create an address book with all our
contacts in it, we will encounter a new individual who needs to be added to the ﬁle.
Since we will want to maintain our contacts in sorted order, we will probably need
to insert the new contact into the data ﬁle in the correct location.
If our ﬂat ﬁle is in fact a spreadsheet, we could do this by adding the new record
at the bottom and then using the “sort” function to move all the data into the
proper locations. In a simple spreadsheet, the sort will quite literally move all the
records, and for an individual’s address book of a few hundred records, this can
be acceptable behavior. However, if the data records are the entire database of the
U.S. Internal Revenue Service, then physically moving all the data on disk so as to
insert one record is not acceptable. Part of the study of data structures, therefore,
is the study of how to maintain sorted order in the presence of change.
1.1.5 Indexing, Search, and Retrieval
Although in many instances there is a natural primary key on which to retrieve
records (such as last name for our address book), it is often important to be able
to retrieve records from a (conceptual) ﬂat ﬁle in an order other than the order
in which they are stored conceptually. If one is maintaining a mailing list, then in
addition to having records sorted by last name, one may well need to be able to
retrieve records sorted by zip code so as to get the beneﬁt of bulk mail postage rates.
To do this, one would invert the ﬁle on the zip code ﬁeld and create an index that
can be used for retrieval on the secondary key instead of the last-name primary key.
More importantly, one of the primary features of any complex computer program
is that it will search for and retrieve a data item, based on a key, from a “collection”
of data. The key might be a Social Security number, a name, or even a request for
“the next” item in some sorted order. We will therefore deal with the organization
of data so that search and retrieval of data can be done eﬃciently.
In working with data, what matters a great deal is whether or not that data is
structured. A retail receipt for purchases at the grocery store represents structured
data. Each such record has date, time, and store information, as well as some
number of lines of transaction information for the item purchased, the individual
price, and the number of items that were purchased. One can easily imagine a