Data Structures, Hour by Hour

What This Book Is About

Almost every program keeps some information and does something with it. A data structure is a way of arranging that information in the computer's memory. The book covers the classic ones: arrays, linked lists, stacks, queues, several kinds of trees, and hash tables.

An algorithm is a step-by-step procedure that works on a structure. Typical jobs are putting a new item in, looking an item up, taking one out, and sorting everything into order.

The two ideas belong together. A structure is only useful because of the operations you can run on it, and the speed of each operation depends on how the data is arranged. Looking up one name can take a single step or a million steps, depending on the structure underneath.

Lafore's aim is practical. He wants programmers and students to know these tools well enough to pick the right one, so their programs run faster and are better organized. The book stays light on mathematics and skips formal proofs. To show that one method beats another, it counts steps and draws pictures.

What's Different About This Book

Four features shape the way the book teaches.

Workshop applets. For each major topic, the book's CD carried a small interactive program, a Workshop applet, that draws the structure on screen. You press buttons to insert, delete, search or sort, and watch the data change. Seeing a structure move teaches more than pages of description, which is the old point about a picture being worth a thousand words.

An easy-to-understand approach. Where many textbooks rely on proofs and formulas, this one leans on intuition, everyday analogies and plenty of figures.

C++ sample programs. Every important idea comes with a complete, short program that you can compile, run, and read in one sitting.

Hour-sized chapters. Each chapter is designed to be learned in about an hour, with a quiz at the end to check that it stuck.

Who This Book Is For

Students taking a data structures course can use the book as a friendly companion to a heavier textbook. Programmers who never took such a course, self-taught developers, and anyone who wants a quick, practical grounding will find it a good place to start. It is not written for experts, since it explains everything from the ground up.

What You Need to Know Before You Read This Book

You should have written some programs before. C++ experience is ideal, but a reader who knows C or Java will follow the code easily because the syntax is so similar. You should be comfortable with variables, loops, functions and arrays, and have a rough idea of what a class is. Hour 1 includes a quick refresher on object-oriented programming.

You don't need to know anything about data structures. The mathematics stops at simple algebra, and the one tool beyond it, the logarithm, gets a plain explanation in Hour 3.

The Software You Need to Use This Book

To run the sample programs you need a C++ compiler. The programs are standard console-mode C++, reading and writing plain text with no graphics, so any standard compiler of the day would do, such as Microsoft Visual C++, Borland C++ or the GNU compiler, g++.

To run the Workshop applets you needed a Java-enabled web browser, or the appletviewer program from Sun's Java Development Kit (JDK). Appendix B of the book explained how to set up both.

How This Book Is Organized

The 24 hours are grouped into five parts, followed by three appendixes. Each part builds on the ones before it, so the structures grow more capable as you go.

Part I, Introducing Data Structures and Algorithms (Hours 1 to 5). Hour 1 surveys the field and refreshes your C++. Hour 2 covers arrays and wraps one in a class. Hour 3 keeps the array in order for binary search, which leads to logarithms and Big O notation. Hours 4 and 5 teach two simple sorts, the bubble sort and the insertion sort.

Part II, Abstract Data Types (Hours 6 to 10). Hour 6 introduces stacks and Hour 7 queues and priority queues, structures that limit which item you can reach. Hour 8 brings in linked lists, Hour 9 rebuilds stacks and queues from lists and explains abstract data types, and Hour 10 covers sorted and doubly linked lists.

Part III, Recursion and Quicksort (Hours 11 to 14). Hour 11 explains recursion, a function calling itself. Hour 12 applies it to the Towers of Hanoi and to mergesort. Hour 13 presents quicksort, and Hour 14 keeps it fast on awkward data.

Part IV, Trees (Hours 15 to 20). Hours 15 and 16 cover binary search trees. Hours 17 and 18 explain red-black trees, which keep themselves balanced. Hours 19 and 20 describe 2-3-4 trees, whose nodes hold several items, and their close tie to red-black trees.

Part V, Hash Tables (Hours 21 to 24). Hour 21 introduces hashing and linear probing, Hour 22 adds quadratic probing and double hashing, and Hour 23 covers separate chaining and hash functions. Hour 24, "When to Use What," turns the whole book into advice for choosing a structure.

Part VI, Appendixes. Appendix A answers every quiz, Appendix B explains how to run the applets and sample programs, and Appendix C suggests further reading.

Enjoy Yourself!

Data structures have a reputation as a dry and difficult subject, and Lafore sets out to prove otherwise. He invites you to treat the book as a place to play, where you run the applets, feed them odd inputs, and see what happens.

There is real satisfaction in watching a tree rebalance itself or a quicksort carve an array into pieces. Once the pictures make sense, the code usually does too.

Conventions Used in This Book

The book sets code, such as class and function names, in a monospace font. New terms are flagged and defined where they first appear. Short notes, tips and cautions sit in boxes beside the main text, and "To Do" boxes give numbered steps for working with the applets.

Every hour ends the same way, with a summary, a Q&A section, and a Workshop quiz whose answers are in Appendix A. This companion keeps the same habits, with a few changes for the web. Its boxes carry these labels:

Quiz answers are hidden under an "Answer" toggle at the end of each hour, so you can test yourself before you look. The Workshop panels are JavaScript re-creations of the book's applets, with similar buttons and displays.

How to Use This Companion

Read the hours in order, because later hours lean on earlier ones. Big O notation from Hour 3, for example, appears in every hour after it.

When a Workshop panel appears, stop and use it. Follow the To do steps, then try inputs of your own; watching the counts of comparisons and moves is the quickest way to feel why one structure beats another. At the end of each hour, answer the quiz before opening the answers, then press the button at the end of the hour to mark it as read.

The C++ listings keep the book's class and function names, so you can match them to the original. The code itself is written fresh for this companion in the book's style, and it compiles with a modern compiler.

Some Uses for Data Structures and Algorithms

Nearly every serious program has to hold data and work with it. The way that data is arranged can make the difference between a program that answers instantly and one that grinds away for minutes. The situations where data structures help fall roughly into three groups.

Real-World Data Storage

Many structures store information about things outside the computer, such as employees in a personnel file, parts in an inventory, or stamps in a collector's catalog.

Lafore's example is an address book kept on 3×5 index cards, each holding one person's name, address and phone number. Imagine moving the card box into a computer, with 1,000 cards in it. You'd have to arrange the cards in memory, and you'd need ways to add a card, find the card for a given name, and remove a card, all without wading through every card each time.

Those three jobs, insert, find and delete, come up again and again. For ten cards any arrangement is fast enough, but for thousands or millions the arrangement decides everything. Most of the structures in this book are different answers to this storage problem.

Programmer's Tools

Some structures never hold the user's data. The program uses them internally as scaffolding, and the user never knows they exist. Stacks, queues and priority queues, the subject of Part II, are often used this way. In Hour 6, for example, a stack checks that every opening bracket in an expression has a matching closing one.

Modeling

A few structures mirror a real situation directly. A queue behaves just like customers waiting for a bank teller or cars lined up at a toll booth, where whoever arrived first is served first, so a program that simulates the bank can use a queue to stand for the line. Graphs, which this book doesn't cover, model networks such as airline routes or city roads.

Overview of Data Structures

The book covers nine structures. Each one makes some operations fast at the cost of making others slow or complicated, and no structure wins at everything. The table below previews the trade-offs, and every row gets one or more hours of its own later on.

Read the table as a map of what lies ahead. The array is quick to add to but slow to search, and keeping it sorted trades faster searching for slower insertion. Stacks and queues deliberately let you reach only one item at a time.

Linked lists make insertion and deletion quick. Trees make nearly everything quick while they stay balanced, and red-black and 2-3-4 trees guarantee that balance at the price of more complex code. Hash tables are fastest of all when you know the key, and Hour 24 returns to every structure to help you choose.

Overview of Algorithms

Most algorithms in the book belong to one particular structure, since finding an item in an array has little in common with finding one in a tree. Across all the structures, though, the same basic jobs keep coming up.

• Insertion puts a new data item into the structure.
• Searching finds a specified item, usually by its key.
• Deletion removes a specified item.

You'll also need to iterate through a structure, visiting each item in turn, for example to display them all. And you'll need to sort items into order, a job that earns several hours of its own (Hours 4, 5 and 12 to 14).

Recursion, in which a function calls itself, is a technique for writing algorithms rather than an operation. It is the key to the fastest sorts and to working with trees, and Part III is devoted to it.

For every algorithm, the book asks how much work it takes. Work is usually counted in comparisons (checking one key against another) and moves (copying an item from one place to another), and it almost always depends on N, the number of items.

Some Initial Definitions

A few words appear so often in the rest of the book that it pays to define them now. The address book makes a good running example.

Database

A database is all the data you are working with in a particular situation. The box of address cards is a database, and so is a company's file of employee records. In this book the word simply means the collection of data, with no suggestion of a special database program.

Record

A database is divided into records, the units you store and retrieve. Each index card is one record, holding everything the address book knows about one person. In an employee file, each record describes one employee.

Field

Each record is divided into fields, one for each kind of information. An address card has a name field, an address field and a phone number field. In a C++ program a record is usually an object, and each field is one of its data members, such as a string lastName or an int age.

Key

To find a record, or to sort a set of them, you pick one field to work with, and that field is the key. For the address book the natural key is the last name, since that's how you look people up and how you would file the cards.

The particular value you're looking for, such as "Smith," is the search key. A search compares the search key with the key field of each record it examines until it finds a match or runs out of records.

A Quick Introduction to Object-Oriented Programming

Every program in the book is built from classes, so this section reviews the object-oriented ideas you'll need. If you use C++ classes every day, you can skim it.

Problems with Procedural Languages

Object-oriented programming (OOP) was invented to fix two weaknesses of procedural languages such as C and Pascal, in which a program is a collection of functions and variables.

The first weakness is poor modeling of the real world. Picture a program that controls the heating in a house. It needs variables for the current and desired temperatures, and functions that switch the furnace on and off. In a procedural language these are separate items, possibly scattered through the program, and nothing says they belong together as one thermostat. With three thermostats, it's up to you to keep track of which function acts on which set of variables.

The second weakness is crude organizational units. A procedural program is built from only functions and global data, which is too little structure once a program grows to thousands of lines. Worse, any function can change global data, so a mistake in one corner can corrupt data used in another.

Objects in a Nutshell

An object bundles data together with the functions that act on that data. A thermostat object contains the data items currentTemp and desiredTemp along with the functions furnace_on() and furnace_off(). The data items are called data members, and the functions are called member functions. Now the language itself records that these things belong together.

A class is the specification for a kind of object, a blueprint that says what data and functions every object of that kind will have. Writing the class doesn't create any objects; it only describes them. Each object you later create from the class is an instance of it. Here is the outline of a thermostat class, with the furnace-control details left out.

class thermostat {
private:
    // each thermostat keeps its own two temperatures
    float currentTemp;
    float desiredTemp;

public:
    // the jobs a thermostat knows how to do
    void furnace_on() {
        // statements that switch the furnace on
    }

    void furnace_off() {
        // statements that switch the furnace off
    }
};

The keyword class is followed by the class name and a pair of braces holding the members, and a semicolon ends the whole thing. The labels private and public control who may use each member, as you'll see shortly. Once the class exists, you create objects from it just as you create variables of a built-in type, and then you tell them what to do.

int main() {
    // two thermostat objects, each with its own temperatures
    thermostat therm1, therm2;

    // each call works on one particular object
    therm1.furnace_on();
    therm2.furnace_off();

    // an object made with new is reached through a pointer
    thermostat* pTherm = new thermostat;
    pTherm->furnace_on();
    delete pTherm;
    return 0;
}

Each object gets its own copy of the data members, so therm1 and therm2 can hold different temperatures. To call a member function, you write the object's name, a dot, and the function. The dot operator ties the call to one object, so therm2.furnace_off() switches off the furnace that therm2 controls and leaves therm1 alone.

An object made with new is reached through a pointer, and the arrow operator, ->, replaces the dot. The book's pointer names start with a p, as in pTherm.

A Runnable Object-Oriented Program

The thermostat outline can't do anything, because its functions are empty. The book's first complete program, bank.cpp, models something just as familiar, a bank account. Its class, BankAccount, holds one data member, the balance, and offers three services: deposit money, withdraw money, and display the balance.

// bank.cpp
// A bank account modeled as a C++ class
#include <iostream>
using namespace std;

class BankAccount {
private:
    // the account's only data: the money in it
    double balance;

public:
    // constructor: runs whenever an account is created
    BankAccount(double openingBalance) : balance(openingBalance) {
    }

    // add money to the account
    void deposit(double amount) {
        balance += amount;
    }

    // take money out of the account
    void withdraw(double amount) {
        balance -= amount;
    }

    // show the current balance
    void display() {
        cout << "balance=" << balance << endl;
    }
};

int main() {
    // open an account with $100 in it
    BankAccount ba1(100.00);

    cout << "Before transactions, ";
    ba1.display();

    ba1.deposit(74.35);
    ba1.withdraw(20.00);

    cout << "After transactions, ";
    ba1.display();
    return 0;
}

In main(), the statement BankAccount ba1(100.00); creates an account object named ba1 with an opening balance of $100. The program prints a label and calls ba1.display(). Then it deposits $74.35 and withdraws $20.00, each time by calling a member function of ba1, and displays the balance again. Since 100 + 74.35 − 20 = 154.35, the output is:

Before transactions, balance=100
After transactions, balance=154.35

(C++ prints 100 rather than 100.00 because its default format drops trailing zeros.) Notice that main() never touches balance directly. It asks the object to deposit, withdraw or display, and the object's own functions do the arithmetic.

Constructors

A constructor is a special member function that runs automatically when an object is created, to give the object's data sensible starting values. It has exactly the same name as its class, and it has no return type, not even void.

In bank.cpp the constructor takes the opening balance as an argument. The part after the colon, : balance(openingBalance), is an initializer list, which copies the argument into the data member, so the body has nothing left to do. You never call a constructor by name. Defining ba1 calls it for you, passing 100.00; without it, balance would start out holding whatever value happened to be in memory.

public and private

The data member balance sits in the class's private section. Private members can be read or changed only by the class's own member functions. If main() tried to write ba1.balance = 1000000;, the compiler would refuse. This protection is called data hiding, and it guards the data against careless or accidental changes from outside the class.

The member functions sit in the public section, so any code with a BankAccount object can call them. Together, the public functions form the class's interface, the services the outside world may use. The usual pattern, and the book's, is private data with public functions. Anyone who wants to change the balance must go through deposit() or withdraw(), which is where a real bank would add checks, such as refusing an overdraft.

Inheritance and Polymorphism

Two more OOP ideas complete the picture, though the book uses them very little. Inheritance lets you create a derived class from an existing base class. The derived class gets all the base class's data and functions and can add its own. You could derive a savings account class from BankAccount, for example, and add a function that pays interest.

Polymorphism lets you treat objects of different derived classes in the same way. You call the same function on each object, and each responds in the manner of its own class. In C++ this works through virtual functions, usually called through pointers to the base class.

New C++ Features

The book's programs rely on parts of Standard C++ that older courses and textbooks often skip. If you learned C++ from one of them, three features may be new to you.

The string Class

Older C++ code stores text in arrays of char and handles it with functions such as strcpy() and strcmp(), a clumsy style that makes it easy to write past the end of the array. Standard C++ offers a string class instead. After including <string>, you can write string s1 = "cat"; and treat the string much like a built-in type.

The + operator joins strings, so s1 + s2 glues the second onto the end of the first. The operators == and < compare them, with "less than" meaning "comes first alphabetically" (when both words use the same capitalization), and s1.length() reports the number of characters. A string grows as needed, and comparing strings with == is how the book's programs search by name.

The vector Class

The vector class belongs to the Standard Template Library (STL), a collection of ready-made containers and algorithms that is part of Standard C++. A vector behaves much like an array, and you reach its elements with square brackets, as in v[j]. Unlike an array, it knows its own size, which v.size() reports, it manages its own memory, and it can grow.

You include <vector> and name the element type in angle brackets. vector<double> v(100); creates 100 double values. You can also create an empty vector and size it later with v.resize(100);, as the book's classes do in their constructors, and v.push_back(value) adds an element at the end. Because of this, the array classes in Hour 2 and Hour 3 can take their size as a constructor argument while the program runs, which a plain C++ array can't do.

New-Style Headers and Namespaces

Standard C++ also renamed the library header files. You write #include <iostream> instead of the older #include <iostream.h>. Everything in the standard library now lives in a namespace called std.

The line using namespace std; near the top of a file lets you write cout, string and vector without putting std:: in front of each one, and every program in the book starts this way. Here is a short program that tries out both classes.

// features.cpp
// A quick tour of the string and vector classes
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    // strings join with + and compare with == and <
    string s1 = "cat";
    string s2 = "fish";
    string s3 = s1 + s2;
    cout << s3 << " has " << s3.length() << " letters" << endl;
    if (s1 < s2)
        cout << s1 << " comes before " << s2 << endl;

    // a vector sized in advance works like an array
    vector<double> v(5);
    for (int j = 0; j < 5; j++)
        v[j] = j * 1.5;

    // push_back adds one more cell at the end
    v.push_back(99.0);
    cout << "The vector now holds " << v.size() << " numbers" << endl;
    return 0;
}

catfish has 7 letters
cat comes before fish
The vector now holds 6 numbers

The first half builds "catfish" by joining two strings, reports its seven letters, and confirms that "cat" sorts before "fish." The second half creates a five-cell vector, fills it with a loop exactly as you would fill an array, and then calls push_back() to add a sixth value, so size() reports 6.

Software Engineering

Software engineering is the study of how to create large programs. It covers a program's whole life cycle, from the first idea to years of later upkeep, and the stages are usually described like this:

1. Specification, or analysis, works out what the program must do.
2. Design decides how the program will be organized, including its classes and data structures.
3. Coding writes the program.
4. Testing finds and fixes errors.
5. Maintenance keeps the program working and adapts it after release, often for years.

Data structures and algorithms matter most in design and coding. Choosing a structure that suits the job is a design decision, implementing it well is a coding task, and together they decide whether the finished program is fast or slow.

The benefits spread to the later stages too. Well-chosen, cleanly separated classes are easier to test, because each can be checked on its own, and easier to maintain, because a change inside one class doesn't ripple through the rest. Software engineering is a big subject with many books of its own, and this book deals only with the parts that concern data structures and algorithms.

The Array Workshop Applet

Suppose you coach a youth-league baseball team and want to take attendance at practice on a laptop. Players turn up one at a time. When a player arrives, you type in the number on the back of the player's jersey. When a parent asks whether a certain player made it, you check the list, and when a player leaves early, you take the number off.

This little program needs exactly the three basic operations from Hour 1: insertion, searching and deletion. The jersey number is the key, and each player is a record with just that one field.

The simplest structure for the job is an array, and the book's Array Workshop applet shows one on the screen. It draws the array as a row of cells, each labeled with its index number and able to hold one key. Buttons let you create a new array (New, which asks for a size and whether duplicate keys are allowed), fill it with random keys (Fill), and insert, find or delete a key typed into a number field (Ins, Find, Del).

Our re-creation below works the same way and counts the comparisons and moves that each operation makes. Try each button as you read the rest of this section.

Insertion

When a new player arrives, the applet puts the number into the first empty cell, just past the last item. It knows exactly where that is because it keeps a count of the items. If the array holds 10 items, they occupy cells 0 through 9, so the new item goes into cell 10 and the count becomes 11.

That makes insertion very fast. There is no searching and no comparing, just one move to copy the new item into place, and the time is the same whether the array holds 10 items or 10,000.

Searching

To check whether a player is present, you type the number and press Find. The algorithm has no idea where the number might be, so it starts at cell 0 and compares each key with the one you typed, moving right one cell at a time, until it finds a match or runs out of items.

If the player is there, the match could be in the first cell or the last, and every position is equally likely. On average the search looks at half the items before it succeeds, so for N items it needs about N/2 comparisons. With 20 players that's 10 comparisons on average; with 20,000 records it's 10,000.

If the player isn't there, the search can't stop early. It must compare all N items before it can report failure.

Deletion

Deleting a player takes two stages. First the algorithm must find the item, which costs about N/2 comparisons on average, just like a search. Then it has to deal with the empty cell the item leaves behind.

The applet's algorithms assume the array has no holes. The items sit in consecutive cells starting at 0, with no empty cells between them. That is what lets insertion go straight to the cell after the last item, and what lets a search stop at the last item instead of checking every cell in the array.

So after finding the item, deletion closes the gap. Every item above the deleted one moves down one cell, starting with the item just above the gap. If the deleted item was near the start, nearly everything moves; if it was near the end, hardly anything does.

On average about N/2 items move. Deletion therefore costs about N/2 comparisons plus about N/2 moves, which makes it the slowest of the three operations.

The Duplicates Issue

When you design a storage structure, you have to decide whether two items may share the same key. Jersey numbers are unique, so the attendance list never needs duplicates. If the key were a last name, though, two brothers named Garcia could easily be on the same team. The book's applet lets you choose when you press New, and allowing duplicates changes the costs.

• Searching. Without duplicates, a search stops at the first match, after N/2 comparisons on average. With duplicates, finding every item with a given key means checking all N cells, since another match could be anywhere.
• Insertion. This stays one move with no comparisons either way, because the new item always goes in the first empty cell. There is one catch. If duplicates are forbidden and a user might type a key that's already present, the program must search before inserting, which costs about N/2 comparisons when the key is found and all N to prove that it's absent.
• Deletion. Deleting every copy of a key means examining all N cells, and each copy removed forces more items to shift, so the moves usually add up to more than N/2.

Not Too Swift

Playing with the applet makes the verdict clear. Insertion is fast, but searching and deletion are slow, because both have to plow through about half the array. For a team of 15 players nobody would notice. For a file of 100,000 customers, an average of 50,000 comparisons per lookup starts to hurt.

Much of the rest of the book is a hunt for structures that do better. An ordered array (Hour 3) makes searching far faster. Linked lists (Hour 8) do away with the shifting, trees (Hour 15) speed up all three operations, and hash tables (Hour 21) can find an item almost instantly.

An Array Example

Before wrapping an array in a class, it helps to see a plain C++ array doing the same jobs. First, a quick review of how C++ arrays work.

Creating an Array

You declare an array by giving the type of its elements, its name, and its size in square brackets. int arr[100]; sets aside room for 100 integers. The size must be a constant that is known when the program is compiled, and it can never change afterward. That fixed size is one of the array's big limitations, as you'll see at the end of Hour 3.

Accessing Array Elements

You reach an element by putting its index in square brackets, as in arr[j]. Indexes start at 0, so the 100 cells of arr are numbered 0 through 99. Asking for arr[100] is a mistake that the compiler won't catch, and the running program won't catch it either. It simply reads or overwrites whatever memory lies beyond the array, which can cause baffling bugs or a crash.

Initialization

You can fill an array when you create it by listing values in braces, as in int intArr[] = {0, 3, 6, 9, 12, 15};. If you leave the brackets empty, the compiler makes the array just big enough for the list, six cells in this case.

The array.cpp Program

The program array.cpp puts all of this to work. It inserts ten items, displays them, searches for one, deletes another, and displays what's left, and everything happens inside main(). In our version the ten keys start out in an initialized array, and a loop inserts them one at a time into the working array, arr.

// array.cpp
// Plain C++ array: insert, display, search and delete, all in main()
#include <iostream>
using namespace std;

int main() {
    // the ten keys, in the order the players arrive
    int arrivals[] = {77, 99, 44, 55, 22, 88, 11, 0, 66, 33};

    // the array itself, and a count of the cells in use
    int arr[100];
    int nElems = 0;
    int j;

    // insertion: each new item goes into the first empty cell
    for (j = 0; j < 10; j++) {
        arr[nElems] = arrivals[j];
        nElems++;
    }

    // display every item
    for (j = 0; j < nElems; j++)
        cout << arr[j] << " ";
    cout << endl;

    // linear search for 66
    int searchKey = 66;
    for (j = 0; j < nElems; j++)
        if (arr[j] == searchKey)
            break;
    if (j == nElems)
        cout << "Can't find " << searchKey << endl;
    else
        cout << "Found " << searchKey << endl;

    // deletion: find 55, then slide the higher items down
    searchKey = 55;
    for (j = 0; j < nElems; j++)
        if (arr[j] == searchKey)
            break;
    if (j < nElems) {
        for (int k = j; k < nElems - 1; k++)
            arr[k] = arr[k + 1];
        nElems--;
    }

    // display what's left
    for (j = 0; j < nElems; j++)
        cout << arr[j] << " ";
    cout << endl;
    return 0;
}

The variable nElems is the heart of the program. It counts the items, and it's also the index of the first empty cell, since the items fill cells 0 through nElems − 1. That's why insertion is just arr[nElems] = value followed by nElems++.

The search loop compares each item with searchKey and uses break to leave as soon as it finds a match. When the loop ends there are only two possibilities. Either it broke out early and j holds the index of the match, or it ran all the way to the end and j equals nElems. The test j == nElems tells the two apart.

Deletion begins with the same search, this time for 55, which it finds at index 3. The second loop then closes the gap by copying the item at k + 1 into cell k, for each k from the hole upward. It stops when k reaches nElems − 1, so its last copy moves the final item into the cell below it. Then nElems drops by one.

Our version also checks that the search succeeded before it shifts anything, so asking it to delete a missing key does no harm. Here is the output:

77 99 44 55 22 88 11 0 66 33
Found 66
77 99 44 22 88 11 0 66 33

The program shows the ten items, reports the successful search for 66, and then shows the array after 55 has gone. The items that followed 55 kept their order; each simply slid one cell to the left.

Dividing a Program into Classes

array.cpp works, but it's organized like a procedural program. The data (the array and its count) and every operation on it are mixed together in one long main(). In a program of ten thousand lines that used the array in dozens of places, search loops and shifting loops would be scattered everywhere, and any one of them could damage the array.

The object-oriented cure from Hour 1 is to put the data into a class, together with the functions that act on it. The book takes this in two steps. The first, lowArray.cpp, moves the array into a class called LowArray but gives that class only the most basic abilities.

// lowArray.cpp
// The array moves into a class with a bare-bones interface
#include <iostream>
#include <vector>
using namespace std;

class LowArray {
private:
    // the storage is hidden inside the class
    vector<double> v;

public:
    // constructor: make room for max items
    LowArray(int max) {
        v.resize(max);
    }

    // put value into cell number index
    void setElem(int index, double value) {
        v[index] = value;
    }

    // hand back the value in cell number index
    double getElem(int index) {
        return v[index];
    }
};

The array is now a private vector<double> named v, so no code outside the class can reach it directly. The constructor takes the size you want and calls resize() to make the vector that big. After that there are just two member functions. setElem() stores a value at a given index, and getElem() returns the value at a given index.

The client still does all the real work, as the main() function shows.

int main() {
    LowArray arr(100);
    int nElems = 0;
    int j;

    // main decides where each item goes
    double arrivals[] = {77, 99, 44, 55, 22, 88, 11, 0, 66, 33};
    for (j = 0; j < 10; j++) {
        arr.setElem(nElems, arrivals[j]);
        nElems++;
    }
    for (j = 0; j < nElems; j++)
        cout << arr.getElem(j) << " ";
    cout << endl;

    // main runs the linear search itself
    double searchKey = 26;
    for (j = 0; j < nElems; j++)
        if (arr.getElem(j) == searchKey)
            break;
    if (j == nElems)
        cout << "Can't find " << searchKey << endl;
    else
        cout << "Found " << searchKey << endl;

    // main shifts the items after a deletion, one cell at a time
    searchKey = 55;
    for (j = 0; j < nElems; j++)
        if (arr.getElem(j) == searchKey)
            break;
    if (j < nElems) {
        for (int k = j; k < nElems - 1; k++)
            arr.setElem(k, arr.getElem(k + 1));
        nElems--;
    }
    for (j = 0; j < nElems; j++)
        cout << arr.getElem(j) << " ";
    cout << endl;
    return 0;
}

These are the loops from array.cpp, with arr[j] replaced by arr.getElem(j) and assignments replaced by setElem() calls. main() still keeps nElems, still decides where each item goes, still runs the linear search, and still does the shifting. Our version searches for 26, which isn't there:

77 99 44 55 22 88 11 0 66 33
Can't find 26
77 99 44 22 88 11 0 66 33

The one real gain is that the data is now hidden. The only way to touch the vector is through two member functions, which could later be changed to check every index, for example. But the interface is so primitive that LowArray is little more than an array with a clumsier syntax.

Class Interfaces

A class's interface is the set of public member functions its clients can call. The interface decides how easy the class is to use, and how much its clients need to know about its insides. LowArray shows what goes wrong when the interface is too thin.

Not So Convenient

With LowArray, every client must know that items are packed from index 0, keep its own count, write its own search loop, and remember to shift items after a deletion, in the right direction and stopping at the right place. Two clients might do these things in two different ways, and a client that forgot to shift would silently leave a hole. The interface hands over all of the responsibility and none of the help.

Who's Responsible for What?

A better division of labor asks the class to manage its own data. The client should only have to say what it wants, such as "insert this," "is this here?" or "remove that," and the class should work out how. That means the item count and all three algorithms move out of main() and into the class. The result is the book's HighArray class.

The highArray.cpp Example

// highArray.cpp
// An array class with a convenient interface
#include <iostream>
#include <vector>
using namespace std;

class HighArray {
private:
    vector<double> v;
    // how many cells are in use
    int nElems;

public:
    HighArray(int max) : nElems(0) {
        v.resize(max);
    }

    // linear search: true if searchKey is in the array
    bool find(double searchKey) {
        for (int j = 0; j < nElems; j++)
            if (v[j] == searchKey)
                return true;
        return false;
    }

    // put a new item into the first empty cell
    void insert(double value) {
        v[nElems] = value;
        nElems++;
    }

    // delete one item; false if it wasn't there
    bool remove(double value) {
        int j;
        for (j = 0; j < nElems; j++)
            if (v[j] == value)
                break;
        if (j == nElems)
            return false;

        // close the gap: each higher item moves down one cell
        for (int k = j; k < nElems - 1; k++)
            v[k] = v[k + 1];
        nElems--;
        return true;
    }

    void display() {
        for (int j = 0; j < nElems; j++)
            cout << v[j] << " ";
        cout << endl;
    }
};

The class now owns both the vector and the count, nElems, which the constructor sets to zero. Its four public functions do everything main() used to do.

• insert() puts the new value in cell nElems and adds one to the count.
• find() runs a linear search. It returns true from inside the loop the moment it sees a match, and if the loop finishes, the key wasn't there.
• remove() searches for the value and returns false if it can't find it. Otherwise it shifts the higher items down, reduces the count, and returns true.
• display() prints every item on one line.

Look closely at the shifting loop in remove(). It runs while k < nElems - 1, so its last pass copies v[nElems-1], the final item, into the cell below. If it ran while k < nElems, its last pass would read v[nElems], a cell beyond the last item. Usually that junk would land in a cell that no longer counts, so the mistake could go unnoticed, but when the array is full the read runs off the end of the vector.

Here is the new client:

int main() {
    HighArray arr(100);

    arr.insert(77);  arr.insert(99);  arr.insert(44);
    arr.insert(55);  arr.insert(22);  arr.insert(88);
    arr.insert(11);  arr.insert(0);   arr.insert(66);
    arr.insert(33);
    arr.display();

    double searchKey = 35;
    if (arr.find(searchKey))
        cout << "Found " << searchKey << endl;
    else
        cout << "Can't find " << searchKey << endl;

    arr.remove(0);
    arr.remove(55);
    arr.remove(99);
    arr.display();
    return 0;
}

77 99 44 55 22 88 11 0 66 33
Can't find 35
77 44 22 88 11 66 33

The search for 35 fails. After 0, 55 and 99 are removed, seven items remain, still in their original relative order.

The User's Life Made Easier

Compare the two versions of main(). The LowArray client was full of loops, index arithmetic and bookkeeping. The HighArray client reads almost like plain English: insert these numbers, display them, look for 35, remove three numbers, display again.

There's no nElems in sight, and main() has no way to leave a hole in the array, because it can reach the array only through functions that keep it tidy. The work didn't disappear, of course; the same loops still run. But they're written once, inside the class, where they can be tested once and trusted wherever the class is used.

Abstraction

The client of HighArray knows what the class does. It stores numbers and can insert, find, remove and display them. The client doesn't know how the class does these things, and doesn't need to. It can't tell whether the numbers live in a vector or somewhere else, or which search method find() uses.

Separating what from how is called abstraction, and it's one of the most useful ideas in programming. Because the client depends only on the interface, you could rewrite HighArray to store its data differently or to search faster, and every client would keep working unchanged. Hour 3 does something close to this when it keeps the items in order and switches to a much faster search, and the idea returns in full force in Hour 9, on abstract data types.

The Ordered Workshop Applet

An ordered array keeps its items sorted by key, with the smallest key in cell 0 and each cell holding a key at least as large as the one before it. The book's Ordered Workshop applet shows such an array. It looks and behaves much like the Array applet from Hour 2. The main difference is that pressing New to create an array also asks you to choose a search method, linear or binary.

Insertion

Order comes at a price, and insertion pays it. A new item must take its proper place among the others, so insertion finds the first item with a larger key, moves it and every item above it up one cell, and copies the new item into the gap. On average about N/2 items move, where an unsorted array needed a single move. Deletion works as in Hour 2, shifting the larger items down to close the hole.

Linear Search

If you choose linear search, the applet steps through the cells from the left, just as before, with one small advantage. Because the keys increase from left to right, the search can stop as soon as it reaches a key larger than the one it wants. A failed search therefore gives up about halfway on average, after roughly N/2 comparisons instead of N. A successful search still takes about N/2.

Binary Search

The real payoff of keeping things in order is binary search, which finds an item by repeatedly cutting the range of possible cells in half. The idea is easiest to see in a children's game.

The Guess-a-Number Game

A friend thinks of a number between 1 and 100 and asks you to guess it. After each guess, the friend tells you whether you're too high, too low, or right. You could start at 1 and work upward, but that might take 100 guesses.

The smart move is to guess the middle, 50. Whatever the answer, one guess throws away half the possibilities. Then you guess the middle of the half that's left, and keep going. Here is how the game goes when the secret number is 33.

It took seven guesses, numbered 0 through 6. Each guess is the middle of the remaining range, rounded down when the middle falls between two numbers. Starting from 100 possibilities, at most 50 remain after the first guess, then at most 25, 12, 6, 3 and finally 1, so this strategy never needs more than seven guesses for a number from 1 to 100.

Our Workshop panel turns the game around. You think of a number, and the computer finds it by binary search.

Binary Search in the Ordered Applet

Binary search in an ordered array plays the same game with cell numbers. The applet shows a lower bound and an upper bound enclosing the cells where the key could still be, starting at the first and last cells. At each step it points at the cell halfway between them and compares that cell's key with the one you want.

If the middle key is too small, the lower bound jumps to just past the middle; if it's too large, the upper bound jumps to just before it. Half the remaining cells drop out each time, so while linear search plods from cell to cell, binary search finishes in a handful of steps.

C++ Code for an Ordered Array

The book's program orderedArray.cpp defines a class called OrdArray. It resembles HighArray from Hour 2, with a private vector<double> v, a count nElems, and a small function getSize() that returns the count. The big changes are in find(), which now uses binary search, and in insert(), which keeps the items in order.

Binary Search with the find() Member Function

// orderedArray.cpp
// An array class that keeps its items in ascending order
#include <iostream>
#include <vector>
using namespace std;

class OrdArray {
private:
    vector<double> v;
    int nElems;

public:
    OrdArray(int max) : nElems(0) {
        v.resize(max);
    }

    int getSize() {
        return nElems;
    }

    // binary search: returns the index of searchKey,
    // or nElems if searchKey isn't in the array
    int find(double searchKey) {
        int lowerBound = 0;
        int upperBound = nElems - 1;

        // keep going while the range still holds at least one cell
        while (lowerBound <= upperBound) {
            // look at the cell in the middle of the range
            int curIn = (lowerBound + upperBound) / 2;
            if (v[curIn] == searchKey)
                return curIn;

            // throw away the half that can't contain the key
            if (v[curIn] < searchKey)
                lowerBound = curIn + 1;
            else
                upperBound = curIn - 1;
        }
        // the range is empty, so the key is not here
        return nElems;
    }

lowerBound and upperBound mark the ends of the range still in play. Each pass through the loop computes curIn, the index halfway between them; integer division drops any fraction, so the midpoint of 8 and 15 is 11.

If v[curIn] equals the search key, find() returns the index. If v[curIn] is smaller, the key can only lie to the right, so lowerBound moves to curIn + 1. Otherwise it can only lie to the left, and upperBound moves to curIn - 1. Either way, the middle cell and everything on the wrong side of it are ruled out.

If the key isn't there, the bounds eventually cross, with lowerBound greater than upperBound. The range is empty, the loop ends, and find() returns nElems, a value that can never be the index of a real item. The caller compares the result with getSize() to tell success from failure.

Here is a search for 57 in an array of 16 items. The first step examines cell 7.

Cell 7 holds 45, which is smaller than 57, so the lower half is discarded and lowerBound becomes 8.

Cell 11 holds 70, which is too large, so upperBound becomes 10. The third step examines cell 9 and finds the key.

Binary search found the key in three steps, each examining one cell. A linear search would have examined ten cells, 0 through 9.

The OrdArray Class

The rest of the class handles insertion, deletion and display.

    // put value in its proper place, keeping the order
    void insert(double value) {
        int j;
        // find the first item larger than value
        for (j = 0; j < nElems; j++)
            if (v[j] > value)
                break;

        // move items j and above up one cell, highest first
        for (int k = nElems; k > j; k--)
            v[k] = v[k - 1];

        v[j] = value;
        nElems++;
    }

    bool remove(double value) {
        int j = find(value);
        if (j == nElems)
            return false;

        // close the gap by moving larger items down one cell
        for (int k = j; k < nElems - 1; k++)
            v[k] = v[k + 1];
        nElems--;
        return true;
    }

    void display() {
        for (int j = 0; j < nElems; j++)
            cout << v[j] << " ";
        cout << endl;
    }
};

insert() works in two stages. The first loop scans from the left for the first item larger than the new value, and when it stops, j is the cell where the value belongs (nElems if every item is smaller). The second loop opens a gap at j. It must start at the top and work down, so that each copy lands in a cell that is already free; starting at j would overwrite each item before it had been moved.

remove() calls find(), so deletion also benefits from binary search when it locates the item. The shifting afterward is the same as in HighArray.

The orderedArray.cpp Program

The main() function inserts the same ten numbers as in Hour 2, in the same scrambled order. It then searches for 55, displays the array, removes three items, and displays it again.

int main() {
    OrdArray arr(100);

    // insert ten numbers in scrambled order
    double keys[] = {77, 99, 44, 55, 22, 88, 11, 0, 66, 33};
    for (int j = 0; j < 10; j++)
        arr.insert(keys[j]);

    double searchKey = 55;
    if (arr.find(searchKey) != arr.getSize())
        cout << "Found " << searchKey << endl;
    else
        cout << "Can't find " << searchKey << endl;

    arr.display();

    arr.remove(0);
    arr.remove(55);
    arr.remove(99);
    arr.display();
    return 0;
}

Found 55
0 11 22 33 44 55 66 77 88 99
11 22 33 44 66 77 88

Although the numbers went in scrambled, they come out sorted, because insert() put each one in its place. The last insertion, of 33, is the one pictured above.

Advantages of Ordered Arrays

The trade is easy to state. Searching becomes far faster, insertion becomes slow because half the items must move on average, and deletion is slow in both kinds of array.

So an ordered array pays off when searches are frequent and insertions and deletions are rare. The book's example is a database of company employees, where people are looked up constantly but hiring and firing happen far less often. A retail store's inventory is the opposite case. Items arrive and sell all day, and an ordered array would spend much of its time shifting data around.

Logarithms

Binary search is fast, and logarithms tell you exactly how fast. The word sounds intimidating, but here it has a very concrete meaning. Start with the numbers.

For small arrays the difference hardly matters, since 4 comparisons against 5 is nothing. For a million items, though, binary search needs at most 20 comparisons where linear search averages 500,000, and for a billion items it needs just 30. Making the array ten times bigger adds only three or four steps to a binary search.

The Equation

To see where these numbers come from, think about the search backward. Each step cuts the range in half, so each extra step doubles the range you can handle. If some range takes s steps, a range twice as big takes s + 1, because its first step cuts it back down. Start from a range of 1, which needs no steps, and double it s times. The range r that s steps can cover is

r = 2^s

Seven steps cover 128 values, more than 100, which is why seven guesses are enough for the number game. Ten steps cover 1,024, so a thousand items need 10 comparisons.

The Opposite of Raising Two to a Power

The equation r = 2^s tells you how big a range s steps can handle. A search needs the reverse, the number of steps s for a given range r. The operation that undoes raising 2 to a power is the base-2 logarithm, written log₂, so

s = log₂(r)

In words, log₂(r) is the power you must raise 2 to in order to get r. Since 2¹⁰ = 1,024, log₂(1,024) = 10. When r isn't an exact power of 2, the logarithm has a fractional part, and you round up to get the number of steps. For example, log₂(100) is about 6.64, which rounds up to 7.

Many calculators only have a key for base-10 logarithms. To convert, multiply by 3.322, since log₂(x) = log₁₀(x) × 3.322. For a million items, log₁₀(1,000,000) is 6, and 6 × 3.322 = 19.93, which rounds up to 20, just as the table says.

Storing Objects

So far the arrays have held plain numbers. Real databases hold records with several fields, like the address cards in Hour 1. The book's next program, classDataArray.cpp, shows how an array can hold objects, using a simple record that describes a person.

The Person Class

A Person object has three fields: a last name, a first name, and an age. The constructor fills them in, displayPerson() prints them, and getLast() returns the last name so that other code can use it as the key.

// classDataArray.cpp
// An array of pointers to Person objects, searched by last name
#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Person {
private:
    string lastName;
    string firstName;
    int age;

public:
    Person(string last, string first, int a)
        : lastName(last), firstName(first), age(a) {
    }

    void displayPerson() {
        cout << lastName << ", " << firstName
             << ", age " << age << endl;
    }

    // the key field, used for searching
    string getLast() {
        return lastName;
    }
};

The ClassDataArray Class

The array class, ClassDataArray, is HighArray adapted to hold people. Its vector doesn't contain Person objects themselves. It holds pointers to them, vector<Person*>, and each object is created with new when it is inserted.

class ClassDataArray {
private:
    // each cell points to a Person stored elsewhere in memory
    vector<Person*> v;
    int nElems;

public:
    ClassDataArray(int max) : nElems(0) {
        v.resize(max);
    }

    // free the people still in the array
    ~ClassDataArray() {
        for (int j = 0; j < nElems; j++)
            delete v[j];
    }

    // linear search on the key field; NULL means not found
    Person* find(string searchName) {
        for (int j = 0; j < nElems; j++)
            if (v[j]->getLast() == searchName)
                return v[j];
        return NULL;
    }

    // build a new Person and keep a pointer to it
    void insert(string last, string first, int age) {
        v[nElems] = new Person(last, first, age);
        nElems++;
    }

    bool remove(string searchName) {
        int j;
        for (j = 0; j < nElems; j++)
            if (v[j]->getLast() == searchName)
                break;
        if (j == nElems)
            return false;

        // free the object, then slide the later pointers down
        delete v[j];
        for (int k = j; k < nElems - 1; k++)
            v[k] = v[k + 1];
        nElems--;
        return true;
    }

    void displayA() {
        for (int j = 0; j < nElems; j++)
            v[j]->displayPerson();
    }
};

The last name is the key field. find() takes a search key such as "Stimson" and compares it with v[j]->getLast() for each person, using the string class's == operator. When it finds a match it returns the pointer, which gives the caller the whole record. When it fails, it returns NULL, a pointer to nothing.

insert() receives the three field values, builds a new Person with new, and stores its address in the next free cell. remove() searches by last name, frees the object with delete, and shifts the remaining pointers down. Our version also adds a destructor, ~ClassDataArray(), which runs automatically when the array object is destroyed and frees the people still stored.

Storing pointers pays off whenever items move. When remove() closes a gap, each step copies one pointer, just a few bytes, however big the Person objects are.

The classDataArray.cpp Program

The main() function inserts ten people, searches for one, removes three, and displays the rest.

int main() {
    ClassDataArray arr(100);

    arr.insert("Evans", "Patty", 24);
    arr.insert("Smith", "Lorraine", 37);
    arr.insert("Yee", "Tom", 43);
    arr.insert("Adams", "Henry", 63);
    arr.insert("Hashimoto", "Sato", 21);
    arr.insert("Stimson", "Henry", 29);
    arr.insert("Velasquez", "Jose", 72);
    arr.insert("Lamarque", "Henry", 54);
    arr.insert("Vang", "Minh", 22);
    arr.insert("Creswell", "Lucinda", 18);

    string searchKey = "Stimson";
    Person* found = arr.find(searchKey);
    if (found != NULL) {
        cout << "Found ";
        found->displayPerson();
    }
    else
        cout << "Can't find " << searchKey << endl;

    arr.remove("Evans");
    arr.remove("Smith");
    arr.remove("Yee");
    arr.displayA();
    return 0;
}

Found Stimson, Henry, age 29
Adams, Henry, age 63
Hashimoto, Sato, age 21
Stimson, Henry, age 29
Velasquez, Jose, age 72
Lamarque, Henry, age 54
Vang, Minh, age 22
Creswell, Lucinda, age 18

The search for Stimson succeeds and prints his whole record, and after Evans, Smith and Yee are removed, the other seven people remain in the order they were inserted. This array is unordered, so find() searches linearly. You could keep the pointers sorted by last name and use binary search instead, as OrdArray does with numbers.

Big O Notation

You need a compact way to describe an algorithm's efficiency that doesn't depend on a particular computer. A statement such as "binary search is 50 times faster than linear search" doesn't work, because the ratio changes with the size of the array. For 10 items the two are nearly even, and for a million items binary search wins by a factor of 25,000. What matters is how the running time grows as the number of items, N, grows, and Big O notation is the standard way to describe that growth.

Insertion in an Unordered Array: Constant

Inserting into an unsorted array takes the same time however many items the array holds, because the new item always goes into the next empty cell. The time T is a constant, K.

T = K

K depends on things like the speed of the processor and how well the compiler translates the code. It doesn't depend on N.

Linear Search: Proportional to N

A linear search examines about N/2 items on average, so its time is

T = K × N/2

The 1/2 is just another constant, so it can be folded into K. Calling the combined constant K again gives T = K × N. Double the array and the search takes twice as long.

Binary Search: Proportional to log(N)

Binary search takes about log₂N steps, so T = K × log₂N. Here there's a further simplification. Logarithms in different bases differ only by a constant factor (you saw that log₂N = 3.322 × log₁₀N), so the base can be folded into K as well and left out, giving T = K × log N.

Don't Need the Constant

Big O notation goes one step further and drops K altogether, because K says nothing about how the time grows. What remains is written with a capital O, read as "order of." Insertion into an unsorted array is O(1), linear search is O(N), and binary search is O(log N). The simple sorts in Hours 4 and 5 will turn out to be O(N²), which means that doubling the number of items makes them take four times as long.

Big O can't predict how many microseconds a particular run will take, but it shows how the time changes as N grows, which is what you need when choosing between algorithms for large amounts of data. For small N the constants can matter more, and a simple O(N) method might even beat an O(log N) one. As N grows, the algorithm with the slower growth rate always pulls ahead.

To feel the gap, suppose each step takes one microsecond and N is a million. An O(1) operation takes a microsecond, and an O(log N) one takes about 20 microseconds. An O(N) operation takes a full second. An O(N²) operation takes 10¹² microseconds, which is more than 11 days.

Why Not Use Arrays for Everything?

Arrays are simple, and an ordered array with binary search finds things quickly. They still fall short in two ways, which is why the book has 21 more hours to go.

The first is speed. An unordered array inserts in O(1) time but searches in O(N). An ordered array searches in O(log N) time but inserts in O(N). Either way, deletion takes O(N), because items must shift to fill the gap. For data that is searched, inserted and deleted often, neither kind of array is good enough.

The second weakness is the fixed size. You must choose an array's size when you create it, usually without knowing how much data will arrive. Guess too small and the array overflows; guess too big and the unused cells waste memory. A vector can grow, but growing means allocating a bigger block of memory and copying every item into it, which is slow.

What's needed is a structure that is fast at insertion, deletion and searching, and that grows and shrinks with the data. The book builds toward that goal step by step, with linked lists in Hour 8, binary trees in Hour 15, and hash tables in Hour 21. First, though, Hour 4 takes up a question that ordered arrays raise, which is how to put data into order in the first place.

Sorting

As soon as a database holds more than a handful of records, someone wants to see them in order. You might list names alphabetically, students by grade, customers by zip code, home sales by price, cities by population, countries by gross national product, or stars by how bright they appear. Underneath, each of these is the same job. You arrange the items by the value of one field, the key.

Order also pays off when you search. In Hour 3 you saw that binary search needs only about 20 comparisons to find an item among a million, while a linear search needs about 500,000 on average. Binary search works only on data that is already in order, so sorting is often the preliminary step that makes fast searching possible.

Because sorting is so useful, and can take so long, it has been studied as closely as any problem in computing. Lafore splits the subject into two groups. This hour and the next cover two simple sorts, the bubble sort and the insertion sort. Part III comes back with the fast ones, mergesort in Hour 12 and quicksort in Hours 13 and 14.

The simple sorts run in O(N²) time, which makes them slow for large amounts of data. They still earn their place. They are easy to understand and easy to code, they are quick enough when N is small, and their ideas return inside the advanced sorts. The insertion sort, for example, is often used to finish off the work of quicksort.

Inventing Your Own Sorting Algorithm

Before looking at any code, picture a kids' baseball team. Nine players have wandered onto the field and stand in a line in no particular order. You want them lined up by height, with the shortest player on the left. Think for a moment about how you would do it.

You would probably solve it without much thought. You can see the whole line at once, so you spot the shortest child and wave her to the left end, then spot the next shortest, and so on. If a couple of players are only slightly out of place, you notice that too and fix it with a quick shuffle.

A computer program has no such overview. At any moment it can look at just two items and compare them. Lafore likens this to being very nearsighted. You can make out the two players standing right in front of you, and everyone else is a blur. Whatever method you invent has to be built out of these close-up looks.

That limitation reduces every sorting algorithm to two basic operations, repeated many times.

1. Compare two items to see which one is larger.
2. Swap two items, or in some algorithms copy one item to a new place.

The sorts in this book differ in which pairs they compare and in when and how they move items. That is why each sort gets measured by counting its comparisons and its swaps or copies. Those two counts decide how fast it runs. In a program, each player becomes a number in an array cell, and "taller" becomes "holds the larger value."

Bubble-Sorting the Baseball Players

The bubble sort is famous for being slow, and just as famous for being simple. Here is how it works on the team. Stand at the left end of the line. Compare the players in positions 0 and 1. If the one on the left is taller, have them trade places. If not, leave them alone. Then move one position to the right and compare the players in positions 1 and 2, and keep going this way until you reach the right end. Each step follows three rules.

1. Compare two players.
2. If the one on the left is taller, swap them.
3. Move one position to the right.

Follow the tallest player during this first trip down the line. Until you reach him, nothing happens to him. Once you do, he is compared with each player to his right in turn, and he is always the taller of the two, so he is swapped at every step. He gets carried all the way to the right end, the way a bubble rises through a glass of soda. That is where the name comes from. On each trip down the line, the largest remaining item bubbles up to the end.

A first pass through a line of N players makes N−1 comparisons (8 for our nine players) and some number of swaps that depends on how the players started out. In our line, 7 of the 8 comparisons led to a swap. After the pass, only one player is sure to be in his final place, the tallest.

Now go back to the left end and start a second pass. This time you can stop one position earlier, because the rightmost spot is settled. The second pass carries the second-tallest player to the second spot from the right. The third pass settles the third-tallest, and so on. Each pass puts one more player in his final place and makes the next pass one step shorter. So the rules get one more line: when you reach the first player who is already sorted, go back to the left end and start over. When there are no unsorted players left, you are done.

Here is the whole sort of our team, pass by pass.

The table shows two patterns that matter later. First, the number of comparisons in each pass is fixed: 8, then 7, then 6, down to 1, however the players happened to stand. Second, tall players travel right quickly, but short players creep left slowly. Watch the player of height 2, who starts at the right end. A taller player passing him can push him one place to the left, but that happens at most once per pass, so he needs seven passes to reach position 1.

Notice also that the line was in order after pass 7, yet the rules still call for pass 8. The plain bubble sort has no way to notice that it has finished early. It simply makes all of its passes.

The bubbleSort Workshop Applet

The Workshop applet for this hour draws the data as a row of vertical bars with random heights, one bar per item. Five buttons control it.

• Run animates the whole sort from start to finish, so you can watch the bars shuffle into order.
• Step carries out a single comparison, plus the swap if one is needed, each time you press it.
• Size switches between 10 bars and 100 bars.
• New makes a fresh set of random bars. Pressed again, it produces an inversely sorted set, tallest bar on the left, which is the hardest case for the bubble sort.
• Draw repaints the bars, in case some of them fail to appear properly during a fast run.

While the sort runs, two arrows labeled inner and inner+1 point at the pair of bars being compared. A third arrow, labeled outer, marks the right edge of the unsorted part, and the bars beyond it are finished. Counters show how many comparisons and swaps have been made so far.

With 10 bars you can step through the sort, predict each decision before the applet makes it, and see the tallest remaining bar ride to the right on every pass. With 100 bars the single steps blur together and you see the big picture instead. The tallest bars stack up at the right end in a staircase that grows leftward, while the left side stays a jumble almost until the end. You also get a feel for how slow the bubble sort is once there is a real amount of data.

Implementing C++ Code for a Bubble Sort

The program bubbleSort.cpp keeps its data in a class named ArrayBub, built along the same lines as the array classes of Hour 2. The private data is a vector<double> called v and an int called nElems that counts how many cells are in use. The public interface offers a constructor, insert(), display() and the new member, bubbleSort(). A private helper, swap(), trades two items.

// bubbleSort.cpp
// sorts a list of numbers with the bubble sort
#include <iostream>
#include <vector>
using namespace std;

class ArrayBub
   {
   private:
      // storage for the items
      vector<double> v;
      // how many cells are in use
      int nElems;

      // trade the items held in two cells
      void swap(int one, int two)
         {
         double temp = v[one];
         v[one] = v[two];
         v[two] = temp;
         }

   public:
      // reserve max cells; the array starts out empty
      ArrayBub(int max) : nElems(0)
         { v.resize(max); }

      // add an item just past the last one
      void insert(double value)
         {
         v[nElems] = value;
         nElems++;
         }

      // show every item on one line
      void display()
         {
         for(int j=0; j<nElems; j++)
            cout << v[j] << " ";
         cout << endl;
         }

      void bubbleSort();
   };

Most of the class is familiar. The constructor sizes the vector to hold max items and sets nElems to zero. insert() places a new value in the first free cell, the one at index nElems, and then bumps the count. display() prints the items in order.

swap() needs the temporary variable temp. If you wrote v[one] = v[two] straight away, the old value of v[one] would be overwritten before you had a chance to move it. So the function parks one value in temp, copies the other value across, and then copies the parked value into the second cell. It is private because it is a tool for the class's own use. Code outside the class has no reason to call it.

void ArrayBub::bubbleSort()
   {
   int out, in;
   // out is the last cell of the unsorted part;
   // it moves one cell to the left after every pass
   for(out=nElems-1; out>0; out--)
      {
      // in walks the unsorted part from the left end
      for(in=0; in<out; in++)
         {
         // a bigger item on the left means the pair
         // is out of order, so trade places
         if( v[in] > v[in+1] )
            swap(in, in+1);
         }
      }
   }

The whole algorithm is two nested for loops. The outer loop's variable, out, starts at the last occupied cell, nElems-1, and moves one cell to the left after each pass. Think of it as the right edge of the unsorted part. Every cell with a higher index than out already holds its final item.

The inner loop's variable, in, starts at 0 on every pass and climbs toward out. At each position it compares the neighbors v[in] and v[in+1], and if the left one is larger it calls swap() to exchange them. The loop stops when in reaches out, so the last comparison of each pass is between v[out-1] and v[out]. That final comparison delivers the largest unsorted item into cell out, just before out moves left.

Lafore makes swap() a separate function so that bubbleSort() stays short and readable. A function call costs a little time, though, and this one sits in the innermost loop, where it may run millions of times. A program tuned for speed would put the three lines of the swap directly inside the if statement.

The main() function tests the class. It creates an ArrayBub with room for 100 items, inserts ten numbers in scrambled order, displays them, sorts them and displays them again.

int main()
   {
   // room for 100 numbers, though only 10 are used
   ArrayBub arr(100);

   // ten test values in scrambled order
   double data[] = { 77, 99, 44, 55, 22, 88, 11, 0, 66, 33 };
   for(int j=0; j<10; j++)
      arr.insert( data[j] );

   // show the list, sort it, show it again
   arr.display();
   arr.bubbleSort();
   arr.display();
   return 0;
   }

The first line of output is the data in the order it went in. The second is the same data after bubbleSort() has put it in ascending order.

77 99 44 55 22 88 11 0 66 33
0 11 22 33 44 55 66 77 88 99

Invariants

Many algorithms have a condition that stays true for as long as they run. Such a condition is called an invariant. Spotting it helps you see why an algorithm works, and it gives you something concrete to check when a program misbehaves.

In bubbleSort() the invariant is that the items to the right of out are sorted and sit in their final positions. At the start this holds in a trivial way, because out is at the right end and nothing lies beyond it. Each pass of the inner loop carries the largest unsorted item into cell out, and then out steps one cell left. So the sorted zone on the right grows by exactly one item per pass. Nothing inside that zone is ever touched again, since the inner loop never looks past out.

The invariant also explains why the array must be sorted when the outer loop ends. The last pass runs with out equal to 1, and afterward out drops to 0. By the invariant, every cell from 1 to the end now holds its final item. The single item left over, in cell 0, can only be the smallest, so the whole array is in order.

As a debugging aid, an invariant gives you a precise test. Suppose a sort you wrote leaves the data slightly scrambled. You could add a temporary call to display() at the end of each outer pass and check that the right-hand zone is sorted and unchanged from one pass to the next. The first pass where the check fails is where the bug does its damage.

Efficiency of the Bubble Sort

Counting comparisons is easy, because their number doesn't depend on the data. Take the ten numbers in bubbleSort.cpp. The first pass makes 9 comparisons, the second makes 8, and so on down to a single comparison on the last pass. The total is 9+8+7+6+5+4+3+2+1 = 45.

For N items the sum is (N−1)+(N−2)+(N−3)+…+1, which works out to N×(N−1)/2. For N = 10 that gives 10×9/2 = 45, as expected. When N is large, subtracting 1 hardly changes anything, so the bubble sort makes roughly N²/2 comparisons.

Swaps are fewer, since a swap happens only when a pair is out of order, and their number depends on the data. If the data is random, a swap is needed about half the time, so there are about N²/4 swaps. In the worst case, when the data starts out inversely sorted, every comparison finds a pair out of order and triggers a swap, which gives about N²/2 swaps. Data that is already sorted needs no swaps at all, but the comparisons still run their full course.

Both columns grow in proportion to N². Multiply N by 10 and the work goes up about 100 times. Big O notation ignores constant factors such as the 2 and the 4, so the bubble sort runs in O(N²) time. With 10,000 items it makes about 50 million comparisons. At one microsecond per comparison, that is 50 seconds spent just comparing, before a single swap is counted. You can feel this slowness in the Workshop applet with 100 bars.

There's a quick way to recognize this kind of cost in any code. When one loop is nested inside another, and each loop runs about N times (or N divided by some constant), the body of the inner loop executes roughly N×N times. In the bubble sort the outer loop makes N−1 passes and the inner loop averages about N/2 steps per pass. Nested loops of this kind are a strong hint that an algorithm is O(N²).

How much this matters depends on N. For a few dozen items the whole sort finishes in a blink, and its simplicity is a real virtue. For thousands of items it becomes a nuisance. A million items would need about 500 billion comparisons, close to six days at a microsecond each. The next hour shows a simple sort that does about half the work, and Part III shows sorts that are far faster.

Of the two simple sorts in this book, the insertion sort is the one you would actually choose. It still runs in O(N²) time, but on random data it finishes in roughly half the time the bubble sort needs, and its code is only a little more involved. It is also a favorite finishing tool for faster algorithms. In Hour 14 you'll see quicksort hand its last small jobs to an insertion sort.

Insertion Sort on the Baseball Players

Take the baseball team from Hour 4 again, nine players to be lined up by height. The insertion sort is easiest to understand if you join it in the middle, when the job is already partly done.

Partial Sorting

Imagine a chalk mark on the ground somewhere in the middle of the line. The players to the left of the mark are in order among themselves: each one is taller than the player to his left. They are not necessarily in their final positions, though. Some shorter players are still waiting to the right of the mark, and when their turn comes they will be squeezed in among the sorted group, pushing some of its members to the right.

This differs from the bubble sort. There, the sorted players at the right end were finished and never moved again. Here, the sorted group on the left is only a draft that keeps getting revised as new players join it.

The Marked Player

The player standing just to the right of the mark is the marked player. He and everyone to his right are still unsorted. The next job is to insert him into the right place in the partially sorted group, and it goes like this.

1. The marked player steps out of the line and waits nearby. In a program, this means copying him to a temporary variable. His old spot is now an empty gap.
2. Look at the sorted player just left of the gap. If he is taller than the marked player, he shifts one place right into the gap, and the gap moves one place left.
3. Repeat step 2 with the next player to the left, and keep shifting until the player left of the gap is shorter than the marked player, or until the gap reaches the left end of the line.
4. The marked player steps into the gap.

Inserting this one player took four comparisons (with heights 9, 8, 6 and 4) and three shifts. Now the partially sorted group is one player bigger and the unsorted group one player smaller. Move the mark one place to the right, so the player with height 2 becomes the marked player, and do it all again. He is shorter than everyone in the group except the player of height 1, so five players shift right and he lands in position 1.

The process has to start somewhere, and it starts in the simplest possible way. A single player is always in order with himself, so the mark begins just after the first player. The first marked player is the one in position 1. The sort ends when the mark has passed the last player and everyone has been inserted. If you run the whole insertion sort on the nine players from Hour 4, it takes 28 comparisons and 22 shifts, where the bubble sort needed 36 comparisons and 22 swaps.

The insertSort Workshop Applet

The insertSort applet uses the same bar display and the same buttons as the bubbleSort applet. With 100 bars, press Run and watch the left end of the display. A sorted slope forms there and widens steadily to the right, while the unsorted bars wait on the right side. Each new bar gets slipped into its place somewhere in the slope, which is the partial sorting you just saw with the players.

With 10 bars, Step shows the details. An arrow labeled outer marks the marked bar, playing the role of the chalk mark. An arrow labeled inner shows where the shifting is happening, which is the position of the gap. At the start of each pass the marked bar is copied into temp and drawn off to one side, apart from the others, while the taller bars shift right one at a time. When the gap reaches the right spot, the bar in temp is copied into it. The counters report comparisons and copies. Copies take the place of the bubble sort's swaps, and they are cheaper, as you'll see shortly.

Implementing the Insertion Sort in C++

The program insertSort.cpp uses a class named ArrayIns. It is the ArrayBub class from Hour 4 with two changes. The swap() helper is gone, because the insertion sort never swaps, and bubbleSort() is replaced by insertionSort(). The data (a vector<double> named v and the count nElems), the constructor, insert() and display() are unchanged.

void ArrayIns::insertionSort()
   {
   int in, out;
   // out is the marker; cells to its left are partially sorted
   for(out=1; out<nElems; out++)
      {
      // the marked item steps out of line
      double temp = v[out];
      // the gap starts where the marked item stood
      in = out;
      // while the item left of the gap is bigger than temp,
      // slide it right into the gap; the gap moves left
      while( in>0 && v[in-1] > temp )
         {
         v[in] = v[in-1];
         --in;
         }
      // the marked item steps into the gap
      v[in] = temp;
      }
   }

The outer for loop moves out, the marker, from 1 up to the last occupied cell. It starts at 1 because a single item in cell 0 counts as partially sorted already. At the start of each pass the marked item v[out] is copied into temp, and in is set equal to out. From then on, in is the position of the gap.

The inner while loop does the shifting. It keeps going as long as two things are true: in is greater than 0, so a cell still exists to the left of the gap, and the item in that cell, v[in-1], is larger than temp. Each time around, the loop copies v[in-1] one cell right into the gap and decrements in, which moves the gap one cell left. When either condition fails, the gap is exactly where temp belongs, and the last statement of the pass copies temp into v[in].

The insertion sort has an invariant of its own. At the end of each pass, once temp has been dropped into place, the items in cells 0 through out are partially sorted. After out moves right for the next pass, the same fact reads this way: every item with an index less than out is partially sorted. When out finally moves past the last cell, "every item to its left" means the whole array, so the whole array is sorted.

The main() function is the same as in bubbleSort.cpp, except that it creates an ArrayIns and calls insertionSort(). It inserts the same ten numbers, displays them, sorts them and displays them again, with the same result.

77 99 44 55 22 88 11 0 66 33
0 11 22 33 44 55 66 77 88 99

On these ten numbers the insertion sort makes 36 comparisons and 31 shifts. The bubble sort makes 45 comparisons and 31 swaps on the same data. The number of moves comes out the same, but each of the insertion sort's shifts is a single copy, while each of the bubble sort's swaps is three copies.

Efficiency of the Insertion Sort

Count the comparisons pass by pass. On the first pass the marked item can be compared with at most one item, on the second with at most two, and so on, up to at most N−1 comparisons on the last pass. The largest possible total is 1+2+3+…+(N−1) = N×(N−1)/2, the same sum you met with the bubble sort.

The difference is that the insertion sort usually stops early. On each pass, the while loop quits as soon as it finds an item smaller than temp. In random data that happens, on average, about halfway through the partially sorted group, so a typical pass makes only about half of its possible comparisons. That brings the total down to about N×(N−1)/4, roughly N²/4.

The number of copies is roughly the same as the number of comparisons, since nearly every comparison leads to one shift. A copy is much cheaper than a swap, which needs three copies. So on random data the insertion sort makes about half the comparisons of the bubble sort and moves its data far more cheaply. In practice it runs about twice as fast. It is still an O(N²) algorithm, though, because N²/4 grows as N² and the 4 disappears in Big O notation.

Already Sorted and Almost Sorted Data

The insertion sort shines when the data is already in order, or nearly so. If the data is sorted, the condition in the while loop is false the first time it is tested on every pass, because the item left of the gap is always smaller than temp. No shifting ever happens. The inner loop shrinks to a single comparison, the outer loop makes N−1 passes, and the whole sort takes N−1 comparisons. That is O(N) time.

If the data is almost sorted, with only a few items out of place, most passes still end after one comparison, and only the few misplaced items trigger any shifting. The running time is close to O(N). That makes the insertion sort an excellent choice for data that is only slightly out of order, such as a sorted list with a few new items tacked onto the end.

Inversely Sorted Data

The worst case is data in inverse order. Every marked item is smaller than everything in the partially sorted group, so every pass compares and shifts all the way to the left end. The sort makes every possible comparison, all N×(N−1)/2 of them, and a shift for each one. Lafore's verdict is that in this case the insertion sort runs no faster than the bubble sort, since both make the maximum number of comparisons.

The insertion sort's copy count includes two copies per pass for the marked item itself, one into temp and one back out, which is why sorted data still costs 2×99 = 198 copies. The random rows are averages. They sit slightly above N²/4 = 2,500 because every pass that stops early spends one extra comparison discovering where to stop.

Sorting Objects

For simplicity, the sorts so far have worked on plain numbers. Real programs usually sort records, such as personnel files, parts lists or customer accounts. Each record is an object with several fields, and one field serves as the key. The program objectSort.cpp shows how little the insertion sort has to change to handle this.

Its data items are objects of a class named Person, with three fields: a last name, a first name and an age. The key is the last name. The array class, ArrayInOb, keeps its data in a vector<Person*>, a vector of pointers to Person objects. Its insert() member creates each new person with new and stores the object's address in the next free cell, and its destructor deletes the objects when the array goes away.

class Person
   {
   private:
      string lastName;
      string firstName;
      int age;

   public:
      Person(string last, string first, int a) :
         lastName(last), firstName(first), age(a)
         { }

      // one person per line: last name, first name, age
      void displayPerson()
         {
         cout << "   " << lastName << ", " << firstName
              << " (" << age << ")" << endl;
         }

      // the sort key
      string getLast()
         { return lastName; }
   };

void ArrayInOb::insertionSort()
   {
   int in, out;
   for(out=1; out<nElems; out++)
      {
      // hold on to the marked person's address
      Person* temp = v[out];
      in = out;
      // string's > operator compares the names
      // alphabetically, one letter at a time
      while( in>0 && v[in-1]->getLast() > temp->getLast() )
         {
         v[in] = v[in-1];
         --in;
         }
      v[in] = temp;
      }
   }

The only real change is the comparison. Because v[in-1] and temp are pointers, the code uses the -> operator to call getLast() on the objects they point to. The two strings that come back are compared with >, which the C++ string class defines to compare alphabetically. Everything else is as before, except that temp is now a Person* and each shift copies a pointer.

Storing pointers keeps the moves cheap. Copying a pointer copies a single address. Copying a whole Person on every shift would mean copying two strings and an int. The sort rearranges the vector's cells, and the Person objects themselves never move.

Lexicographical Comparisons

The string class compares strings lexicographically, a formal word for the way a dictionary orders words. It compares the first characters of the two strings. If they differ, the string whose character comes earlier in the alphabet comes first. If they match, it moves on to the second characters, and so on. If one string runs out while every character so far has matched, the shorter string comes first, which is why "Smith" sorts ahead of "Smithers."

So "Smith" comes before "Stimson": both start with S, and at the second letter m comes before t. "Vang" comes before "Velasquez" because a comes before e. Two copies of "Smith" are equal, so neither is greater than the other, and that fact becomes important in the next section. Here is the program's output for ten people.

Before sorting:
   Evans, Patty (24)
   Smith, Doc (59)
   Smith, Lorraine (37)
   Smith, Paul (37)
   Yee, Tom (43)
   Hashimoto, Sato (21)
   Stimson, Henry (29)
   Velasquez, Jose (72)
   Vang, Minh (22)
   Creswell, Lucinda (18)
After sorting:
   Creswell, Lucinda (18)
   Evans, Patty (24)
   Hashimoto, Sato (21)
   Smith, Doc (59)
   Smith, Lorraine (37)
   Smith, Paul (37)
   Stimson, Henry (29)
   Vang, Minh (22)
   Velasquez, Jose (72)
   Yee, Tom (43)

The people come out in alphabetical order of last name. Look at the three Smiths. They went in as Doc, Lorraine and Paul, and they come out in that same order.

Another Feature of Sorting Algorithms: Stability

Sometimes it matters what a sort does with items whose keys are equal. Suppose a company's employee records are already sorted alphabetically by last name. Now you want them sorted by zip code, and within each zip code you want the employees to stay in alphabetical order. You need a sort that leaves equal-key items in the order it found them. Such a sort is called stable.

In the table, the three employees in zip code 30303 come out as Arnold, Castillo, Fong, still alphabetical. An unstable sort could legally produce Fong, Arnold, Castillo instead, because all three have the same key, and you would have to sort each zip code by name all over again.

The bubble sort and the insertion sort are both stable, and the reason lies in their comparisons. The bubble sort swaps two neighbors only when the left one is strictly greater, so two equal items never trade places. The insertion sort shifts an item only while it is strictly greater than temp. When the marked item meets an equal key, the shifting stops and the marked item lands just to the right of it, the same side it started on. The three Smiths in objectSort.cpp kept their order for exactly this reason.

Comparing the Simple Sorts

There is seldom a reason to use the bubble sort. Its one strength is that it is so simple you can write it from memory without a mistake. That makes it tolerable for a small amount of data when you need something working in a hurry. For anything bigger it is too slow.

The insertion sort is the best of the simple sorts. It is about twice as fast as the bubble sort on random data, and it is very fast on data that is almost sorted, where it approaches O(N). For a small amount of data, or data that is nearly in order already, it is usually the right choice.

Both sorts work in place. Besides the original array they need only one extra variable, temp, to hold an item while it moves, and they never need a second array. So memory is no concern with either one. When the amount of data grows large, turn to the advanced sorts of Part III, which are much faster.

A Different Way to Think About Data Structure

The arrays of Part I are the kind of structure you would use in a database program. They hold records that matter in their own right, such as personnel files, inventory lists or financial data, and they let you insert, search for and delete those records. The linked lists and trees of later hours serve the same kind of purpose. The structures of Part II (stacks, queues and priority queues) are different in three ways.

Programmer's Tools

In a database program, the data is the point. The records exist before the program runs and are still there after it stops. Stacks and queues are more often working tools. A program sets one up to help it carry out some task, such as checking a line of code, and throws it away when the task is finished. Their lifetimes are short compared with those of database records.

Restricted Access

In an array you can reach any item directly if you know its index, or find it by searching. In a stack or a queue, access is restricted. Only one item can be read or removed at any given moment: the top item of a stack, or the front item of a queue. The other items are there, but the structure's interface gives you no way to get at them until the accessible item has been removed. This limit is deliberate. It is exactly what makes these structures fit the jobs they do.

More Abstract

Stacks, queues and priority queues are also more abstract than arrays. They are defined mainly by their interface, the set of operations a user can perform, such as putting an item on a stack or taking one off. The mechanism underneath is hidden from the user. In this hour the stack is built on a vector, but it could just as well be built on a linked list, and a program that uses the stack would work the same way. This separation of interface from mechanism leads to the idea of abstract data types, the subject of Hour 9.

Understanding Stacks

A stack allows access to only one data item, the last one inserted. To reach the item below it, you must first remove the top one. Remove that, and the next one down becomes accessible, and so on down to the bottom.

That sounds limiting, yet a great many algorithms depend on it. Later in this hour a stack checks whether the parentheses, braces and brackets in a line of source code are properly matched. Stacks are also used to parse arithmetic expressions such as 3×(4+5) and to traverse the nodes of a tree. They even live inside the microprocessor. When a program calls a function, the address to return to and the function's arguments are pushed onto a stack, and when the function returns they are popped off again.

Three Everyday Stacks

Lafore gives three everyday pictures of a stack. The first is a pile of mail. In many households, letters get tossed onto a pile on the hall table as they arrive. When someone finally sits down to deal with the pile, they start at the top: open the top letter, pay the bill or throw away the ad, then pick up the next letter down, and so on until the table is bare. The letter on top is always the newest arrival. The weakness of this system shows when the pile never quite gets finished, because the letters at the bottom can sit untouched for weeks.

The second picture is a workday full of interruptions. You are deep in a long project, call it A, when a coworker asks for help with task B. While you are helping with B, someone from accounting calls about matter C. You deal with C first, then go back to B, and only when B is done do you return to A. Each interruption is placed on top of the work already in progress, and each finished job uncovers the one beneath it.

The third picture is the spring-loaded stack of plates in a cafeteria. Clean plates are pressed down onto the top of the pile, and a diner can take only the top plate. When one is lifted off, the spring pops the next one up into reach.

Push, Pop and Peek

Stacks come with their own vocabulary. Placing an item on the top of the stack is called pushing it. Removing the top item is called popping it. Reading the top item without removing it is called peeking. The top of the stack is the position of the most recently pushed item, and the bottom is the position of the first item pushed. Because the last item in is always the first item out, a stack is called a LIFO structure.

The Stack Workshop Applet

The Stack Workshop applet draws an array of cells stacked vertically, with the bottom of the stack at the bottom of the display. An arrow labeled top points at the highest occupied cell. Four buttons do the work. New creates a new, empty stack. Push asks you for a value and places it on top. Pop removes the top item and shows you its value. Peek shows you the top item and leaves it where it is. If you try to push onto a stack that is already full, or pop from one that is empty, the applet shows a warning instead of carrying out the operation.

Implementing a Stack in C++

The program stack.cpp builds a stack class named StackX on top of a vector. It has three data members: maxSize, the most items the stack can hold; stackVect, a vector<double> whose cells hold the items, with the bottom of the stack at index 0; and top, the index of the item currently on top.

class StackX
   {
   private:
      // the most items the stack can hold
      int maxSize;
      // the cells; the bottom of the stack is index 0
      vector<double> stackVect;
      // index of the top item; -1 while the stack is empty
      int top;

   public:
      StackX(int s) : maxSize(s), top(-1)
         { stackVect.resize(maxSize); }

      // ++top happens first: step up to a free cell, then store j
      void push(double j)
         { stackVect[++top] = j; }

      // top-- happens after the read: return the top item, then step down
      double pop()
         { return stackVect[top--]; }

      // read the top item but leave it where it is
      double peek()
         { return stackVect[top]; }

      bool isEmpty()
         { return top == -1; }

      bool isFull()
         { return top == maxSize-1; }
   };

The constructor sizes the vector and sets top to −1. Since top is the index of the top item, an empty stack has no valid value for it, and −1 is a natural choice because it is one below the first cell. It also makes push() work the same way every time. The very first push raises top from −1 to 0 and stores the item in cell 0, exactly as later pushes raise it from 0 to 1, from 1 to 2, and so on.

The two key members each fit on one line, and the position of the ++ and -- operators is what makes them work. In push(), the expression ++top increments top before its value is used, so top first moves up to the empty cell above the old top item, and then the new item is stored there. In pop(), the expression top-- uses the current value of top first, so the item on top is fetched, and only then does top drop by one to point at the item below. Swap the operators around and both functions break: push() would overwrite the current top item, and pop() would return the wrong one.

peek() returns the top item without changing top. isEmpty() reports whether top is −1, and isFull() reports whether it has reached the last cell, maxSize-1.

The main() function creates a stack with room for ten items, pushes four numbers, and then pops and prints items until the stack is empty.

int main()
   {
   // a stack with room for ten numbers
   StackX theStack(10);

   theStack.push(20);
   theStack.push(40);
   theStack.push(60);
   theStack.push(80);

   // pop until nothing is left, printing each item
   while( !theStack.isEmpty() )
      {
      double value = theStack.pop();
      cout << value << " ";
      }
   cout << endl;
   return 0;
   }

80 60 40 20

The numbers come out in the reverse of the order in which they went in. The last item pushed, 80, is the first one popped. That is LIFO in action.

Error Handling

Notice that main() calls isEmpty() before every pop. StackX leaves that responsibility to the code that uses it: you are expected to call isFull() before pushing and isEmpty() before popping. The class itself doesn't check.

A sturdier class would do the checking inside push() and pop(). It could print an error message and refuse the operation, as in the version of push() below, or it could throw an exception and let the calling code decide what to do.

// a more careful push: refuse to overfill the stack
void push(double j)
   {
   if( isFull() )
      {
      cout << "Error: the stack is full" << endl;
      return;
      }
   stackVect[++top] = j;
   }

Stack Example 1: Reversing a Word

The first real job for a stack is a tiny one, reversing the letters of a word. Push the letters one at a time, from first to last, and then pop them all. Because a stack hands items back in the opposite order, the letters come out backward. Push the letters of "part" and you pop "trap."

The program reverse.cpp uses the same StackX class with one change: its vector holds char values instead of double, so push() takes a char and pop() and peek() return one. The work is done by a class named Reverser. Its constructor stores the input string, and its doRev() member function produces the reversed output string.

string doRev()
   {
   int len = input.length();
   // one cell per letter is all the room needed
   StackX theStack(len);

   // push the letters from first to last
   for(int j=0; j<len; j++)
      theStack.push( input[j] );

   // pop them all; they come out last letter first
   output = "";
   while( !theStack.isEmpty() )
      output += theStack.pop();
   return output;
   }

doRev() first creates a stack exactly as big as the word, since it will never hold more letters than that. The for loop pushes every character of input. The while loop then pops characters until the stack is empty, appending each one to output with the string class's += operator. The finished output is returned to the caller.

In main(), a loop asks the user for a word, hands it to a new Reverser, and prints the result. Pressing Enter without typing anything ends the program. A short session looks like this.

Type a word (Enter alone quits): part
Backward: trap
Type a word (Enter alone quits): drawer
Backward: reward
Type a word (Enter alone quits):

Stack Example 2: Delimiter Matching

A more serious job for a stack is checking the delimiters in a line of text, the way a compiler checks a program's source code. The delimiters are braces { and }, brackets [ and ], and parentheses ( and ). Each opening delimiter must be matched by a closing delimiter of the same type. The matching also has to respect nesting, which means a delimiter opened later must be closed before any delimiter opened earlier. The book uses these examples.

Opening Delimiters on the Stack

The checking program reads the string one character at a time, from left to right, and follows three rules.

• When it reads an opening delimiter, it pushes it onto a stack.
• When it reads a closing delimiter, it pops the top item off the stack and checks that the two delimiters are the same type. A mismatch is an error. If the stack is empty, there is nothing to pop, which is also an error, because the closer has no partner.
• Any other character is ignored.

When the whole string has been read, the stack should be empty. If an opening delimiter is still on it, that delimiter was never closed, and that is an error too. Here is the stack at every step of checking the correct string a{b(c[d]e)f}.

A stack suits this job because the delimiter that must close next is always the one opened most recently, and that is exactly the one on top. The stack remembers the open delimiters in the very order in which they have to be checked. Simply counting openers and closers of each type would not be enough. The string ([)] has one of each and is still wrong. With a stack the algorithm stays short and clear, which is what Lafore means by calling the stack a conceptual aid.

C++ Code for Delimiter Matching

The program brackets.cpp uses the char version of StackX again. The checking is done by a class named BracketChecker, which stores the input string. A small private helper, matches(), reports whether an opener and a closer are the same kind, and the check() member function does the rest.

class BracketChecker
   {
   private:
      string input;

      // true when the opener and the closer are the same kind
      bool matches(char opener, char closer)
         {
         return (opener=='{' && closer=='}') ||
                (opener=='[' && closer==']') ||
                (opener=='(' && closer==')');
         }

   public:
      BracketChecker(string in) : input(in)
         { }
      void check();
   };

void BracketChecker::check()
   {
   int len = input.length();
   // at worst, every character is an opener
   StackX theStack(len);
   bool ok = true;

   for(int j=0; j<len; j++)
      {
      char ch = input[j];
      switch(ch)
         {
         // an opener waits on the stack for its partner
         case '{':  case '[':  case '(':
            theStack.push(ch);
            break;

         // a closer must pair with the most recent opener
         case '}':  case ']':  case ')':
            if( theStack.isEmpty() )
               {
               cout << "Error: " << ch << " at position " << j
                    << " has no opener" << endl;
               ok = false;
               }
            else
               {
               char chx = theStack.pop();
               if( !matches(chx, ch) )
                  {
                  cout << "Error: " << ch << " at position " << j
                       << " does not match " << chx << endl;
                  ok = false;
                  }
               }
            break;

         // everything else is ignored
         default:
            break;
         }
      }

   // openers left on the stack were never closed
   if( !theStack.isEmpty() )
      {
      cout << "Error: " << theStack.peek() << " is never closed" << endl;
      ok = false;
      }
   if(ok)
      cout << "Delimiters match" << endl;
   }

check() creates a stack as long as the input string, because in the worst case every character could be an opener. The for loop reads the characters, and a switch statement sorts each one into one of three cases. Openers are pushed. For a closer, the code first checks for an empty stack, which means the closer has no partner. Otherwise it pops the most recent opener into chx and asks matches() whether the two belong together. Every other character falls through to the default case and is ignored.

After the loop, anything still on the stack is an opener that was never closed. The flag ok records whether any error turned up, so the function can announce success when none did. The error messages give the position of the offending character, counting from 0. As in reverse.cpp, main() repeatedly asks for a line of text and hands it to a new BracketChecker. Here is a session using the book's examples.

Type a string (Enter alone quits): a{b(c[d]e)f}
Delimiters match
Type a string (Enter alone quits): a{b(c]d}e
Error: ] at position 5 does not match (
Type a string (Enter alone quits): a[b{c}d]e}
Error: } at position 9 has no opener
Type a string (Enter alone quits): a{b(c)
Error: { is never closed
Type a string (Enter alone quits):

Efficiency of Stacks

Items are pushed onto and popped off a StackX in constant time, O(1). Neither operation compares items or moves any other item. A push adds one to top and copies one item into a cell. A pop copies one item out and subtracts one from top. The time doesn't depend on how many items the stack holds, whether that is three or three million. peek(), isEmpty() and isFull() are O(1) as well.

That speed, together with the tiny interface, is why stacks turn up inside so many algorithms. The price is the restricted access, since you can never reach an arbitrary item. For a programmer's tool that is usually a good trade.

Queues

In Britain, a queue is a line of people waiting for something. In computing, a queue is a data structure that works like such a line. It resembles a stack, except that the first item inserted is the first item removed. That rule is called FIFO, for first-in, first-out. A stack, as you saw in Hour 6, works the other way around, last-in, first-out.

Think of the line at a movie theater. The first person to join it is the first to buy a ticket and go in, and the last person to join is the last one served. Nobody at the back gets served before the people ahead of them.

Queues turn up wherever things must wait their turn. Airplanes wait in a queue on the taxiway for their turn to take off. Data packets wait in queues for their turn to be sent across the Internet. A printer keeps a queue of print jobs and prints them in the order they arrived. Even your keyboard has one. A typeahead buffer holds your keystrokes when you type faster than a program can read them, so none are lost and they reach the program in the order you typed them.

Queues are also used to model real-world waiting lines in simulation programs, such as customers lining up at a bank teller's window or cars waiting at a toll booth. By watching how long the simulated lines grow, a planner can estimate, say, how many tellers are needed.

The names of the queue operations aren't standardized. Adding an item is called insert, put or enqueue, and the item goes in at the back of the queue, called the rear or tail. Taking an item out is called remove, get or dequeue, and the item comes from the front or head. Peek reads the front item without removing it. This hour uses insert, remove and peek, with front and rear.

The Queue Workshop Applet

The Queue Workshop applet shows a queue stored in an array, with one arrow labeled front and another labeled rear. Ins asks for a value and adds it at the rear. Rem removes the item at the front and shows its value. Peek shows the front item without removing it. New creates a new, empty queue.

Watch the arrows as you work. Each insertion moves rear up one cell, and each removal moves front up one cell and leaves an empty cell behind it. After a few insertions and removals, the whole group of items has crept up the array, with empty cells below front. Soon rear reaches the top cell, and the queue seems unable to take another item, even though there are empty cells at the bottom of the array.

One cure would be to shift all the remaining items down to the bottom of the array after every removal, the way a line of people shuffles forward when the person at the head leaves. That works, but it is slow, because every removal would have to move every item still waiting. The better cure is to let the arrows wrap around.

A Circular Queue

When rear reaches the last cell and another item arrives, rear jumps back to cell 0. As long as the queue isn't full, that cell is free, because its item has already left. In effect the two ends of the array are joined into a ring. This is called wraparound, and a queue that uses it is called a circular queue, or a ring buffer.

After rear wraps around, it sits below front, the reverse of the usual arrangement. The items now form two broken sequences. One runs from front up to the top of the array, and the other continues from cell 0 up to rear. Front wraps around in the same way. When it moves past the last cell, it continues from cell 0, and the queue becomes one unbroken sequence again.

C++ Code for a Queue

The program queue.cpp implements a circular queue in a class named Queue. Besides the vector queVect and its capacity maxSize, the class keeps three integers: front, the index of the item that will leave next; rear, the index of the item that arrived most recently; and nItems, the number of items waiting.

class Queue
   {
   private:
      int maxSize;
      vector<double> queVect;
      // index of the item that will leave next
      int front;
      // index of the item that arrived most recently
      int rear;
      // how many items are waiting
      int nItems;

   public:
      Queue(int s) : maxSize(s), front(0), rear(-1), nItems(0)
         { queVect.resize(maxSize); }

      // add an item at the rear
      void insert(double j)
         {
         // rear in the last cell? send it back to just before cell 0
         if(rear == maxSize-1)
            rear = -1;
         // step rear forward, then store the item there
         rear++;
         queVect[rear] = j;
         nItems++;
         }

      // take away the item at the front
      double remove()
         {
         // read the front item, then step front forward
         double temp = queVect[front];
         front++;
         // stepped past the last cell? wrap around to cell 0
         if(front == maxSize)
            front = 0;
         nItems--;
         return temp;
         }

      double peekFront()
         { return queVect[front]; }
      bool isEmpty()
         { return nItems == 0; }
      bool isFull()
         { return nItems == maxSize; }
      int size()
         { return nItems; }
   };

The constructor starts front at 0 and rear at −1, the same trick StackX used for top. The first insertion moves rear up to 0 and stores the item there, which is also where front is waiting.

insert() handles wraparound before it does anything else. If rear is already in the last cell, it is set back to −1, so the increment that follows carries it to cell 0. Then rear moves up one cell, the item is stored there, and nItems goes up by one. remove() works the other way around. It copies the item at front into temp and moves front up one cell. If that step has carried front past the last cell, it wraps back to 0. Then nItems goes down by one and the saved item is returned.

peekFront() returns the front item without changing anything, and isEmpty(), isFull() and size() simply consult nItems. Like StackX, the class trusts its user. It is up to the calling code to check isFull() before inserting and isEmpty() before removing.

The main() function gives the wraparound code a workout. It creates a queue with only five cells and then runs this sequence.

int main()
   {
   // five cells in all
   Queue theQueue(5);

   // four items arrive
   theQueue.insert(10);
   theQueue.insert(20);
   theQueue.insert(30);
   theQueue.insert(40);

   // three leave: 10, 20 and 30
   theQueue.remove();
   theQueue.remove();
   theQueue.remove();

   // four more arrive; rear runs off the end and wraps to cell 0
   theQueue.insert(50);
   theQueue.insert(60);
   theQueue.insert(70);
   theQueue.insert(80);

   // empty the queue, printing items in the order they leave
   while( !theQueue.isEmpty() )
      cout << theQueue.remove() << " ";
   cout << endl;
   return 0;
   }

The first four insertions fill cells 0 to 3. The three removals take out 10, 20 and 30, leaving only 40, with front at cell 3. Inserting 50 uses the last cell, cell 4. Then 60 arrives while rear is in the last cell, so rear wraps to cell 0, and 70 and 80 follow into cells 1 and 2. The queue is now completely full, with rear below front.

The final loop removes and prints items until the queue is empty. front takes 40 from cell 3 and 50 from cell 4, wraps to cell 0, and continues with 60, 70 and 80. The items leave in exactly the order they arrived.

40 50 60 70 80

Efficiency of Queues

As with a stack, items can be inserted into and removed from a queue in O(1) time. insert() and remove() each touch a single cell and adjust a couple of integers, and neither depends on how many items are waiting. The wraparound tests add only a constant amount of work. The circular arrangement is what makes this possible. The shift-everything-down cure mentioned earlier would have made every removal an O(N) operation.

Deques

A deque, pronounced "deck," is a double-ended queue. You can insert items at either end and delete them from either end. The operations might be called insertLeft() and insertRight(), and removeLeft() and removeRight().

A deque can stand in for either of the other two structures. If you use only insertLeft() and removeLeft(), or only the two right-hand operations, it behaves like a stack. If you insert at one end and remove at the other, it behaves like a queue. That makes the deque more versatile than either one, although in practice it is used less often than stacks and queues.

Priority Queues

A priority queue is a more specialized structure. Like an ordinary queue it has a front and a rear, and items are removed from the front. The difference is that the items are kept in order by key value, so the item with the lowest key is always at the front, ready to be removed next. Each new item is inserted at whatever position keeps the order, which may be anywhere from the rear to the front. In the book's version a lower key means a higher priority. Some implementations work the other way around and keep the highest key at the front, but the idea is the same.

Lafore's picture is a person who sorts incoming mail by urgency. As each letter arrives, it goes into the pile at the position its importance deserves, with the most urgent letters on top and the ones that can wait at the bottom. Whenever there is time to deal with mail, the top letter is taken first, so the most urgent matter always gets handled first. Compare that with the plain mail stack of Hour 6, where the newest letter was always on top regardless of what it said.

Priority queues are workhorses in system software. In a preemptive multitasking operating system, the programs waiting to run sit in a priority queue, so the highest-priority program is the one that gets the processor next. Priority queues also appear in many graph algorithms and simulation programs.

The PriorityQ Workshop Applet

The PriorityQ applet implements a priority queue with an ordered array. The item with the smallest key sits at the top of the array, in the highest occupied cell, and larger keys lie toward cell 0. Keeping the smallest item at the top makes removal fast, since Rem simply takes the top item and nothing else has to move.

Insertion is the slow part. When you press Ins with a new key, the applet must find the right place for it. Starting at the top, it shifts every item smaller than the new one up one cell to make room, and then puts the new item into the opening. This is the same shifting you saw in the insertion sort in Hour 5. Peek shows the front item without removing it, and New creates a new, empty priority queue.

No wraparound is needed. The front of the queue is always at cell nItems−1 and the rear is always at cell 0, so the items never creep along the array the way they do in an ordinary queue.

C++ Code for a Priority Queue

The program priorityQ.cpp defines a class named PriorityQ. It keeps its items in a vector named queVect in descending order, with the largest item in cell 0 and the smallest in the top occupied cell, nItems-1. There are no front and rear fields, because those positions never change.

class PriorityQ
   {
   private:
      int maxSize;
      // kept in descending order: largest at 0, smallest on top
      vector<double> queVect;
      int nItems;

   public:
      PriorityQ(int s) : maxSize(s), nItems(0)
         { queVect.resize(maxSize); }

      void insert(double item)
         {
         // begin at the front, where the smallest item sits
         int j = nItems - 1;
         // each item smaller than the newcomer moves up one cell
         while( j>=0 && queVect[j] < item )
            {
            queVect[j+1] = queVect[j];
            j--;
            }
         // the newcomer fills the opening just above cell j
         queVect[j+1] = item;
         nItems++;
         }

      // the smallest item always sits in the top occupied cell
      double remove()
         {
         nItems--;
         return queVect[nItems];
         }

      double peekMin()
         { return queVect[nItems-1]; }
      bool isEmpty()
         { return nItems == 0; }
      bool isFull()
         { return nItems == maxSize; }
   };

insert() starts with j at the front of the queue, the top occupied cell. As long as the item in cell j is smaller than the newcomer, that item is copied up one cell and j moves down. When the loop meets an item that is not smaller, or runs off the bottom of the array, the opening is at cell j+1, and the new item goes there. If the queue is empty, j starts at −1, the loop never runs, and the item lands in cell 0. The book's listing treats the empty queue as a separate case, but the loop covers it naturally.

remove() could hardly be simpler. It reduces nItems by one and returns the item in cell nItems, which is the smallest one. The item stays in the cell, just as a popped item stays in a stack's vector, but it is no longer part of the queue. peekMin() returns the same item without removing it.

The main() function inserts 30, 50, 10, 40 and 20, in that scrambled order, and then removes and prints items until the queue is empty. Along the way the vector passes through the states [30], [50, 30], [50, 30, 10], [50, 40, 30, 10] and finally [50, 40, 30, 20, 10]. The items come out smallest first, whatever order they went in.

10 20 30 40 50

Efficiency of Priority Queues

In this implementation, insertion runs in O(N) time. On average a new item has to move past about half the items in the queue, and in the worst case past all of them. Deletion takes O(1) time, because the smallest item is always waiting in the top cell, and taking it needs no shifting at all.

For a small priority queue, or one where items are inserted rarely, the ordered array is a perfectly good choice, and it is easy to write. When the queue holds many items and insertion speed matters, a different structure does better.

So far the array has done all the work in this book. It was a small database in Hour 2, an ordered array in Hour 3, and the storage inside the stacks and queues of Hours 6 and 7. Arrays have two built-in weaknesses. Inserting or deleting an item in the middle means shifting every item beyond it, which is slow. And you must fix an array's size when you create it, before you know how much data will turn up.

After the array, the linked list is probably the most widely used general-purpose storage structure, and it cures both problems. Items are added and removed by changing a pointer or two, so nothing ever shifts. The list is always exactly as long as the data it holds. You can use a linked list almost anywhere you would use an array. The main exception is a program that keeps asking for items by position number, as in "give me item 517". An array answers that in one step. A list can't.

This hour builds the basic machinery. In Hour 9 you'll use it to rebuild stacks and queues, and in Hour 10 you'll meet sorted lists and doubly linked lists.

Understanding Links

In a linked list, every data item is packed inside an object called a link. The link holds the data plus one extra member, a pointer to the next link in the list. The links can be scattered anywhere in memory. What turns them into a list is that each one knows the address of the link that follows it.

The list as a whole is represented by a second, very small object of class LinkList. It holds a single pointer, pFirst, which points to the first link. The first link's pointer leads to the second link, the second link's pointer leads to the third, and so on down the chain. The last link's pointer holds NULL, the special value that means "points nowhere". That NULL is how code recognizes the end of the list.

A Class That Refers to Itself

Here is the declaration of a link that carries two pieces of data, an integer and a floating-point number.

class Link
   {
   public:
      // The two data items this link carries.
      int iData;
      double dData;
      // Where the following link lives, or NULL if this is the last one.
      Link* pNext;
   };

The interesting member is pNext. Its type is Link*, a pointer to an object of the very class being declared. A class like this is called self-referential. That sounds like a riddle, but the compiler is perfectly happy with it, because pNext is only an address. The compiler knows how much room an address takes, so it can lay out a Link without knowing anything else about it. What a class can't do is contain a complete object of its own type, since that inner object would contain another one, and that one another, forever.

A link can hold any data at all: numbers, strings, a complete object such as the Person records of Hour 3, or a pointer to such an object. The list code never looks at the data except to compare keys. The part it cares about is pNext. The book keeps its links small, with one or two numbers, so the pointer logic stays easy to follow.

Relationships Instead of Positions

In an array, every item sits at a numbered position. If you want the item at index 7, the index takes you there in a single step, however big the array is. A linked list has no position numbers at all. An item belongs to the list only because the link in front of it points to it. So the one and only way to reach an item is to start at pFirst and follow the pointers, link by link, until you arrive.

Lafore compares this to tracking someone down through other people. Say you're looking for Bob. You ask Harry, who has no idea, though he thinks Jane might know. Jane remembers seeing Bob go off with Sally. Sally tells you she gave Bob a ride to Peter's office, and that is where you finally find him. You couldn't have gone straight to Peter's office, because you didn't know about it until Sally told you. Each person knew only the next step.

A linked list works the same way. To reach the fourth link, you must pass through the first, second and third, because only the third link knows where the fourth one is. Keep this picture in mind. It explains both the strengths and the weaknesses of lists that you'll see at the end of this hour.

The LinkList Workshop Applet

The book's LinkList Workshop applet draws each link as a small rectangle showing its key, with an arrow from each rectangle to the next. A long list won't fit across the screen, so the links wrap onto several rows, like words on a page. Four buttons drive it.

• Ins asks for a key, makes a new link holding it, and puts that link at the beginning of the list. The new link's arrow points to the link that used to be first. In an unsorted list, inserting at the front is the fastest insertion there is, because there's nothing to search for and nothing to move.
• Find asks for a key, then moves a red arrow from link to link, starting at the first one, until it reaches the link with that key. You can watch the cost of a list search directly. The farther along the key sits, the longer the arrow travels.
• Del asks for a key, finds its link the same step-by-step way, and then removes it. On screen, the arrow leaving the link before the deleted one swings around to point at the link after it, so the chain simply skips over the deleted link.
• New starts a fresh list. It asks how many links you want and whether the list should be sorted or unsorted. Sorted lists are the topic of Hour 10, so stay with unsorted lists for now.

Our re-creation below works the same way. It also labels the two pointers the C++ code uses while it walks the list, pCurrent and pPrevious. You'll meet both of them in the code later this hour.

Implementing a Simple Linked List

The first program, linkList.cpp, supports only three operations: insert a link at the front of the list, remove the link at the front, and display the whole list. That sounds modest, but those three are exactly what a stack needs, as you'll see in Hour 9. The program has two classes, Link and LinkList, plus a main() that tries them out.

The Link Class

The complete Link class adds a constructor and a function that displays the link's data.

#include <iostream>
#include <cstddef>
using namespace std;

class Link
   {
   public:
      int iData;
      double dData;
      Link* pNext;

      // A new link receives its data and isn't attached to anything yet.
      Link(int id, double dd) : iData(id), dData(dd), pNext(NULL)
         { }

      // Print the data in the form {22, 2.99}.
      void displayLink()
         {
         cout << "{" << iData << ", " << dData << "} ";
         }
   };

The constructor copies its two arguments into the data members and sets pNext to NULL. A brand-new link isn't part of any list yet, so it shouldn't point anywhere. The list code will set pNext when it hooks the link into the chain. displayLink() prints the two data items inside braces, such as {22, 2.99}. The members are public so the list class can reach them directly, which keeps the code short.

The LinkList Class

The LinkList class needs only one data member, the pointer to the first link. Here is the class with everything except displayList(), which comes a little later.

class LinkList
   {
   private:
      // Address of the first link, or NULL when the list is empty.
      Link* pFirst;

   public:
      LinkList() : pFirst(NULL)
         { }

      bool isEmpty()
         { return pFirst == NULL; }

      Link* getFirst()
         { return pFirst; }

      // Make a new link and put it at the front of the list.
      void insertFirst(int id, double dd)
         {
         Link* pNewLink = new Link(id, dd);
         // First, the new link points at the current first link.
         pNewLink->pNext = pFirst;
         // Then the list starts at the new link.
         pFirst = pNewLink;
         }

      // Unhook the first link and give its memory back.
      // Call this only when the list isn't empty.
      void removeFirst()
         {
         Link* pTemp = pFirst;
         pFirst = pFirst->pNext;
         delete pTemp;
         }

      void displayList();
   };

The constructor sets pFirst to NULL, so every new list starts out empty, and isEmpty() simply checks for that value. getFirst() hands out the address of the first link. As you'll see, main() uses it to look at a link before removing it.

The insertFirst() Member Function

insertFirst() is the heart of the class. It creates a new link with new, which returns the address of the new object, and keeps that address in pNewLink. Then it makes two pointer assignments.

1. pNewLink->pNext = pFirst; The new link's pNext now points at whatever link used to be first. If the list was empty, pFirst was NULL, so the new link's pNext becomes NULL. That is correct, because in a one-link list the new link is also the last.
2. pFirst = pNewLink; The list now begins at the new link.

The order of the two assignments matters. Suppose you did the second one first. pFirst would hold the new link's address, and nothing would remember where the old first link was. The other assignment would then make the new link point to itself, and the rest of the list would be adrift in memory with no pointer leading to it.

However long the list is, insertFirst() does the same two assignments. Its running time doesn't depend on N at all, so it's O(1).

The removeFirst() Member Function

removeFirst() undoes what insertFirst() did. The first link's pNext holds the address of the second link, so the statement pFirst = pFirst->pNext; reroutes pFirst past the first link to the second. The old first link is now outside the chain.

In Java, an object that nothing points to is eventually cleaned up by the garbage collector. C++ has no garbage collector. Memory you get with new stays allocated until you hand it back with delete, so removeFirst() has to delete the old link itself. If it didn't, every removal would leave a dead link lying in memory, a problem called a memory leak. That's why the function starts by saving the old link's address in pTemp. Once pFirst moves on, pTemp is the only remaining record of where that link lives, and delete needs the address.

The displayList() Member Function

To display the list, the program has to visit every link in turn, starting at the first.

void LinkList::displayList()
   {
   cout << "List (first-->last): ";
   // Begin at the head of the chain.
   Link* pCurrent = pFirst;
   // Stop when we step past the last link.
   while(pCurrent != NULL)
      {
      pCurrent->displayLink();
      // Move to the neighbor this link points to.
      pCurrent = pCurrent->pNext;
      }
   cout << endl;
   }

The function keeps a pointer called pCurrent that starts at pFirst. Each time around the loop, it displays the link that pCurrent points to and then moves on with pCurrent = pCurrent->pNext;. That statement is the basic step of all list code. It replaces the address in pCurrent with the address stored inside the current link, which is the address of the next link. When pCurrent steps past the last link it picks up that link's NULL, and the loop ends. For an empty list, pCurrent is NULL from the start, so the loop body never runs.

The main() Function

main() builds a list of four links, displays it, and then takes the links off the front one at a time until the list is empty.

int main()
   {
   LinkList theList;

   // Each call puts its link in front of the others.
   theList.insertFirst(22, 2.99);
   theList.insertFirst(44, 4.99);
   theList.insertFirst(66, 6.99);
   theList.insertFirst(88, 8.99);
   theList.displayList();

   while( !theList.isEmpty() )
      {
      // Show the first link while it still exists.
      Link* pTemp = theList.getFirst();
      cout << "Removed ";
      pTemp->displayLink();
      cout << endl;
      // Now it can go.
      theList.removeFirst();
      }
   theList.displayList();
   return 0;
   }

List (first-->last): {88, 8.99} {66, 6.99} {44, 4.99} {22, 2.99}
Removed {88, 8.99}
Removed {66, 6.99}
Removed {44, 4.99}
Removed {22, 2.99}
List (first-->last):

The list comes out in the reverse of the order the links went in. Each insertFirst() puts its link in front of all the others, so the last one inserted (88) ends up first. The loop then removes links from the front until isEmpty() reports true, and the final display shows an empty list. A list used this way behaves like a stack, where the last item in is the first one out. Hour 9 builds on exactly that.

Finding and Removing Specified Links

The second program, linkList2.cpp, keeps everything from the first one and adds two member functions. find() searches the list for a link with a given key. remove() searches for a link with a given key and takes it out of the list, wherever it happens to be. Both treat iData as the key. Like displayList(), they are declared inside the class and defined after it.

The find() Member Function

// Return the link holding this key, or NULL if there isn't one.
Link* LinkList::find(int key)
   {
   Link* pCurrent = pFirst;
   // Keep going while there is a link and it isn't the one we want.
   while(pCurrent != NULL && pCurrent->iData != key)
      pCurrent = pCurrent->pNext;
   return pCurrent;
   }

find() is a traversal that can stop early. pCurrent starts at pFirst and steps along the chain, exactly as in displayList(). The loop keeps going as long as there is a current link and its key isn't the one wanted. It stops for one of two reasons: pCurrent points to a matching link, or pCurrent has become NULL because the search ran off the end of the list. Either way, returning pCurrent gives the caller the right answer, the address of the link or NULL for "not found".

The order of the two tests matters. C++ evaluates && from left to right and stops as soon as the result is known. When pCurrent is NULL, the left test fails and the right test, which reads pCurrent->iData, never runs. That is what you want, because following a NULL pointer crashes the program. Lafore's version checks for the end of the list in a slightly different way. Inside the loop, it looks at whether the current link's pNext is NULL before stepping forward, and returns NULL if it is. Both versions visit the same links. Ours also copes with an empty list, where pFirst itself is NULL.

Once find() has handed you a link, inserting a new link right after it takes just two assignments, the same pattern as insertFirst(). Point the new link's pNext at the found link's successor, then point the found link's pNext at the new link.

The remove() Member Function

Removing a link from the middle of a list is trickier than removing the first one. The pointer that has to change belongs to the link before the one being deleted. In a singly linked list you can only move forward, so once pCurrent has reached the target there's no way to step back. The fix is to carry a second pointer, pPrevious, that trails one link behind pCurrent all the way down the list.

// Unhook and delete the link holding this key.
// Return false if no link holds it.
bool LinkList::remove(int key)
   {
   Link* pPrevious = NULL;
   Link* pCurrent = pFirst;
   // Walk the list with pPrevious one step behind pCurrent.
   while(pCurrent != NULL && pCurrent->iData != key)
      {
      pPrevious = pCurrent;
      pCurrent = pCurrent->pNext;
      }
   // We fell off the end, so the key isn't in the list.
   if(pCurrent == NULL)
      return false;
   // Close the gap around pCurrent.
   if(pCurrent == pFirst)
      pFirst = pFirst->pNext;
   else
      pPrevious->pNext = pCurrent->pNext;
   delete pCurrent;
   return true;
   }

Each time the loop advances, pPrevious takes over pCurrent's old value, and then pCurrent moves on to the next link. When the loop ends, one of three things is true.

• pCurrent is NULL. No link holds the key, so remove() returns false and changes nothing.
• pCurrent is the first link. There is no previous link to fix, so pFirst moves to the second link, just as in removeFirst().
• pCurrent is somewhere further along. The assignment pPrevious->pNext = pCurrent->pNext; makes the previous link point to the link after pCurrent, so the chain now skips over it.

In the last two cases the link is out of the chain, and delete pCurrent returns its memory. Notice that the list never moves anything. However long the list is, removing a link changes exactly one pointer once the link has been found.

The main() Function of linkList2.cpp

This main() builds the same four-link list as before, displays it, and then tries the two new functions.

// Look for the link whose key is 44.
Link* pFound = theList.find(44);
if(pFound != NULL)
   cout << "Found link with key " << pFound->iData << endl;
else
   cout << "Can't find link" << endl;

// Take out the link whose key is 66.
if( theList.remove(66) )
   cout << "Removed link with key 66" << endl;
else
   cout << "Can't remove link" << endl;

theList.displayList();

List (first-->last): {88, 8.99} {66, 6.99} {44, 4.99} {22, 2.99}
Found link with key 44
Removed link with key 66
List (first-->last): {88, 8.99} {44, 4.99} {22, 2.99}

The search for 44 compares three keys (88, 66 and 44) before it succeeds. The removal of 66 compares two keys and then changes a single pointer, the one inside the 88 link.

The Efficiency of Linked Lists

Speed

Insertion and deletion at the beginning of a linked list are about as fast as operations get. insertFirst() and removeFirst() each change a pointer or two, and the number of steps doesn't depend on how many links the list holds. Both are O(1).

Finding a particular link, deleting it, or inserting a new link next to it is another matter, because you have to find the link first, and that means walking from pFirst. On average the target is halfway down the list, so a search takes about N/2 comparisons. For a list of 10,000 links, that's around 5,000. Big O drops the constant, so these operations are O(N), the same as searching an unsorted array.

Even so, the list beats the array at deletions and at insertions in the middle, because once the spot is found, nothing has to move. To delete an item halfway through a 10,000-item array, you compare about 5,000 keys and then shift about 5,000 items down one cell to close the gap. In a list you compare about 5,000 keys and change one pointer. When the items are large objects, copying one takes much longer than comparing a key, and the list's advantage grows.

Memory

A linked list uses exactly as much memory as it needs. Each insertion allocates one link and each removal frees one, and the list can keep growing until the computer runs out of memory. You never have to guess its size in advance.

An array's size is fixed when you create it, which leads to one of two problems. If the array is too small, it overflows when more data arrives than you planned for. If it's too large, the unused cells waste memory. A vector (Hour 2) eases the problem because it can grow, but growing is expensive. The vector has to grab a new, larger block of memory, usually about twice as big, and copy every item into it. Right after it grows, much of the new block sits unused.

The list pays for its flexibility in two ways. First, there is no random access. You can't jump to the 500th link; you have to walk there. That also rules out algorithms that leap into the middle of the data, such as the binary search of Hour 3. Second, every link carries a pointer as well as its data. When the data is a single small number, the pointer can double the memory each item needs.

So linked lists shine when the amount of data is hard to predict and insertions and deletions are frequent. Arrays win when you know roughly how many items you'll have and you need to reach them by position.

An abstract data type, or ADT, is a way of looking at a data structure that concentrates on what it does and ignores how it does it. You have already used two of them. The stack of Hour 6 offered push, pop and peek, and the queue of Hour 7 offered insert, remove and peek. Behind those operations, both classes kept their items in arrays. Nothing about the operations themselves requires an array, though.

The first half of this hour rebuilds the stack and the queue on top of the linked lists from Hour 8. The programs that use them hardly change, and they can't tell the difference. Once you've watched that happen, the idea of an ADT stops being vague, and the second half of the hour looks at what ADTs are and how they help you design software.

A Stack Implemented By a Linked List

Look back at insertFirst() and removeFirst() from Hour 8. One puts an item at the front of the list, and the other takes the front item off. If you call the front of the list the top of a stack, those two functions are push and pop. The linkStack.cpp program makes that connection official.

It uses a slimmed-down version of the Hour 8 list. Each link carries a single double called dData. And removeFirst() now returns the value it removes, because a stack's pop() has to hand the item back to the caller.

class Link
   {
   public:
      double dData;
      Link* pNext;
      Link(double dd) : dData(dd), pNext(NULL)
         { }
      void displayLink()
         { cout << dData << " "; }
   };

class LinkList
   {
   private:
      Link* pFirst;
   public:
      LinkList() : pFirst(NULL)
         { }
      bool isEmpty()
         { return pFirst == NULL; }
      void insertFirst(double dd)
         {
         Link* pNewLink = new Link(dd);
         pNewLink->pNext = pFirst;
         pFirst = pNewLink;
         }
      // Unhook the first link, free it, and return its data.
      double removeFirst()
         {
         Link* pTemp = pFirst;
         double key = pTemp->dData;
         pFirst = pTemp->pNext;
         delete pTemp;
         return key;
         }
      void displayList()
         {
         // The Hour 8 traversal, written as a for loop.
         for(Link* pCurrent = pFirst; pCurrent != NULL; pCurrent = pCurrent->pNext)
            pCurrent->displayLink();
         cout << endl;
         }
   };

The one new detail is in removeFirst(). It copies the link's data into key before it deletes the link, since after delete the data is gone. The traversal in displayList() is the same walk as in Hour 8, squeezed into a for loop: start at pFirst, stop at NULL, and follow pNext at each step.

Now the stack itself. Class LinkStack contains a LinkList object as its only data member, and every one of its member functions is a one-liner that passes the job to the list.

class LinkStack
   {
   private:
      // The items live in this list. Its front is the top of the stack.
      LinkList theList;
   public:
      // Put an item on top.
      void push(double j)
         { theList.insertFirst(j); }
      // Take the top item off and return it.
      double pop()
         { return theList.removeFirst(); }
      bool isEmpty()
         { return theList.isEmpty(); }
      void displayStack()
         {
         cout << "Stack (top-->bottom): ";
         theList.displayList();
         }
   };

int main()
   {
   LinkStack theStack;
   theStack.push(20);
   theStack.push(40);
   theStack.displayStack();

   theStack.push(60);
   theStack.push(80);
   theStack.displayStack();

   theStack.pop();
   theStack.pop();
   theStack.displayStack();
   return 0;
   }

Stack (top-->bottom): 40 20
Stack (top-->bottom): 80 60 40 20
Stack (top-->bottom): 40 20

Each push puts a new link at the front of the list, so the most recent item is always first, which is to say on top. The two pops remove 80 and then 60, the last two items pushed, leaving 40 and 20. LinkStack doesn't even need a constructor of its own. When a LinkStack is created, C++ automatically runs the constructor of its theList member, which sets pFirst to NULL.

Now compare this main() with the one in Hour 6. The push and pop calls are exactly the same. The only change is the line that creates the stack. StackX needed a size, as in StackX theStack(10);, while LinkStack theStack; needs none, because a linked stack never fills up until the computer runs out of memory. For the same reason, LinkStack has no isFull(). Everything else about the storage is invisible to the user of the class. That invisibility is the whole point of this hour.

Both versions push and pop in O(1) time. In the array version, each operation moves top and reads or writes one cell. In the list version, each one changes a pointer or two and calls new or delete.

Double-Ended Lists

A double-ended list is an ordinary linked list with one addition. Besides pFirst, the list object keeps a second pointer, pLast, that points to the last link.

With pLast available, you can attach a new link at the end of the list directly. In an ordinary list you'd first have to walk all N links to find the end, an O(N) job. With pLast it takes a couple of assignments, O(1). Inserting at the end is exactly what a queue needs, as you'll see in the next section.

The firstLastList.cpp program implements a double-ended list. Its Link class is the one-number link from linkStack.cpp.

class FirstLastList
   {
   private:
      Link* pFirst;
      // The extra pointer: the last link in the list.
      Link* pLast;
   public:
      FirstLastList() : pFirst(NULL), pLast(NULL)
         { }
      bool isEmpty()
         { return pFirst == NULL; }

      void insertFirst(double dd)
         {
         Link* pNewLink = new Link(dd);
         // In an empty list, the new link is the last one too.
         if( isEmpty() )
            pLast = pNewLink;
         pNewLink->pNext = pFirst;
         pFirst = pNewLink;
         }

      void insertLast(double dd)
         {
         Link* pNewLink = new Link(dd);
         // Attach the new link after the old last link,
         // or make it the first link if the list is empty.
         if( isEmpty() )
            pFirst = pNewLink;
         else
            pLast->pNext = pNewLink;
         pLast = pNewLink;
         }

      double removeFirst()
         {
         Link* pTemp = pFirst;
         double key = pTemp->dData;
         // Removing the only link empties both ends.
         if(pFirst->pNext == NULL)
            pLast = NULL;
         pFirst = pFirst->pNext;
         delete pTemp;
         return key;
         }

      void displayList();
   };

Each function has to take care of a special case, the moment when pFirst and pLast must change together.

• insertFirst() works as before, except that when the list is empty, the new link is also the last link, so pLast must point to it too. The emptiness test has to come first, while pFirst still tells the truth about the old list.
• insertLast() makes the old last link's pNext point to the new link and then moves pLast to the new link. When the list is empty there's no old last link to attach to, so the new link becomes the first link instead. The new link's own pNext is already NULL, set by the Link constructor, which correctly marks it as the end.
• removeFirst() works as before, except when it removes the only link. Then the list becomes empty, and pLast must become NULL as well. Otherwise it would go on pointing at a link that has just been deleted.

The main() in firstLastList.cpp inserts 22, 44 and 66 at the front, inserts 11, 33 and 55 at the end, and displays the list. Then it removes the first two items and displays the list again.

List (first-->last): 66 44 22 11 33 55
List (first-->last): 22 11 33 55

The items inserted at the front pile up in reverse order (66 44 22), while the items inserted at the end line up in the order they arrived (11 33 55). The two calls to removeFirst() take away 66 and 44.

A double-ended list does nothing for removing the last link, though. To remove it you would have to make the next-to-last link's pNext NULL and move pLast back to that link. The only way to find the next-to-last link is to walk from pFirst, which is O(N), because the pointers lead only forward. The doubly linked list of Hour 10 solves this by giving every link a backward pointer as well.

Implementing a Queue Using a Linked List

A queue inserts items at the rear and removes them from the front. A double-ended list does both of those in O(1) time: insertLast() adds a link at the end, and removeFirst() takes one off the front. So linkQueue.cpp wraps a FirstLastList inside a LinkQueue class, in the same way LinkStack wrapped a LinkList. Each program in this hour is a self-contained file with its own copy of the list class. In this program's copy, displayList() prints only the items, and displayQueue() puts a label in front of them.

class LinkQueue
   {
   private:
      // The front of the queue is the first link; the rear is the last.
      FirstLastList theList;
   public:
      bool isEmpty()
         { return theList.isEmpty(); }
      // New items join at the rear.
      void insert(double j)
         { theList.insertLast(j); }
      // Items leave from the front.
      double remove()
         { return theList.removeFirst(); }
      void displayQueue()
         {
         cout << "Queue (front-->rear): ";
         theList.displayList();
         }
   };

The main() for this program inserts 20 and 40 and displays the queue, inserts 60 and 80 and displays it again, and then removes two items and displays what's left.

Queue (front-->rear): 20 40
Queue (front-->rear): 20 40 60 80
Queue (front-->rear): 60 80

Items leave in the order they arrived. The first two in, 20 and 40, are the first two out. Compare this with the array-based Queue class of Hour 7. That class needed a fixed size, a count of items, and wraparound code to move front and rear back to the start of the array. None of that is needed here. The front of the queue is simply pFirst, the rear is pLast, and the list grows and shrinks as items come and go.

The applet below makes the "same interface, different insides" idea visible. One set of buttons drives two implementations at once: an array version like StackX and Queue on one side, and a linked-list version like LinkStack and LinkQueue on the other. Every push or insert goes to both, so you can compare what each one does with the same request.

Data Types and Abstraction

With two stacks and two queues in hand, it's time to look at the idea behind them. The phrase "abstract data type" has two halves, and each is worth taking apart.

Data Types

The phrase data type is used first for built-in types such as int and double. When you declare an int, you get more than a place to keep a number. You get a set of values, the whole numbers within a certain range (on a typical 32-bit system, from about −2.1 billion to about +2.1 billion). You also get a set of operations that are allowed on those values, such as +, −, *, / and comparisons. The operations are part of the type. You can use % to find the remainder when one int is divided by another, but C++ won't let you apply % to a double.

Classes let you create data types of your own. A class says what data its objects hold and which member functions may operate on that data, just as the language defines the values and operators of an int. A stack class is a new data type whose operations are push, pop and peek. A queue class is a data type with insert, remove and peek. Once such a class is written, you can declare a stack as easily as you declare an int.

Abstraction

To abstract something is to consider it apart from its detailed specification or implementation. An abstraction keeps the essential idea and leaves out the machinery. When you drive a car, you think of it as something that speeds up when you press the pedal. You don't think about fuel pressure or valve timing, even though they are what make the car move.

In object-oriented programming, then, an abstract data type is a class considered without regard to its implementation. It is a description of the data the class holds, plus a list of the operations that can be carried out on that data and instructions on how to use them. Users of the class know what each operation does. They don't know how it does it, and they don't need to.

The stack is a good example. For the main() in Hour 6 and the main() earlier in this hour, a stack was simply "something you push items onto and pop them off, where the last item pushed is the first one popped". That description is the ADT. StackX, with its vector, and LinkStack, with its linked list, are two different implementations of the same ADT.

The Interface

The set of operations an ADT offers to the outside world is called its interface. In a C++ class, the interface is the list of public member functions, along with any rules for using them, such as "check isEmpty() before you call pop()". Everything private belongs to the implementation: the data members, plus any helper functions the class uses internally. A user who sticks to the interface never depends on the private parts, which is why those parts can be replaced.

ADT Lists

The word "list" is used for an ADT too. A list, sometimes called a linear list, is a group of items arranged in a linear order, one after another. Typical operations are insert an item, delete an item, and read an item (for example, the item at a given place in the order). Don't confuse this list ADT with the linked list. A list ADT can be implemented with an array or with a linked list, in the same way that a stack can.

Using ADTs as a Design Tool

The ADT idea is a practical help when you design a program. Before you decide how to store your data, decide what you need to do with it. Perhaps the program needs the most recently added item, or items in the order they arrived, or fast search by key. Those needs define the operations, and the operations define the ADT: a stack, a queue, or something else.

Only after the operations are settled do you choose an implementation, and you choose the one that makes the most frequent operations fast. Then you write the rest of the program against the interface alone. Two good things follow. The design stays clean, because the code that uses the data structure contains no storage details. And you can change the implementation later without touching that code. If an array-based stack turns out to overflow in real use, you can drop in the linked-list version, and the calling code keeps working, as you saw with LinkStack.

For stacks and queues, Big O doesn't settle the choice, because both versions do their main operations in O(1) time. The deciding question is usually how much data to expect.

• Use an array when you know in advance roughly the largest number of items you'll need to hold, and you want speed. The array version is quicker in practice, because it doesn't call new and delete for every item, and it spends no memory on pointers.
• Use a linked list when you can't predict how many items there will be. It never fills up, and it uses memory only for the items it actually holds.

Abstract Is a Relative Term

Abstraction comes in degrees. Take the priority queue of Hour 7. As an ADT, it is defined by its operations: insert an item, and remove the item with the smallest key. In Hour 7 you implemented it with an ordered array. It could also be implemented with a heap, a structure this book doesn't cover. From the priority queue's point of view, the ordered array is just the implementation. But the ordered array is itself an abstraction, built on something lower down, the computer's memory, which is a long row of numbered storage locations.

So stacks, queues and priority queues are more abstract than arrays and linked lists, which in turn are more abstract than raw memory. Which of these you call "the ADT" and which "the implementation" depends on where you're standing. To someone writing a program that schedules jobs, the priority queue is the ADT and the array is a hidden detail. To the person writing the PriorityQ class, the array is a tool with its own interface of cells and indices. Even the linked list can be seen as an ADT, with an interface of insertFirst(), find() and remove() that hides how its pointers are arranged.

The lists of Hour 8 and Hour 9 kept their links in whatever order you happened to insert them, and they could only be walked from front to back. This hour lifts both limits. First you'll keep a list in order by key, and then you'll give each link a second pointer so the list can be walked backward too.

Sorted Lists

In the lists you've seen so far, the order of the links had nothing to do with their keys. In a sorted list, the links are kept in order by key, usually ascending, with the smallest key first.

Most operations work just as before. Finding a link, or deleting a specific one, still means walking from the front and comparing keys along the way. The change is in insertion. A new link can't simply go at the front. It must go in its proper place, just after the last link with a smaller key and just before the first link with a larger one. So every insertion now includes a search.

Sorted Lists and Sorted Arrays

A sorted list does much the same job as the ordered array of Hour 3, and each one has an edge over the other.

• Insertion is faster in the list. Both structures have to find the right spot. After that, the array must shift every larger item up one cell to open a gap, while the list just changes two pointers. The list also never fills up.
• Searching is faster in the array. Binary search works by jumping straight to the middle of the remaining range, and that needs random access by index. A list can only be searched link by link, so its searches stay at O(N).

So a sorted list is a good substitute for a sorted array when insertions are frequent or the amount of data is hard to predict. It also makes a simple priority queue, because the smallest item is always at the front, where it can be removed in one step. And, as the next section shows, it can be used to sort an array.

The LinkList Workshop Applet in Sorted Mode

The LinkList Workshop applet from Hour 8 can build a sorted list. When you press New, it asks whether the new list should be sorted or unsorted. Choose sorted, and from then on Ins puts each new link in order. It walks from the start of the list until it reaches the first link with a larger key, then links the new one in just before it. The applet below is set to sorted mode.

C++ Code to Insert an Item

The sortedList.cpp program uses one-number links like those of Hour 9, and its SortedList class keeps the usual pFirst. The interesting member function is insert().

void SortedList::insert(double key)
   {
   Link* pNewLink = new Link(key);
   // pCurrent examines each link; pPrevious remembers the one before it.
   Link* pPrevious = NULL;
   Link* pCurrent = pFirst;
   // Move past every link whose key is smaller than the new key.
   while(pCurrent != NULL && pCurrent->dData < key)
      {
      pPrevious = pCurrent;
      pCurrent = pCurrent->pNext;
      }
   // The new link belongs between pPrevious and pCurrent.
   pNewLink->pNext = pCurrent;
   if(pPrevious == NULL)
      pFirst = pNewLink;
   else
      pPrevious->pNext = pNewLink;
   }

Like remove() in Hour 8, insert() needs two pointers. pCurrent looks at each link in turn, and pPrevious trails one link behind, because the link before the insertion point is the one whose pNext will have to change. The loop moves both pointers forward as long as the current key is smaller than the new one. It can stop in three situations.

• At the very start. The list is empty, or the new key is no larger than the first key. The loop body never runs, pPrevious is still NULL, and the new link becomes the first link: pFirst = pNewLink.
• In the middle. pCurrent stops at the first link whose key is at least as big as the new key. The new link goes between pPrevious and pCurrent.
• Past the end. Every key was smaller, so pCurrent ran off the end and is NULL. The new link goes after pPrevious, the old last link. Its pNext gets the NULL in pCurrent, which correctly marks it as the new end.

The last two situations need exactly the same assignments, which is why the code has only one if. In every case the new link points forward to pCurrent, and whichever pointer used to lead to pCurrent (either pFirst or pPrevious->pNext) now leads to the new link. Unlike in insertFirst(), the order of these two assignments doesn't matter here, because pCurrent keeps its own copy of the address of the next link.

The sortedList.cpp Program

Besides insert(), the SortedList class has isEmpty(), displayList(), and a remove() that takes off the first link and returns its key. It is the removeFirst() of Hour 9 under a new name. Because the list is sorted, the first link always holds the smallest key, so remove() always hands back the minimum.

The main() function inserts 20 and 40 and displays the list. Then it inserts 10, 30 and 50, displays the list again, removes one item, and displays it a third time.

List (first-->last): 20 40
List (first-->last): 10 20 30 40 50
List (first-->last): 20 30 40 50

The three new keys exercise all three cases of insert(). The 10 went to the front (the loop never ran), the 30 went into the middle, and the 50 went at the end (pCurrent ran off the list). The single remove() took away 10, the smallest item.

Efficiency of Sorted Linked Lists

Inserting or deleting an arbitrary item in a sorted list takes about N/2 comparisons on average, because the item could belong anywhere along the list. That's O(N). A search for a key that isn't there can stop as soon as it reaches a larger key, but on average it still covers about half the list. Finding or removing the smallest item, on the other hand, is O(1), since it is always at the front.

That combination makes a sorted list a reasonable priority queue when insertion speed isn't critical. Compare it with the ordered-array priority queue of Hour 7. Both take O(N) time to insert and O(1) time to remove the minimum, but the list's insertion moves no items, and the list never fills up.

List Insertion Sort

A sorted list can serve as a fairly efficient sorting mechanism. Suppose you have an array of unsorted items. Take them out of the array one at a time and insert each one into a sorted list. They fall into order automatically as they go in. Then remove them from the list one at a time, always from the front, and put them back into the array. They come out smallest first, so the array ends up sorted. Lafore calls this the list insertion sort.

The listInsertionSort.cpp program works this way. Here the idea is written as a function that sorts a vector in place, using the SortedList class from the previous section.

// Sort v by passing every item through a sorted list.
void listInsertionSort(vector<double>& v)
   {
   SortedList theList;
   int n = v.size();
   // Trip one: each item finds its own place in the list.
   for(int j=0; j<n; j++)
      theList.insert( v[j] );
   // Trip two: the smallest remaining item always comes off first.
   for(int j=0; j<n; j++)
      v[j] = theList.remove();
   }

The program's main() fills an array with 10 random numbers, displays it, sorts it through the list, and displays it again. Because the numbers are random, your output will differ from this run.

Unsorted array: 59 69 41 56 84 15 86 81 37 35
Sorted array:   15 35 37 41 56 59 69 81 84 86

Efficiency of the List Insertion Sort

Start with the comparisons. The first item goes into an empty list without any. Each later item is compared, on average, with about half of the items already in the list before its place is found. Adding that up over all N items gives roughly N²/4 comparisons: about 25 for 10 items and about 250,000 for 1,000 items. That grows as N², so the list insertion sort is still an O(N²) algorithm, in the same class as the bubble sort and insertion sort of Hours 4 and 5.

The copies are where it shines. Each item is copied only twice, once from the array into a link and once from the link back into the array. That makes 2N copies in all: 20 for 10 items, 2,000 for 1,000. The ordinary insertion sort of Hour 5 copies an item every time it shifts one, and the number of shifts grows as N² (about N²/4 on random data, or roughly 250,000 copies for 1,000 items). When copying an item takes much longer than comparing keys, as it does with large records, the list version wins by a wide margin.

The drawback is memory. While the sort runs, the data exists twice, once in the array and once in the list, and every link adds a pointer on top. So the list insertion sort needs about twice as much memory as the array alone. It's a good choice when copies are expensive and memory is plentiful. For large amounts of data, the advanced sorts of Hours 12 to 14 do far better than any O(N²) method.

Doubly Linked Lists

The Trouble with Going Backward

Every list so far has had a built-in limitation. You can only travel forward. The statement pCurrent = pCurrent->pNext takes you to the next link in one step, but there is no matching step to the previous link. To go back, you have to start at pFirst again and walk until you reach the link before the current one.

The book illustrates the problem with a text editor. Suppose the editor stores a document as a linked list, one link per line of text. Moving the cursor down a line is quick, because you just follow pNext. Moving the cursor up a line means finding the previous line, and in a singly linked list that means a walk from the top of the document every time the user presses the up arrow.

A doubly linked list fixes this by giving each link two pointers, pNext to the following link and pPrevious to the one before it.

class Link
   {
   public:
      double dData;
      // Forward: the link after this one.
      Link* pNext;
      // Backward: the link before this one.
      Link* pPrevious;

      Link(double dd) : dData(dd), pNext(NULL), pPrevious(NULL)
         { }
      void displayLink()
         { cout << dData << " "; }
   };

The list object, of class DoublyLinkedList, keeps pointers to both ends, pFirst and pLast, so it is double-ended as well. The first link's pPrevious and the last link's pNext are both NULL.

Traversal

Two display functions walk the list in opposite directions. displayForward() starts at pFirst and follows pNext, exactly like displayList() in earlier hours. displayBackward() is its mirror image. It starts at pLast and follows pPrevious.

void DoublyLinkedList::displayBackward()
   {
   cout << "List (last-->first): ";
   // Start at the far end and follow the backward pointers.
   Link* pCurrent = pLast;
   while(pCurrent != NULL)
      {
      pCurrent->displayLink();
      pCurrent = pCurrent->pPrevious;
      }
   cout << endl;
   }

Insertion

The DoublyLinkedList class has three insertion functions. insertFirst() puts a link at the front, insertLast() puts one at the end, and insertAfter() puts one just after the link holding a given key. Here is the class, with the first two written out.

class DoublyLinkedList
   {
   private:
      Link* pFirst;
      Link* pLast;
   public:
      DoublyLinkedList() : pFirst(NULL), pLast(NULL)
         { }
      bool isEmpty()
         { return pFirst == NULL; }

      void insertFirst(double dd)
         {
         Link* pNewLink = new Link(dd);
         // The old first link, if there is one, must point back at the newcomer.
         if( isEmpty() )
            pLast = pNewLink;
         else
            pFirst->pPrevious = pNewLink;
         pNewLink->pNext = pFirst;
         pFirst = pNewLink;
         }

      void insertLast(double dd)
         {
         Link* pNewLink = new Link(dd);
         // The old last link, if there is one, must point forward to the newcomer.
         if( isEmpty() )
            pFirst = pNewLink;
         else
            {
            pLast->pNext = pNewLink;
            pNewLink->pPrevious = pLast;
            }
         pLast = pNewLink;
         }

      bool insertAfter(double key, double dd);
      void removeFirst();
      void removeLast();
      bool removeKey(double key);
      void displayForward();
      void displayBackward();
   };

Compare insertFirst() with the Hour 9 version. There is one new job. The old first link used to have a NULL pPrevious, and now it must point back at the new link. If the list was empty, there's no old first link, and the new link becomes the last link as well. insertLast() is the mirror image. The old last link points forward to the new link, the new link points back to it, and pLast moves to the new link.

insertAfter() is the most involved of the three. It first finds the link with the given key, then fits the new link in right after it.

// Insert dd just after the link holding key.
// Return false if no link holds key.
bool DoublyLinkedList::insertAfter(double key, double dd)
   {
   Link* pCurrent = pFirst;
   while(pCurrent != NULL && pCurrent->dData != key)
      pCurrent = pCurrent->pNext;
   if(pCurrent == NULL)
      return false;

   Link* pNewLink = new Link(dd);
   // Changes 1 and 2: the new link points ahead to current's
   // old successor and back to current.
   pNewLink->pNext = pCurrent->pNext;
   pNewLink->pPrevious = pCurrent;
   // Change 3: the old successor points back at the new link.
   // If current was the last link, pLast moves instead.
   if(pCurrent == pLast)
      pLast = pNewLink;
   else
      pCurrent->pNext->pPrevious = pNewLink;
   // Change 4: current points ahead to the new link.
   pCurrent->pNext = pNewLink;
   return true;
   }

Once the search has found the link, pCurrent points to it, and four pointers must change to fit the new link in after it.

1. The new link's pNext points to the link that used to follow pCurrent.
2. The new link's pPrevious points back to pCurrent.
3. The link that used to follow pCurrent must point back to the new link. If pCurrent was the last link, there is no such link, and pLast moves to the new link instead.
4. pCurrent's pNext points to the new link.

The order matters again. Change 3 reaches the old successor through pCurrent->pNext, so it must happen before change 4 overwrites that pointer. If change 4 came first, change 3 would reach the new link instead. The new link would end up pointing back at itself, and the old successor would still point back at pCurrent.

Deletion

There are three deletion functions: removeFirst(), removeLast() and removeKey(). removeFirst() works as in a double-ended list, with one extra step. After pFirst moves to the second link, that link becomes the new first link, so its pPrevious is set to NULL. If the removed link was the only one, pLast becomes NULL too.

removeLast() is where the backward pointers pay off. In a singly linked list, removing the last link required a walk to find the next-to-last link. Here the next-to-last link is simply pLast->pPrevious, one step away.

void DoublyLinkedList::removeLast()
   {
   Link* pTemp = pLast;
   // The next-to-last link becomes the end of the list.
   if(pLast->pPrevious == NULL)
      pFirst = NULL;
   else
      pLast->pPrevious->pNext = NULL;
   pLast = pLast->pPrevious;
   delete pTemp;
   }

// Remove the link holding key; return false if there is none.
bool DoublyLinkedList::removeKey(double key)
   {
   Link* pCurrent = pFirst;
   while(pCurrent != NULL && pCurrent->dData != key)
      pCurrent = pCurrent->pNext;
   if(pCurrent == NULL)
      return false;
   // Fix the forward pointer that leads into pCurrent.
   if(pCurrent == pFirst)
      pFirst = pCurrent->pNext;
   else
      pCurrent->pPrevious->pNext = pCurrent->pNext;
   // Fix the backward pointer that leads into pCurrent.
   if(pCurrent == pLast)
      pLast = pCurrent->pPrevious;
   else
      pCurrent->pNext->pPrevious = pCurrent->pPrevious;
   delete pCurrent;
   return true;
   }

Like removeFirst(), removeLast() expects a list that isn't empty, so the caller should check isEmpty() first. When it removes the only link, the list becomes empty, so pFirst is set to NULL, and pLast picks up the NULL from the removed link's pPrevious.

removeKey() searches for the key and then cuts pCurrent out of the list in both directions. In the general case, when the link has neighbors on both sides, it takes two statements.

• pCurrent->pPrevious->pNext = pCurrent->pNext; makes the link before pCurrent point forward past it.
• pCurrent->pNext->pPrevious = pCurrent->pPrevious; makes the link after pCurrent point back past it.

The special cases replace one of those statements. If pCurrent is the first link, there's no link before it, so pFirst moves instead. If it's the last link, pLast moves instead. If it's the only link, both happen, and the list is left empty. Notice also that removeKey() doesn't need a pPrevious pointer trailing behind pCurrent, as remove() did in Hour 8. The link being deleted already knows its predecessor.

The doublyLinked.cpp Program

The main() in doublyLinked.cpp exercises every function. It inserts 22, 44 and 66 at the front and 11, 33 and 55 at the end, then displays the list forward and backward. Next it calls removeFirst(), removeLast() and removeKey(11) and displays the list again. Finally it calls insertAfter(22, 77) and insertAfter(33, 88) and displays the result.

List (first-->last): 66 44 22 11 33 55
List (last-->first): 55 33 11 22 44 66
List (first-->last): 44 22 33
List (first-->last): 44 22 77 33 88

The backward display is the forward one reversed, which shows that the pPrevious pointers are consistent with the pNext pointers. removeFirst() took 66, removeLast() took 55, and removeKey(11) took 11 from the middle. Then 77 went in after 22, and 88 went in after 33. Because 33 was the last link, that final insertion also moved pLast to the 88 link.

Deques, and the Cost of Two Pointers

A doubly linked list is a natural base for the deque of Hour 7, the double-ended queue that can insert and delete at either end. The deque's insertLeft() and insertRight() become insertFirst() and insertLast(), and removeLeft() and removeRight() become removeFirst() and removeLast(). All four are O(1). A double-ended singly linked list can't make that promise, because its removeLast() would need an O(N) walk.

The extra pointer has a price, though. Every insertion and deletion must now change four pointers instead of two, so the code is longer and has more places for a mistake to hide. Each link is bigger too, since it carries two pointers along with its data. When a program never needs to move backward or remove from the end, a singly linked list is the leaner choice.

Recursion is a programming technique in which a function calls itself. The first time you see it, it can look like a dog chasing its own tail. It works because each call tackles a smaller version of the problem than the call before it, until the problem becomes so small that the answer is obvious.

This hour works through several examples: triangular numbers, anagrams, and a recursive version of binary search. Along the way you'll see what makes a recursive function work, what it costs, and how the computer actually carries it out. Recursion is the foundation for the rest of Part III. The Towers of Hanoi and mergesort in Hour 12, the quicksort of Hours 13 and 14, and the tree algorithms of Hours 15 to 20 all depend on it.

Demonstrating Recursion with Triangular Numbers

The Pythagoreans, the circle of ancient Greek mathematicians around Pythagoras, are said to have seen something mystical in the series 1, 3, 6, 10, 15, 21, and so on. Each term is the previous term plus n, where n is the term's position in the series. The second term is 1 + 2 = 3, the third is 3 + 3 = 6, the fourth is 6 + 4 = 10, and the fifth is 10 + 5 = 15.

These are called triangular numbers, because each one can be drawn as a triangle of objects: a row of 1, a row of 2 beneath it, then a row of 3, and so on. The fourth triangular number, 10, is a triangle with rows of 1, 2, 3 and 4 objects. For the code that follows, it helps to tip the triangle over and think of it as columns, a column of 4, then 3, then 2, then 1.

Finding the nth Term with a Loop

To find the nth triangular number, add up the column heights: n for the tallest column, n − 1 for the next one, and so on down to 1. A loop does that directly.

int triangle(int n)
   {
   int total = 0;
   // Add the columns, from the tallest (n) down to the shortest (1).
   for(int column = n; column > 0; column--)
      total += column;
   return total;
   }

For n = 4, the loop adds 4, 3, 2 and 1 and returns 10. Nothing about this is surprising. The interesting part is that the same answer can be reached by a completely different route.

Finding the nth Term with Recursion

Look at the columns again. The nth triangular number is the tallest column, which is n high, plus the sum of all the remaining columns. And the remaining columns form a smaller triangle, the (n − 1)th triangular number. So if you already had a function that could compute triangular numbers, you could get the nth one as n plus that function's answer for n − 1.

That is the recursive idea, and the function you "already have" is the very function you're writing.

int triangle(int n)
   {
   // A triangle with one column holds exactly one object.
   if(n == 1)
      return 1;
   // Otherwise: the tallest column plus the smaller triangle beside it.
   return n + triangle(n-1);
   }

Each call hands a slightly smaller job to another call of the same function. triangle(4) needs the total of the three columns to its right, so it asks triangle(3), which asks triangle(2), and so on. You can picture a line of assistants. Each one takes care of a single column and passes the rest of the job down the line, then adds its own column to whatever answer comes back.

The Base Case

Something has to stop the chain. If triangle() always called itself, the calls would go on forever, or in practice until the program ran out of memory and crashed. The recursive version stops when n is 1. The first triangular number is simply 1, so the function returns 1 without calling itself again. A condition like this, where the function answers directly, is called the base case. Every recursive function needs at least one, and every chain of calls must eventually reach it.

What's Really Happening

To watch the recursion at work, you can add output statements that report each time the function is entered and each time it returns.

int triangle(int n)
   {
   cout << "Entering: n=" << n << endl;
   if(n == 1)
      {
      cout << "Returning 1" << endl;
      return 1;
      }
   // Wait here for the smaller triangle, then add this column.
   int answer = n + triangle(n-1);
   cout << "Returning " << answer << endl;
   return answer;
   }

Here is what it prints when main() calls triangle(5).

Entering: n=5
Entering: n=4
Entering: n=3
Entering: n=2
Entering: n=1
Returning 1
Returning 3
Returning 6
Returning 10
Returning 15

Each time triangle() is called, it gets its own fresh copy of n. The calls with n = 5, 4, 3 and 2 each stop partway through, waiting for the call below them to return. Only the call with n = 1 can answer at once, and it returns 1. Then the waiting calls finish in reverse order. The n = 2 call adds its 2 to the 1 it got back and returns 3. The n = 3 call returns 3 + 3 = 6, the n = 4 call returns 4 + 6 = 10, and finally the n = 5 call returns 5 + 10 = 15 to main().

The Triangle applet below replays this process one step at a time. It shows the stack of unfinished calls growing as the function calls itself and shrinking as each call returns, with an "Entering" or "Returning" line for every step.

Characteristics of Recursive Functions

Simple as it is, triangle() has the three characteristics that every recursive function shares.

1. It calls itself.
2. When it calls itself, it does so to solve a smaller problem.
3. There is some version of the problem that is simple enough for the function to solve and return without calling itself. This is the base case.

In triangle(), the smaller problem is the triangle with one column fewer, and the base case is the one-column triangle. Every call moves one step closer to the base case, which guarantees that the chain of calls comes to an end.

The Cost of Recursion

Recursion is not especially efficient. Every function call has overhead. Control has to jump to the start of the function, and the arguments and the address to return to have to be saved, which the computer does by pushing them onto an internal stack. When the function returns, they are popped off again. A recursive triangle(1000) makes 1,000 calls and pays that overhead every time, while the loop version just goes around its loop 1,000 times. The loop is usually faster.

There is a memory cost as well. All the unfinished calls wait on the stack at the same time, so a recursion that goes very deep, many thousands of calls, can use up the space set aside for that stack. This is called a stack overflow, and it usually crashes the program.

Recursion earns its place for a different reason. It can make a problem conceptually simpler. For some problems the recursive solution is short and clear, while a loop version would be long and hard to get right. The anagram example later in this hour is one such problem, and the Towers of Hanoi and the fast sorts of the coming hours are others.

Mathematical Induction

Recursion has a counterpart in mathematics. Mathematical induction is a way of defining something in terms of itself. Using it, the triangular numbers can be defined like this.

• tri(n) = 1, if n = 1
• tri(n) = n + tri(n − 1), if n > 1

The first line is the base case, and the second is the recursive step. Put side by side with the recursive C++ function, the definition reads almost line for line like the code. The definition only looks circular. Each use of it refers to a smaller n, and the smallest case is defined outright.

Factorials

Factorials are another classic example of the same pattern. The factorial of n, written n!, is the product of the whole numbers from 1 to n. It can be defined recursively: the factorial of n is n times the factorial of n − 1, and by definition the factorial of 0 is 1.

int factorial(int n)
   {
   // By definition, 0! is 1. This is the base case.
   if(n == 0)
      return 1;
   // n! is n times the factorial of the next smaller number.
   return n * factorial(n-1);
   }

The function is triangle() with two small changes: the base case is n = 0 instead of n = 1, and the operation is multiplication instead of addition. Factorials grow far faster than triangular numbers, though.

Demonstrating Recursion with Anagrams

Here is a problem where recursion gives a neat solution that would be hard to find any other way. Suppose you want to list all the anagrams of a word. In this hour, an anagram means any arrangement of the word's letters, whether or not the result is a real word. The three-letter word cat has six: cat, cta, atc, act, tca and tac.

Try listing the anagrams of a five-letter word by hand and you'll soon find how easy it is to miss some or write others twice. You need a system.

The Algorithm

The system Lafore uses works on the rightmost letters of the word. To anagram a word of n letters:

1. Anagram the rightmost n − 1 letters.
2. Rotate all n letters.
3. Repeat these steps n times.

To rotate a group of letters means to shift every letter one position to the left, except the leftmost letter, which moves around to the right end. Rotating cat gives atc, rotating again gives tca, and a third rotation brings back cat.

Each rotation gives a different letter the first position of the group. While that letter sits in front, step 1 produces every arrangement of the letters behind it. After n rotations, each of the n letters has had its turn in front, and the group is back the way it started.

That leaves the question of how to anagram the rightmost n − 1 letters in step 1. The answer is to do it the same way, by anagramming the rightmost n − 2 of them, rotating those n − 1, and repeating. That is the recursion. The group shrinks by one letter at each level, until it is a single letter, which has only one arrangement and needs no work. That is the base case.

Here is how the algorithm handles cat. The outer level rotates all three letters, three times. Before each rotation, the inner level anagrams the last two letters, which means showing the word, swapping the last two letters by rotating them, and showing the word again.

The C++ Code

The anagram program keeps the word in a string data member called workStr, with its length in size and a running total of words displayed in count. The recursive member function doAnagram() takes one argument, newSize, the number of letters at the right end of the word that it should anagram. The first call passes the length of the whole word.

// Produce every arrangement of the rightmost newSize letters.
void doAnagram(int newSize)
   {
   // A single letter has only one arrangement.
   if(newSize == 1)
      return;
   // Give each letter of the group a turn at the front.
   for(int turn = 0; turn < newSize; turn++)
      {
      // Arrange everything behind the front letter.
      doAnagram(newSize - 1);
      // Only the two-letter level displays, so each word appears once.
      if(newSize == 2)
         displayWord();
      // Bring the next letter of the group to the front.
      rotate(newSize);
      }
   }

The loop runs newSize times, once for each letter that will take a turn at the front of the group. Inside it, the function calls itself to anagram the smaller group, then rotates its own group. The display happens only at the level where newSize is 2. At that moment the call to doAnagram(1) has just returned without doing anything, so the word holds a fresh arrangement that no other level has displayed. If every level displayed the word, the same arrangement would be printed several times.

// Rotate the rightmost newSize letters one place to the left.
void rotate(int newSize)
   {
   int position = size - newSize;
   char first = workStr[position];
   // Slide the rest of the group one place left.
   for(int j = position + 1; j < size; j++)
      workStr[j-1] = workStr[j];
   // The old front letter goes to the far right.
   workStr[size-1] = first;
   }

// Show the current arrangement, numbered, six to a line.
void displayWord()
   {
   count++;
   cout << setw(2) << count << " " << workStr << "   ";
   if(count % 6 == 0)
      cout << endl;
   }

rotate() works out where its group begins. If the word has 4 letters and the group has 3, the group starts at position 4 − 3 = 1. It saves the group's first letter, slides the other letters one cell to the left, and drops the saved letter into the last cell. displayWord() numbers each arrangement and starts a new line after every sixth one. It uses setw(), so the program includes the iomanip header.

The Output

Given the word cats, the program prints all 24 arrangements.

 1 cats    2 cast    3 ctsa    4 ctas    5 csat    6 csta
 7 atsc    8 atcs    9 asct   10 astc   11 acts   12 acst
13 tsca   14 tsac   15 tcas   16 tcsa   17 tasc   18 tacs
19 scat   20 scta   21 satc   22 sact   23 stca   24 stac

The pattern is easy to see. The first six arrangements all begin with c, the next six with a, then six with t and six with s. Each block of six is every arrangement of the other three letters, produced by the level below while one letter held the front position.

A word of n letters has n! arrangements: n choices for the first letter, n − 1 for the second, and so on. So cats, with 4 letters, has 4! = 24, and a five-letter word has 5! = 120. A 10-letter word has 10! = 3,628,800, which would take a while to print. If the word contains a repeated letter, some arrangements come out more than once. The algorithm treats the two t's in tot as different letters, so it prints tot, tto and ott twice each.

Demonstrating Recursion in a Binary Search

Remember the binary search of Hour 3. It finds a key in an ordered array by repeatedly halving the range: look at the middle cell, decide which half must hold the key, and repeat on that half. In Hour 3 the find() function did this with a loop that adjusted lowerBound and upperBound each time around. The same algorithm can be written recursively, and it's a natural fit, because each step is a smaller copy of the same problem, a search of half the range.

The binarySearch.cpp program adds these member functions to the OrdArray class of Hour 3, which keeps its items in a vector<double> called v and their count in nElems.

// Search the whole array; return the key's index, or nElems if absent.
int find(double searchKey)
   {
   return recFind(searchKey, 0, nElems-1);
   }

// Search the cells from lowerBound through upperBound.
int recFind(double searchKey, int lowerBound, int upperBound)
   {
   // An empty range means the key isn't in the array.
   if(lowerBound > upperBound)
      return nElems;
   int curIn = (lowerBound + upperBound) / 2;
   if(v[curIn] == searchKey)
      return curIn;
   // Otherwise search only the half that could hold the key.
   if(v[curIn] < searchKey)
      return recFind(searchKey, curIn+1, upperBound);
   else
      return recFind(searchKey, lowerBound, curIn-1);
   }

The user of the class calls find() just as in Hour 3, and never needs to know that recursion is involved. find() simply starts the search with the full range, 0 to nElems − 1. The real work happens in recFind(), which only find() needs to call.

Where the Hour 3 loop changed lowerBound or upperBound and went around again, recFind() passes the new bounds to a fresh call of itself. It has two base cases, one for each way a search can end. Either the middle cell holds the key (found), or the range has become empty because lowerBound has passed upperBound (not found, reported by returning nElems). Our version checks for the empty range first, so it never looks at a cell outside the range. The book's version tests for a match first. Both give the same answers.

Suppose the array holds 0, 11, 22, 33, 44, 55, 66, 77, 88 and 99, and you search for 55. The first call looks at index 4 (44), the second at index 7 (77), and the third finds 55 at index 5.

Each call works on half the range of the call before it, so the recursion never goes deep. A 10-item array needs at most 4 cells examined, and a million-item array at most about 20, the same counts as in Hour 3. The recursive version is still O(log N). It does pay the small overhead of a function call at each step, which the loop version avoids.

Divide and Conquer

The recursive binary search is an example of the divide-and-conquer approach. You divide a big problem into smaller problems and solve each one separately. Each smaller problem is divided the same way, until you reach problems simple enough to solve directly. Binary search is an unusually easy case, because after dividing it only has to solve one of the halves, since the key can't be in both. Mergesort (Hour 12) and quicksort (Hours 13 and 14) also divide their data in two, but they have to deal with both halves, so their recursive functions call themselves twice.

Recursion Versus Stacks

You've seen that each call of triangle() has its own copy of n, and that unfinished calls wait while deeper calls do their work. The computer keeps track of all this with a stack. When a function is called, the code the compiler generates pushes the arguments and the return address, the place in the caller where execution should continue afterward, onto an internal stack. The function reads its arguments from the top of that stack. When it returns, the return address and the arguments are popped off, which uncovers the values belonging to the call that is still waiting underneath.

So recursion is a stack in disguise. The last call made is the first one to finish, which is exactly the last-in, first-out rule of Hour 6. It follows that any recursive algorithm can be rewritten to use a stack of your own in place of the recursive calls.

Simulating What the Compiler Does

The book first shows a literal simulation of what the compiler does for triangle(). It defines a small class that bundles an argument together with a return address, keeps a stack of objects of that class, and runs the whole computation as a loop around a switch statement. Each case of the switch handles one numbered step of calling or returning, and a variable that says which step comes next plays the part of the return address. The result is a mechanical imitation of calls and returns, and it produces the same answers as the recursive function.

That simulation is not easy reading, which is rather the point. It shows how much bookkeeping recursion quietly does for you. Lafore then boils the idea down to a much simpler function.

A Simpler Stack Version

int stackTriangle(int n)
   {
   // Room for far more values than we will ever push.
   StackX theStack(10000);
   // Phase 1: push the column heights, as the calls did going down.
   for(int column = n; column > 0; column--)
      theStack.push(column);
   // Phase 2: pop and add them, as the returns did coming back up.
   int answer = 0;
   while( !theStack.isEmpty() )
      answer += theStack.pop();
   return answer;
   }

The function works in two phases that mirror the two halves of the recursive trace. The first loop pushes n, n − 1, and so on down to 1, just as the recursive calls went down from triangle(5) to triangle(1), each one leaving its own n behind on the stack. The second loop pops the values and adds them up, just as the returns came back up, each adding its own n. The function uses the StackX class of Hour 6, changed to hold int values instead of doubles. The size, 10,000, only needs to be larger than any n the function will be given.

Why Use a Stack

Replacing recursion with your own stack is worthwhile for a few reasons. Sometimes the stack version is more efficient, because it avoids the overhead of real function calls and stores only what it needs, here a single number per level instead of arguments plus a return address. It can also avoid stack overflow, since your own stack can be made as big as memory allows, while the system's call stack is usually much more limited. And writing the stack version is a good way to see what recursion really does behind the scenes.

For triangular numbers, the plain loop at the start of this hour beats both versions. The stack technique matters most for algorithms that have no such simple loop, such as some of the sorting and tree algorithms in the hours ahead.

The Towers of Hanoi

The Towers of Hanoi is an ancient puzzle made of three columns and a set of disks. Every disk has a different diameter, and each has a hole through its center so it can slide down over a column. The columns are called towers A, B and C.

At the start, every disk is stacked on tower A, widest at the bottom and narrowest at the top. Your job is to move the whole stack to tower C.

Two rules make this harder than it sounds. You may move only one disk at a time, always the top disk of some tower. And you may never set a disk down on a disk smaller than itself. Tower B is there to help, and you can use it as often as you like.

Lafore passes on the legend that usually travels with the puzzle. Somewhere in India, the story goes, a remote temple holds three towers encrusted with diamonds and a pile of 64 golden disks. Monks work in shifts around the clock, shifting the pile from one tower to another under the same two rules. When the final disk comes to rest, the world will end.

You can relax. As you'll see shortly, 64 disks need 2⁶⁴ − 1 moves. Working at one move per second without a single break, the monks would need about 585 billion years.

The Towers Workshop Applet

The book's Towers Workshop applet lets you choose how many disks to play with. You can then solve the puzzle yourself by dragging disks from tower to tower. You can also press Step to see the solution one move at a time, or Run to watch the applet solve it from start to finish.

Lafore suggests working a few puzzles by hand before you let the applet show you how. Three disks take 7 moves and four take 15. On the first tries it is easy to trap yourself, with a small disk sitting on exactly the tower you need next. After a little practice a rhythm appears, and that rhythm is what the recursive solution captures.

The re-creation below behaves like the original, except that you click instead of drag. Click the tower whose top disk you want to move, then click the tower where it should go. A counter shows your moves next to the minimum, 2ⁿ − 1 for n disks.

Moving Subtrees

To describe the solution, it helps to give the piles names. Lafore calls the starting pile of disks a tree, and any smaller pile sitting on top of it a subtree. (The binary trees that begin in Hour 15 are a separate idea; here the words simply describe piles of disks.) With four disks, the top three form a subtree, the top two form a smaller subtree, and the top disk by itself is a subtree of one.

Now think about the largest disk, number 4. It can't move while anything sits on top of it. It also needs an empty tower to land on, because every other disk is smaller than it is. So at the moment disk 4 travels from A to C, tower C must be empty and the other three disks must all be stacked on tower B.

That one observation splits the puzzle into three jobs. First, move the three-disk subtree from A to B. Second, move disk 4 from A to C. Third, move the three-disk subtree from B to C, where it lands on top of disk 4.

The middle job is a single move. The first and third jobs are the original puzzle again, only with three disks and with the towers playing different parts. Each of those can be split the same way, into a two-disk job, one move, and another two-disk job. A problem that contains smaller copies of itself is exactly the kind of problem recursion handles well.

The Recursive Algorithm

To state the solution in general terms, name the towers by the part they play instead of by letter. S is the source, where the pile starts, D is the destination, where it must end up, and I is the intermediate tower, the spare. To move a pile of n disks from S to D, you follow three steps.

1. Move the subtree made of the top n − 1 disks from S to I.
2. Move the remaining disk, the largest one, from S to D.
3. Move the subtree from I to D.

The base case is a subtree of just one disk. Nothing sits on top of it, so nothing has to be cleared away, and you move it straight from S to D. Every recursive call works on a pile one disk smaller than its caller's pile, so the calls always get down to this case.

The part that takes getting used to is that the towers trade roles from one call to the next. In step 1 the subtree has to end up on I, so for that call I is the destination and D serves as the spare. In step 3 the subtree starts on I, so I is the source and S becomes the spare. Here is the complete plan for three disks, written as jobs inside jobs.

• Move 3 disks from A to C, with B as the spare:
  • Move 2 disks from A to B, with C as the spare:
    • Disk 1 from A to C
    • Disk 2 from A to B
    • Disk 1 from C to B
  • Disk 3 from A to C
  • Move 2 disks from B to C, with A as the spare:
    • Disk 1 from B to A
    • Disk 2 from B to C
    • Disk 1 from A to C

Read the innermost lines from top to bottom and you have the seven moves that solve the three-disk puzzle.

The towers.cpp Program

The C++ version follows the three steps almost word for word. The function doTowers() takes the number of disks in the pile, then the names of the three towers in the order source, intermediate, destination. Disks are numbered by size, 1 for the smallest, so a pile of topN disks always has disk topN at its bottom.

// towers.cpp
// Solves the Towers of Hanoi puzzle recursively.
#include <iostream>
using namespace std;

// Move the pile made of disks 1..topN from tower src to tower dest,
// using tower inter as a parking place along the way.
void doTowers(int topN, char src, char inter, char dest)
{
   // Base case: a pile of one disk simply moves.
   if(topN == 1)
   {
      cout << "Disk 1 from " << src << " to " << dest << endl;
      return;
   }
   // Park the smaller disks on the spare tower.
   doTowers(topN - 1, src, dest, inter);

   // The biggest disk of this pile is now free to move.
   cout << "Disk " << topN << " from " << src
        << " to " << dest << endl;

   // Bring the smaller disks back on top of it.
   doTowers(topN - 1, inter, src, dest);
}

int main()
{
   int nDisks = 3;
   doTowers(nDisks, 'A', 'B', 'C');
   return 0;
}

When topN is 1, the function prints a single move and returns. Otherwise it makes two recursive calls with one print statement between them.

Watch the order of the tower arguments. The first call passes src, dest, inter, so the spare and the destination swap places and the smaller disks go to the spare. The second call passes inter, src, dest, so the pile starts from the spare and the original source becomes the new spare.

main() calls doTowers(nDisks, 'A', 'B', 'C') with nDisks set to 3. The program prints one line per move.

Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C

These are the same seven moves as the nested plan. Each call to doTowers() prints exactly one line, so the number of calls equals the number of moves. The calls never nest deeply, though. At any moment the chain of unfinished calls holds at most one call per pile size, so even 64 disks would need only 64 levels of recursion.

Now count the moves. Write moves(n) for the number of moves needed with n disks. One disk takes one move. A larger pile needs the moves for n − 1 disks, then one move, then the moves for n − 1 disks again, so moves(n) = 2 × moves(n − 1) + 1.

Starting from moves(1) = 1, that rule gives 3, 7, 15, 31 and so on. Each result is one less than a power of 2, which means moves(n) = 2ⁿ − 1.

Every extra disk doubles the work and adds one move. Growth of this kind is called exponential, and it leaves even N² behind almost at once. Twenty disks already need more than a million moves. Sixty-four disks need so many that the monks, at one move per second, will be busy for those 585 billion years.

Mergesort

The second application of recursion is a sort, and a much faster one than those you've met so far. The bubble sort of Hour 4 and the insertion sort of Hour 5 take O(N²) time. Mergesort takes O(N log N).

For large arrays the gap is enormous. With N = 10,000, N² is 100,000,000, while N × log₂N is only about 133,000, roughly 750 times smaller. If each step took one microsecond, the simple sort would run for about 100 seconds and mergesort would be done in about 0.13 seconds.

Mergesort is also easy to understand and fairly easy to code, easier than the quicksort of Hour 13. Its one real drawback is memory, because it needs a second array, called the workspace, as large as the array being sorted. If your data only just fits in memory, mergesort is ruled out. If memory is plentiful, it is an excellent choice.

Merging Two Sorted Arrays

The heart of mergesort is a simpler job, merging two arrays that are already sorted. The result is a third array that holds all the items of both, also in sorted order.

Think of two piles of exam papers, each already sorted by student name. To combine them, you look at the top paper of each pile, move the one whose name comes first in the alphabet onto a new pile, and repeat. When one pile runs out, you move the rest of the other pile across as it is, since it is already in order. Merging arrays works exactly the same way.

The book's example merges array A, which holds 4 items, with array B, which holds 6, into array C, which has room for 10. The program keeps an index into each array. At every step it compares the front items of A and B, copies the smaller one into the next free cell of C, and advances the index of the array it copied from.

After step 8, B has nothing left, so there is nothing to compare. The last two steps simply copy the remaining items of A, which are already in order. C ends up holding 7 14 23 39 47 55 62 74 81 95. Ten items found their places with only eight comparisons.

Here is the merge as a C++ function, with a small main() that runs the example. The arrays are ordinary C++ arrays of int, and each array's size is passed in beside it.

// merge.cpp
// Merges two sorted arrays into a third, larger array.
#include <iostream>
using namespace std;

// Copy every item of the sorted arrays arrayA and arrayB into
// arrayC, which must have room for sizeA + sizeB items.
void merge(int arrayA[], int sizeA,
           int arrayB[], int sizeB,
           int arrayC[])
{
   int aDex = 0;
   int bDex = 0;
   int cDex = 0;

   // While both inputs still hold items, copy the smaller front item.
   while(aDex < sizeA && bDex < sizeB)
   {
      if(arrayA[aDex] <= arrayB[bDex])
         arrayC[cDex++] = arrayA[aDex++];
      else
         arrayC[cDex++] = arrayB[bDex++];
   }
   // One input is used up. Copy what remains of the other one.
   // (Only one of these two loops will find anything to do.)
   while(aDex < sizeA)
      arrayC[cDex++] = arrayA[aDex++];
   while(bDex < sizeB)
      arrayC[cDex++] = arrayB[bDex++];
}

int main()
{
   int arrayA[] = {23, 47, 81, 95};
   int arrayB[] = {7, 14, 39, 55, 62, 74};
   int arrayC[10];

   merge(arrayA, 4, arrayB, 6, arrayC);

   for(int j = 0; j < 10; j++)
      cout << arrayC[j] << " ";
   cout << endl;
   return 0;
}

The first while loop runs as long as both arrays still have items to offer. Each pass compares the two front items, copies the smaller one into C, and moves two indexes forward, cDex and the index of the array that supplied the item. A statement such as arrayC[cDex++] = arrayA[aDex++] does the copy and both increments at once.

When the first loop ends, one of the arrays has run dry. The next two loops copy whatever is left of the other one. Only one of them does any work, because the array that emptied first fails its loop test straight away. The program's output is the merged array.

7 14 23 39 47 55 62 74 81 95

Sorting by Merging

Merging only works on arrays that are already sorted, which at first seems to leave you where you started. Mergesort gets around this with a simple plan. Divide the array in half, sort each half, and then merge the two sorted halves into one sorted array.

Each half is sorted the same way, by mergesort itself. The half is divided into two quarters, each quarter is sorted, and the two sorted quarters are merged. The quarters in turn are split into eighths, and so on down. This is the divide-and-conquer approach you met with recursive binary search in Hour 11.

The splitting stops when a piece holds a single item. An array of one item is already sorted, so that is the base case. From there the work runs back up. Pairs of single items merge into sorted runs of 2, pairs of those runs merge into runs of 4, then 8, until one run fills the whole array.

The picture shows the work level by level, but the program does it in a different order. Each call finishes sorting its lower half before it even starts on the upper half, so the left side of the array is completely sorted before the right side is touched. For the eight items above, the seven merges happen in this order.

The array's size doesn't have to be a power of 2. When a range holds an odd number of items, its two halves differ in size by one. Twelve items split into 6 and 6, each 6 splits into 3 and 3, and each 3 splits into 2 and 1. Merging works just as well on runs of unequal length.

The mergeSort Workshop Applet

The mergeSort Workshop applet runs the algorithm on a row of bars of different heights. As it works, short sorted runs appear at the left end and grow, merging with their neighbors into longer and longer runs that spread to the right. The applet marks the range it is currently merging, and it counts comparisons and copies as it goes.

The re-creation below does the same. It marks the two runs being merged, reports each comparison and copy in a message line, and keeps both counts on screen.

C++ Code for Mergesort

The mergeSort.cpp program wraps the data in a class called DArray. The class keeps the items in a vector<double> named theVect and counts them in nElems. Besides the usual insert() and display(), it offers a public mergeSort() function, backed by two private helpers that do the real work.

// mergeSort.cpp
// Sorts an array of doubles with a recursive mergesort.
#include <iostream>
#include <vector>
using namespace std;

class DArray
{
private:
   // The data, and the number of cells actually in use.
   vector<double> theVect;
   int nElems;

   void recMergeSort(vector<double>& workSpace,
                     int lowerBound, int upperBound);
   void merge(vector<double>& workSpace,
              int lowPtr, int highPtr, int upperBound);
public:
   DArray(int max) : nElems(0)
   {
      theVect.resize(max);
   }
   void insert(double value)
   {
      theVect[nElems++] = value;
   }
   void display();
   void mergeSort();
};

// The public entry point. It creates one scratch array, the same
// size as the data, and every recursive call shares it.
void DArray::mergeSort()
{
   vector<double> workSpace(nElems);
   recMergeSort(workSpace, 0, nElems - 1);
}

void DArray::recMergeSort(vector<double>& workSpace,
                          int lowerBound, int upperBound)
{
   // Base case: a range of one item is already sorted.
   if(lowerBound >= upperBound)
      return;

   // Split the range in the middle and sort each half.
   int mid = (lowerBound + upperBound) / 2;
   recMergeSort(workSpace, lowerBound, mid);
   recMergeSort(workSpace, mid + 1, upperBound);

   // Both halves are now sorted runs, so merge them into one.
   merge(workSpace, lowerBound, mid + 1, upperBound);
}

mergeSort() is the only sorting function a user of the class calls. It creates the workspace, a vector exactly as long as the data, and hands it to recMergeSort() together with the bounds of the whole array.

recMergeSort() is the whole algorithm in a few lines. If the range holds a single item, it returns at once, since there is nothing to sort. (The test uses >= so that an empty array is handled safely too.) Otherwise it finds the middle of the range, calls itself on the lower half, calls itself on the upper half, and finally merges the two halves, which by then are both sorted.

The merging is done by a member function also named merge(), but it differs from the merge.cpp version in two ways.

// Merge the sorted run lowPtr..highPtr-1 with the sorted run
// highPtr..upperBound. The two runs sit side by side in theVect.
void DArray::merge(vector<double>& workSpace,
                   int lowPtr, int highPtr, int upperBound)
{
   // Remember where the combined range starts, where the lower run
   // ends, and how many items there are altogether.
   int start = lowPtr;
   int mid = highPtr - 1;
   int count = upperBound - start + 1;
   int w = 0;

   // Take the smaller front item until one run is used up.
   while(lowPtr <= mid && highPtr <= upperBound)
   {
      if(theVect[lowPtr] <= theVect[highPtr])
         workSpace[w++] = theVect[lowPtr++];
      else
         workSpace[w++] = theVect[highPtr++];
   }
   // Copy the leftovers of whichever run still has items.
   while(lowPtr <= mid)
      workSpace[w++] = theVect[lowPtr++];
   while(highPtr <= upperBound)
      workSpace[w++] = theVect[highPtr++];

   // Copy the merged run back into the same stretch of theVect.
   for(int k = 0; k < count; k++)
      theVect[start + k] = workSpace[k];
}

First, its two input runs are not separate arrays. They lie next to each other inside theVect. The lower run occupies cells lowPtr through mid, and the upper run occupies highPtr (which is always mid + 1) through upperBound. The pointers lowPtr and highPtr play the parts that aDex and bDex played before.

Second, the merged items go into the workspace, starting at cell 0 each time, and the final for loop copies them back over the cells the two runs came from. That round trip is the reason the workspace exists. If the merge wrote straight into theVect, it would overwrite items of the lower run before they had been merged.

main() creates a DArray, inserts twelve numbers (64, 21, 33, 70, 12, 85, 44, 3, 99, 0, 108 and 36), displays them, calls mergeSort(), and displays them again. display() is a plain loop that prints every item.

64 21 33 70 12 85 44 3 99 0 108 36
0 3 12 21 33 36 44 64 70 85 99 108

Efficiency of the Mergesort

Mergesort runs in O(N log N) time. The simplest way to see why is to count copies, and the simplest arrays to count are those whose size is a power of 2.

Look back at the eight-item picture. Below the single items there are log₂8 = 3 levels of merging, producing runs of 2, runs of 4 and the final run of 8. At each level every item takes part in exactly one merge, so each level copies all 8 items into the workspace and all 8 back again. In general there are log₂N levels, so the items are copied into the workspace N × log₂N times in all, and the same number of times back.

Comparisons take a little more thought, because their number depends on the data. Merging two runs that hold n items between them takes at most n − 1 comparisons. That worst case happens when the items of the two runs interleave, so that neither run empties until the very end.

For two runs of equal length, the best case is n/2 comparisons. It happens when every item of one run is smaller than every item of the other; that run is used up after n/2 comparisons, and the rest is copied without any.

Two patterns run through the comparison column. The minimum is exactly half of N × log₂N, since in the best case each level needs only N/2 comparisons. The maximum is N × log₂N − N + 1. There are N − 1 merges in all, and each one needs at most one comparison fewer than the number of items it handles.

The eight-item example sits right on the worst case. Its seven merges used 1 + 1 + 3 + 1 + 1 + 3 + 7 = 17 comparisons and made 48 copies, just as the table predicts, because every one of its merges interleaved its runs completely.

Now compare the simple sorts. Bubble sort on 128 items makes 128 × 127 / 2 = 8,128 comparisons, more than ten times mergesort's worst case of 769. The gap keeps widening as N grows, because N² grows far faster than N × log₂N.

Quicksort is the most popular sorting algorithm, and with good reason. In most situations it is the fastest way to sort data held in memory, running in O(N log N) time. It was invented by C.A.R. (Tony) Hoare in 1962.

The whole algorithm rests on one simpler operation, partitioning. Once partitioning makes sense, quicksort itself takes only a few more lines, so that is where this hour begins.

Partitioning

To partition data is to divide it into two groups. Every item with a key larger than some chosen value goes into one group, and every item with a smaller key goes into the other.

People partition things all the time without using the word. A company might split its personnel records into employees who live within 15 miles of the office and those who live farther away, perhaps to organize car pools. A school might divide its students into those with grade point averages above 3.5 and those below, to see who qualifies for an honors program.

The Partition Workshop Applet

The Partition Workshop applet starts with 12 bars of random heights, and it can also show 100. A horizontal line across the bars marks the pivot value. Two arrows labeled leftPtr and rightPtr start at the two ends of the row and work toward each other as you press Step or Run.

When the applet finishes, the row falls into two groups. Every bar to the left of the dividing point is shorter than the pivot line, and every bar to the right is taller.

Look closely at the result and you'll see that partitioning is a long way from sorting. Inside each group the bars are still in no particular order. For example, 96 comes before 17 on the left, and 188 comes before 111 on the right.

Partitioning isn't stable either. Swaps can carry an item a long way across the array, so two items with equal keys may end up in the opposite order from the one they started in.

Notice also where the dividing point falls. The applet picks its pivot value fairly arbitrarily, so the dividing point is rarely in the middle of the array. In this example it happens to land exactly halfway, six bars and six bars, but that is luck. A pivot value near the top of the range would put most of the bars in the left group.

The re-creation below partitions the bars the same way. It draws the pivot line and the two pointers, explains each step in a message line, and counts comparisons and swaps.

The Partition Algorithm

The algorithm uses two pointers that start at opposite ends of the array and move toward each other. They are array indexes, not C++ pointers. leftPtr moves to the right, and rightPtr moves to the left.

leftPtr keeps moving as long as it finds items smaller than the pivot, since those are already in the correct group. It stops at the first item that is larger, because that item belongs in the right-hand group. rightPtr does the mirror-image job. It moves left past items larger than the pivot and stops at the first smaller one.

When both pointers have stopped, each one is resting on an item that sits on the wrong side, so the algorithm swaps the two items. That one swap fixes both of them. The pointers then set off again, and the stop-and-swap cycle repeats until the pointers meet or cross. At that moment the partition is complete, and leftPtr marks the first item of the right-hand group.

Picture tidying a bookshelf so that the paperbacks end up on the left and the hardcovers on the right. Your left hand walks in from the left end until it touches a hardcover, and your right hand walks in from the right end until it touches a paperback. You swap those two books and keep going. When your hands meet, the shelf is divided.

Here is the complete partition of the twelve bars from the figures, one round per row.

In round 4, leftPtr moves past 17 and stops at 130 in cell 6. rightPtr moves one cell, onto 17 in cell 5, and stops there. The pointers have crossed, so the work is done. The partition is at cell 6, the first cell of the right-hand group.

One situation needs special care. If every item happens to be smaller than the pivot, leftPtr never finds a reason to stop, and it would run right off the end of the array into memory that doesn't belong to it. The mirror case, with every item larger than the pivot, sends rightPtr off the other end. So each scan also checks that its pointer is still inside the range.

C++ Code for Partitioning

The partition.cpp program keeps its data in a class called ArrayPar, built much like DArray from Hour 12. It stores the items in a vector<double> and adds two members that matter here, a swap() helper and the partitionIt() function.

// partition.cpp
// Partitions an array around a pivot value.
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

class ArrayPar
{
private:
   vector<double> theVect;
   int nElems;
public:
   ArrayPar(int max) : nElems(0) { theVect.resize(max); }
   void insert(double value) { theVect[nElems++] = value; }
   int size() { return nElems; }
   void display();
   int partitionIt(int left, int right, double pivot);

   // Exchange the items in two cells.
   void swap(int dex1, int dex2)
   {
      double temp = theVect[dex1];
      theVect[dex1] = theVect[dex2];
      theVect[dex2] = temp;
   }
};

// Rearrange cells left..right so that items smaller than the pivot
// come first. Returns the index where the larger items begin.
int ArrayPar::partitionIt(int left, int right, double pivot)
{
   // Each pointer starts one step outside the range, because it
   // always moves before it looks at an item.
   int leftPtr = left - 1;
   int rightPtr = right + 1;

   while(true)
   {
      // Step right past small items. Stop at an item that belongs
      // in the right-hand group, or when the range runs out.
      do
         ++leftPtr;
      while(leftPtr <= right && theVect[leftPtr] < pivot);

      // Step left past large items. Stop at an item that belongs
      // in the left-hand group, or when the range runs out.
      do
         --rightPtr;
      while(rightPtr >= left && theVect[rightPtr] > pivot);

      // Once the pointers meet or cross, every item is in its group.
      if(leftPtr >= rightPtr)
         break;

      // Both items are on the wrong side, so they trade places.
      swap(leftPtr, rightPtr);
   }
   return leftPtr;
}

partitionIt() takes the bounds of the range to partition and the pivot value, and it returns the index where the right-hand group begins. The outer while(true) loop repeats the stop-and-swap cycle. Inside it, the first do loop moves leftPtr and the second moves rightPtr. Once both have stopped, the if checks whether they have met or crossed; if they have, break ends the loop, and if not, the two items are swapped and the cycle starts again.

This code is more delicate than it looks. Each pointer steps first and looks second, so the pointers start one cell outside the range, at left - 1 and right + 1, and their first steps land on the two end cells. Stepping first also guarantees progress. After a swap, the two items under the pointers are on their correct sides, and the next round moves past them instead of examining them again.

The loop conditions also settle what happens to items equal to the pivot. Neither scan moves past one, so an equal item stops both pointers and gets swapped. That looks like wasted effort, yet it pays off when many keys are the same.

With an array of ten identical keys, the pointers meet in the middle after five swaps and split the array into two equal halves. If the scans skipped equal keys instead, leftPtr would run all the way to the end and the split would be as lopsided as possible.

main() fills an ArrayPar with 16 random numbers between 0 and 199 and displays them. It then partitions the whole array around the pivot value 99, reports where the partition fell, and displays the array again. Because the data is random, the partition index changes from run to run. Here is one run.

41 67 134 100 169 124 78 158 162 64 105 145 81 27 161 91
Pivot is 99, Partition is at index 7
41 67 91 27 81 64 78 158 162 124 105 145 169 100 161 134

Seven of the sixteen numbers were below 99, so they fill cells 0 through 6, and the larger group starts at index 7. Within each group the numbers are still jumbled.

Efficiency of the Partition Algorithm

Partitioning runs in O(N) time. The two pointers start at opposite ends and move toward each other one cell at a time, and they stop when they meet. Between them they cover the array once, so the work grows in step with N.

Comparisons are easy to count. Every item is compared with the pivot, and where the pointers cross, a cell or two gets compared twice. That makes about N + 2 comparisons. In the twelve-bar example, leftPtr made 7 comparisons and rightPtr made 7, for 14 in all.

Swaps depend on how the data is arranged, and there are always fewer swaps than comparisons. The worst arrangement is inverse order, where every item in the left half belongs on the right and every item in the right half belongs on the left. Then every pair is swapped, which comes to N/2 swaps.

Random data needs fewer. With a pivot near the middle value, only about half the items in each half are on the wrong side, so there are roughly N/4 swaps. The twelve-bar example needed just 3.

Basic Quicksort

A partition leaves an array divided into two groups, each still unsorted. Quicksort finishes the job with recursion.

The Quicksort Algorithm

The basic quicksort has three steps.

1. Partition the array or subarray into a left group with smaller keys and a right group with larger keys.
2. Call itself to sort the left group.
3. Call itself to sort the right group.

The base case is a subarray with one item, or none. Such a subarray is already sorted, so the function returns without doing anything.

Those three steps are enough because, after a partition, every key in the left group is smaller than every key in the right group. No item will ever need to cross from one group to the other, so each group can be sorted on its own. When both groups are sorted, the whole array is sorted, with no merging needed at the end.

Compare this with mergesort. Mergesort splits the array without looking at the data and does its real work afterward, when it merges. Quicksort does its real work first, when it partitions, and has nothing left to do once its recursive calls return.

Choosing a Pivot Value

Quicksort still needs a rule for choosing the pivot value. Lafore's answer is to use the key of an actual item in the subarray as the pivot value. That item is called the pivot. It can be chosen more or less at random, and the simplest choice is the rightmost item of the subarray.

While the partition runs, the pivot stays put at the right end. partitionIt() divides the other items, the ones from left to right - 1, into the usual two groups.

When the partition finishes, the pivot is still at the far right, beyond the larger group, though it belongs between the two groups. One way to get it there would be to shift the whole right-hand group one cell to the right, opening a gap, but that could mean moving nearly N items.

A single swap does the job instead. Exchange the pivot with the item at leftPtr, the leftmost item of the right-hand group. That item moves to the far right end, which is still part of the right-hand group. The right-hand group was in no particular order anyway, so nothing is lost.

After that swap, the pivot has every smaller key to its left and every larger key to its right. It is therefore in its final sorted position, and it will never move again. The recursive calls leave it out and sort only the ranges on either side of it.

The rightmost pivot has one more benefit. It sits at the end of the range that leftPtr scans toward, and leftPtr stops at any item that isn't smaller than the pivot, including the pivot itself. So leftPtr can never run past the pivot, and the range test on that scan can be dropped. A value placed at the end of a range to stop a scan like this is called a sentinel.

C++ Code for Quicksort

The quickSort1.cpp program uses a class named ArrayIns, which stores its data the same way as ArrayPar. Its public quickSort() function calls recQuickSort(0, nElems - 1) to sort the whole array. These are the two functions that do the work.

void ArrayIns::recQuickSort(int left, int right)
{
   // Base case: a range of one item (or none) is already sorted.
   if(right - left <= 0)
      return;

   // Use the rightmost item as the pivot and split the range.
   double pivot = theVect[right];
   int partition = partitionIt(left, right, pivot);

   // The pivot is now in its final place. Sort each side of it.
   recQuickSort(left, partition - 1);
   recQuickSort(partition + 1, right);
}

int ArrayIns::partitionIt(int left, int right, double pivot)
{
   // The pivot waits in cell right, so the scan covers left..right-1.
   int leftPtr = left - 1;
   int rightPtr = right;

   while(true)
   {
      // No range test is needed here. At the latest, leftPtr stops at
      // the pivot itself, because the pivot is not smaller than itself.
      do
         ++leftPtr;
      while(theVect[leftPtr] < pivot);

      // rightPtr has no such stopper, so it checks the range.
      do
         --rightPtr;
      while(rightPtr > left && theVect[rightPtr] > pivot);

      if(leftPtr >= rightPtr)
         break;
      swap(leftPtr, rightPtr);
   }
   // Put the pivot between the two groups, where it belongs for good.
   swap(leftPtr, right);
   return leftPtr;
}

recQuickSort() first checks the size of its range. If right - left is zero or less, the range holds one item or none, and the function returns. Otherwise it takes the rightmost item as the pivot, partitions the range, and calls itself twice, once for each side of the pivot's new home.

This partitionIt() is the one from partition.cpp with three changes. rightPtr starts at right instead of right + 1, so its first step lands on right - 1 and the pivot is never examined. The leftPtr scan has no range test, because the pivot is its sentinel. And after the loop, one more swap() moves the pivot from cell right to cell leftPtr, whose index the function returns.

Here is how the program sorts the twelve bars from the figure. The first call partitions cells 0 to 11 around 55, which lands in cell 6. The call for the left side partitions cells 0 to 5 around 27, which lands in cell 3, and then cells 0 to 2 are partitioned around 12. Only when everything left of cell 6 is sorted does the program turn to cells 7 to 11.

Seven partitions sort the twelve items. The other calls all get a range of one item or none, and they return at once. main() fills the array with 16 random numbers from 0 to 99, displays them, sorts them, and displays them again. One run produced this output.

41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91
0 5 24 27 34 41 45 58 61 62 64 67 69 78 81 91

The quickSort1 Workshop Applet

The quickSort1 Workshop applet runs this algorithm on the bars. With 100 bars, pressing Run gives the big picture. The array is divided into ranges, and the ranges are divided again, into smaller and smaller pieces, until everything is in order.

With 12 bars, pressing Step shows every detail of each partition. The applet marks the range being worked on, highlights the pivot (the rightmost bar of the range), and draws the pivot line across the bars. You watch leftPtr and rightPtr stop and swap, and at the end you see the pivot swapped into its final place between the two groups. The re-creation below shows the same things, with a message for every step.

A First Look at Efficiency

Quicksort runs in O(N log N) time on average, and the call tree above shows why. The ranges on each level of the tree are separate, and together they cover nearly the whole array. A partition is O(N), so each level costs about N steps. The number of levels depends on the pivots.

If the pivots split their ranges roughly in half, the ranges shrink from N items to N/2, then N/4, N/8 and so on, and they reach single items after about log₂N levels. About N steps on each of about log₂N levels gives N × log₂N in all. The twelve items above needed three levels of partitioning, close to log₂12, which is about 3.6.

That reasoning assumes the pivots behave. The rightmost item works well for random data, but some arrangements of data make it a terrible choice, and quicksort then slows to a crawl. Hour 14 shows what goes wrong and how to fix it.

Problems with Inversely Sorted Data

If you tried the last step of the quickSort1 exercise in Hour 13, you have already seen the problem. Given inversely sorted bars, the applet grinds through the sort far more slowly than it does with random ones. Data that is already sorted the normal way is just as bad.

The trouble lies in the pivot. A partition works best when the pivot value is the median of the items, the value with half the items above it and half below, because then the range splits into two equal halves. The further the pivot is from the median, the more lopsided the split. With inversely sorted data, the rightmost item is as far from the median as it can possibly be, since it is the smallest item in the range.

A pivot like that divides almost nothing. The left group is empty, the pivot takes one cell, and the other N − 1 items all end up in the right group. Picture splitting a class into students shorter and taller than a chosen classmate, and always choosing the shortest one. Everybody else lands in the taller group, and you have made almost no progress.

The next partition runs into the same trouble. With inversely sorted data, the swap that puts each pivot in place moves the largest item to the right end, so the pivots alternate between the smallest and the largest item left in the range. Either way, one group comes out empty every time. With data that is already sorted, the rightmost item is always the largest, and the result is the same.

Instead of about log₂N levels of recursion there are now N levels, and each level partitions just one item fewer than the level above it. The comparisons add up to about N + (N − 1) + (N − 2) + … + 1, which is roughly N²/2. The twelve inversely sorted bars in the first figure cost 76 comparisons, a little more than 12²/2 = 72. Quicksort has turned into an O(N²) sort, no better than the bubble sort of Hour 4.

There is a second danger. Every recursive call occupies space on the machine's call stack until it returns. With N levels of recursion, a large array can use up all of that space, and the program then crashes with a stack overflow instead of merely running slowly.

Median-of-Three Partitioning

People have proposed many ways to choose a better pivot. The ideal would be the true median of the subarray, since it always splits the range in half. Finding the true median, though, means examining every item, which takes longer than the sort can afford at every step.

The usual compromise is to look at just three items, the first, the middle and the last, and use the median of those three as the pivot. This is called median-of-three partitioning. Putting three items in order takes at most three comparisons, so choosing the pivot stays quick.

For sorted and inversely sorted data, the middle item is the true median of the range, so median-of-three picks an ideal pivot and the partitions stay well balanced. For random data, the median of three items is unlikely to be the smallest or largest item in the range. The worst case is still possible in principle, but it takes an unusual arrangement of data to trigger it.

Take the sorted numbers 10, 20, 30 and so on up to 90. The first, middle and last items are 10, 50 and 90, and their median, 50, is also the median of all nine numbers. The range splits into four items on each side of the pivot, as evenly as it possibly can.

Sorting the three sample items brings two bonuses. The first is speed in the inner loops. After the sort, the left item is no larger than the pivot, and the pivot itself sits just inside the right end.

The left item therefore stops rightPtr, and the pivot stops leftPtr. Both act as sentinels, so neither scan needs a range test. The inner loops run for every item on every level of recursion, so removing a test from them pays off.

The second bonus is less work. The left and right items are already on their correct sides, so the partition can skip them. The median is parked in cell right - 1, out of the way, and the partition deals only with cells left + 1 through right - 2. When the pointers cross, the pivot is swapped from right - 1 into its final place, just as before.

In the example, the partition covers cells 1 through 6 with the pivot 53. In the first round, leftPtr stops at 66 in cell 2 and rightPtr stops at 49 in cell 6, and the two are swapped. In the second round, leftPtr stops at 81 in cell 5 and rightPtr at 28 in cell 4, so the pointers have crossed. Swapping the pivot into cell 5 gives 17 35 49 12 28 53 66 81 92, with 53 in its sorted position.

C++ Code for Median-of-Three

The quickSort2.cpp program keeps the ArrayIns class of quickSort1.cpp and rewrites its private functions. recQuickSort() now gets its pivot from medianOf3(), and it passes small ranges to a new function, manualSort().

void ArrayIns::recQuickSort(int left, int right)
{
   int size = right - left + 1;

   // Median-of-three needs at least four items to work with.
   if(size <= 3)
   {
      manualSort(left, right);
      return;
   }
   double median = medianOf3(left, right);
   int partition = partitionIt(left, right, median);
   recQuickSort(left, partition - 1);
   recQuickSort(partition + 1, right);
}

double ArrayIns::medianOf3(int left, int right)
{
   int center = (left + right) / 2;

   // Put the three sample items in order, so that
   // theVect[left] <= theVect[center] <= theVect[right].
   if(theVect[left] > theVect[center])
      swap(left, center);
   if(theVect[left] > theVect[right])
      swap(left, right);
   if(theVect[center] > theVect[right])
      swap(center, right);

   // Park the median next to the right end and hand back its value.
   swap(center, right - 1);
   return theVect[right - 1];
}

recQuickSort() starts by measuring its range, because the median-of-three method needs at least four items. With three, ordering the left, center and right items already sorts the whole range and leaves nothing to partition, and with two, the three sample positions overlap and the sentinels are lost. So a range of three or fewer items goes to manualSort(), which sorts it directly. Larger ranges get a median-of-three pivot, a partition and two recursive calls, as before.

medianOf3() finds the middle of the range and then makes three compare-and-swap steps. The first two leave the smallest of the three items in the left cell, and the third puts the center and right cells in order. The function then swaps the median into cell right - 1 and returns its value, which becomes the pivot.

Traced on the example from the figures, the left, center and right items start as 92, 17 and 53. The first step swaps 92 and 17, the second finds 17 and 53 already in order, and the third swaps 92 and 53, leaving 17, 53 and 92. The last swap moves 53 from cell 4 into cell 7 and sends the 28 that was there back to cell 4.

int ArrayIns::partitionIt(int left, int right, double pivot)
{
   // Cells left and right are already on the correct sides, and the
   // pivot waits in cell right-1. Only left+1..right-2 is scanned.
   int leftPtr = left;
   int rightPtr = right - 1;

   while(true)
   {
      // No range tests: the pivot in cell right-1 stops leftPtr, and
      // the small item in cell left stops rightPtr.
      do
         ++leftPtr;
      while(theVect[leftPtr] < pivot);
      do
         --rightPtr;
      while(theVect[rightPtr] > pivot);

      if(leftPtr >= rightPtr)
         break;
      swap(leftPtr, rightPtr);
   }
   // Move the pivot from right-1 to the boundary between the groups.
   swap(leftPtr, right - 1);
   return leftPtr;
}

void ArrayIns::manualSort(int left, int right)
{
   int size = right - left + 1;

   // One item (or none) needs no work.
   if(size <= 1)
      return;

   // Two items: one comparison, and perhaps one swap.
   if(size == 2)
   {
      if(theVect[left] > theVect[right])
         swap(left, right);
      return;
   }

   // Three items: order the first two, then pull the smallest of all
   // three to the front, then order the last two.
   int middle = left + 1;
   if(theVect[left] > theVect[middle])
      swap(left, middle);
   if(theVect[left] > theVect[right])
      swap(left, right);
   if(theVect[middle] > theVect[right])
      swap(middle, right);
}

This partitionIt() is shorter than the one in quickSort1.cpp. leftPtr starts at left, so its first step lands on left + 1. rightPtr starts at right - 1, the pivot's cell, so its first step lands on right - 2. Neither scan tests the range, because the sentinels guarantee that both will stop, and the final swap uses right - 1, where the pivot was parked.

manualSort() treats the three small sizes separately. One item needs no work. Two items need one comparison and perhaps a swap. Three items need the same three compare-and-swap steps that medianOf3() uses, which is enough to put any three items in order.

main() is the same as in quickSort1.cpp. It fills the array with 16 random numbers, displays them, sorts them and displays them again. Here is one run.

48 96 94 91 31 77 2 3 17 68 9 33 23 52 78 99
2 3 9 17 23 31 33 48 52 68 77 78 91 94 96 99

The quickSort2 Workshop Applet

The quickSort2 Workshop applet uses median-of-three partitioning, and like manualSort() it sorts ranges of three or fewer items directly. Its display looks like the quickSort1 applet's. The lesson comes from running the two applets on the same kind of data.

Give quickSort2 inversely sorted bars and it stays fast. Each median-of-three pivot splits its range near the middle, the ranges shrink quickly, and the sort finishes in a small fraction of the steps quickSort1 needs. With random data, the two applets perform much more alike.

The re-creation below puts both algorithms in one applet, so you can compare them side by side. It starts with inversely sorted bars.

Handling Small Partitions

Median-of-three already forced one special case, manualSort() for ranges of three items or fewer. The same idea can be pushed further. Quicksort is built for big arrays, and on a tiny subarray its machinery costs more than it saves. Every little range still pays for a function call, a median-of-three and a partition, while a simple sort could put a handful of items in order with far less fuss.

The waste adds up because the recursion is widest at the bottom. Each level holds about twice as many ranges as the level above it, so most of quicksort's calls are made on ranges of just a few items.

The insertion sort of Hour 5 is the natural helper. It is O(N²), but for a few items that hardly matters, and its overhead is tiny. There are two ways to combine it with quicksort.

Using an Insertion Sort for Small Partitions

The first way sets a cutoff. Any subarray smaller than the cutoff is sorted with an insertion sort instead of being partitioned any further. Lafore's quickSort3.cpp uses a cutoff of 10, and Donald Knuth recommends a cutoff of about 9. The best value depends on your computer, your compiler and your data, so it pays to experiment.

void ArrayIns::recQuickSort(int left, int right)
{
   int size = right - left + 1;

   // Below the cutoff, an insertion sort is cheaper than partitioning.
   if(size < 10)
      insertionSort(left, right);
   else
   {
      double median = medianOf3(left, right);
      int partition = partitionIt(left, right, median);
      recQuickSort(left, partition - 1);
      recQuickSort(partition + 1, right);
   }
}

// An insertion sort that works only on the cells left..right.
void ArrayIns::insertionSort(int left, int right)
{
   for(int out = left + 1; out <= right; out++)
   {
      // Lift out the next item, leaving a gap behind it.
      double temp = theVect[out];
      int in = out;

      // Shift larger items one cell to the right until the gap
      // reaches the place where temp belongs.
      while(in > left && theVect[in - 1] > temp)
      {
         theVect[in] = theVect[in - 1];
         --in;
      }
      theVect[in] = temp;
   }
}

The new recQuickSort() looks like the quickSort2 version, except that it compares the size with the cutoff. Every range that reaches medianOf3() now holds at least ten items, so manualSort() is no longer needed.

insertionSort() is the insertion sort from Hour 5, adapted to work on the cells from left to right instead of the whole array. The outer loop takes each item in turn and holds it in temp. The inner loop shifts larger items one cell to the right until it finds the gap where temp belongs, stopping at left at the latest.

Insertion Sort Following Quicksort

The second way turns the idea around. Quicksort ignores every subarray smaller than the cutoff and leaves it unsorted. When the recursion is finished, the array is made of small blocks. Each block holds exactly the items that belong in it, in the right place relative to the other blocks, only jumbled among themselves.

A single insertion sort over the whole array then finishes the job. As Hour 5 showed, insertion sort is very fast on almost-sorted data, because no item has far to travel. Here no item sits more than a block's length from its final cell, so this last pass takes roughly linear time.

void ArrayIns::quickSort()
{
   recQuickSort(0, nElems - 1);

   // One pass puts the items inside every small block in order.
   insertionSort(0, nElems - 1);
}

void ArrayIns::recQuickSort(int left, int right)
{
   // Leave small ranges unsorted for the final insertion sort.
   if(right - left + 1 < 10)
      return;

   double median = medianOf3(left, right);
   int partition = partitionIt(left, right, median);
   recQuickSort(left, partition - 1);
   recQuickSort(partition + 1, right);
}

Both approaches give a modest speedup, and neither one changes quicksort's Big O. The size of the gain depends on the system, anywhere from a few percent to a few tens of percent.

Efficiency of Quicksort

Quicksort runs in O(N log N) time on average. Its worst case is O(N²), but with median-of-three pivots that case becomes rare.

The reason for N log N is the one sketched in Hour 13. The ranges on each level of recursion are separate and together hold about N items, and partitioning is linear, so each level costs about N steps. When the pivots split ranges near the middle, the ranges halve from one level to the next. There is one range of N items, then two of N/2, then four of N/4, and so on, down to ranges of a single item after about log₂N levels.

About N steps on each of about log₂N levels gives N × log₂N steps. For a million items log₂N is about 20, so quicksort needs something like 20 million steps, where an O(N²) sort would need about a trillion.

Quicksort and the Other Sorts

Mergesort is also O(N log N), yet quicksort usually beats it in practice, for two reasons. First, quicksort sorts in place. It needs no workspace array and none of the copying into and out of one. Second, its inner loops are extremely tight, since each step of a scan is little more than one comparison and one increment.

Mergesort keeps one advantage of its own. Its running time is guaranteed, because it never degrades to O(N²) whatever the data, while quicksort's speed depends on getting reasonable pivots.

Hour 24 returns to these trade-offs when it sums up which structures and algorithms to use when.

Why Use Binary Trees?

Every structure so far has forced a trade. The ordered array of Hour 3 searches fast, because binary search needs only about log₂N comparisons. Inserting is slow, since every larger item must shift one cell to the right to make room, and deleting shifts them back. On average half the array moves, so both operations are O(N).

The linked list of Hours 8 to 10 has the opposite strengths. Once you are at the right spot, inserting or deleting a link means changing a pointer or two. Getting to the spot is the problem, because you can't jump into the middle of a list the way binary search jumps into an array. You walk from pFirst one link at a time, visiting half the list on average, so finding is O(N) even in a sorted list.

A tree combines the good halves of both. In a binary search tree that stays reasonably balanced, finding, inserting and deleting all take O(log N) time. For a million items that is about 20 steps per operation, where the array or the list needed hundreds of thousands. This hour and the next cover ordinary binary search trees, and Hours 17 to 20 show how to keep a tree balanced.

What Is a Tree?

A tree is a set of nodes connected by edges. The nodes usually stand for entities such as employees, car parts or airline reservations, and the edges show how those entities are related. In a C++ program an edge is a pointer. The program travels from node to node by following pointers, normally only downward, since a node keeps no pointer back up to its parent.

Computer trees are drawn upside down, with the root at the top and the leaves at the bottom, more like an organization chart than an oak. In a general tree, called a multiway tree, a node may have many children; you'll build one in Hours 19 and 20. In a binary tree each node has at most two. This hour is about one important kind of binary tree, the binary search tree.

Tree Terminology

Trees have a vocabulary of their own, and you'll meet these words for the rest of the book. The figure marks several of them.

• Path. The sequence of nodes you pass through when you walk along edges from one node to another. The path from 50 to 30 runs through 25 and 37.
• Root. The node at the top. A tree has exactly one, and exactly one path leads from it to any other node. If two routes led to the same node, the structure wouldn't be a tree.
• Parent. Every node except the root has one edge running up to another node, its parent. 37 is the parent of 30 and 43.
• Child. The nodes joined to a node from below. 30 and 43 are the children of 37.
• Leaf. A node with no children, such as 12, 30, 43, 62 and 93.
• Subtree. Any node can be seen as the root of a smaller tree made of its children, their children, and so on down. The subtree rooted at 75 holds 75, 62, 87 and 93.
• Visiting. Arriving at a node in order to do something with it, such as checking or displaying its key. Passing through a node on the way somewhere else doesn't count.
• Traversing. Visiting every node in some fixed order, such as ascending order of keys. Hour 16 covers it.
• Levels. How many generations a node is from the root. The root is on level 0, its children on level 1, their children on level 2, and so on.
• Keys. The data field used for searching. The number drawn inside each circle is that node's key.
• Binary tree. A tree in which every node has at most two children, called the left child and the right child. A node may have two children, one, or none.

A binary search tree adds one rule. A node's left child has a smaller key than the node, and its right child has a key greater than or equal to it. The rule holds for whole subtrees, so every key to the left of 50 is below 50 and every key to its right is 50 or more. That arrangement is what makes fast searching possible.

A Tree Analogy in Your Computer

You already use a tree every day. The directories on a disk form a hierarchy, with the root directory (such as C:\) at the top, subdirectories below it, and files at the ends of the branches. A full file name such as C:\SALES\EAST\NOVEMBER\SMITH.DAT is literally a path from the root down to one leaf. File systems borrowed the words root and path from tree theory.

Two differences stand out. A directory can hold any number of entries, so the file system is a multiway tree rather than a binary one. And directories only organize things, while the data itself lives in the files at the leaves. In a binary search tree every node, the root included, holds data.

Unbalanced Trees

A tree's shape depends on the order in which its keys arrive. Keys in random order tend to build a bushy tree, with about as many nodes on each side of every node. Keys in sorted or nearly sorted order go to the same side one after another, and the tree grows lopsided.

In the figure, nearly every key after 20 is larger than the ones before it. Finding 70 takes five steps, although seven nodes fit into a tree of three levels. Keys in exactly sorted order make a straight line, no faster to search than a linked list. Hour 17 starts from that worst case, and until then the speeds claimed for trees assume a reasonably balanced shape.

Basic Binary Tree Operations

The everyday jobs are finding the node with a given key, inserting a node, and deleting one. Traversing, which visits every node in order, is the topic of Hour 16. It helps to watch the operations before reading the code.

The Tree Workshop Applet

The book's Tree Workshop applet draws a binary search tree of up to five levels, which hold at most 1 + 2 + 4 + 8 + 16 = 31 nodes. Fill builds a tree with however many random nodes you ask for. Find sends a red arrow from the root down the path toward the key you typed. Ins makes the same trip and adds a node where the path runs out, Trav steps through an inorder traversal, and Del deletes a node.

Watch the arrow during a find. It visits at most one node per level, so no search in the applet takes more than five steps. With Ins, notice that the new node always appears at the bottom of a branch. Random fills also tend to leave a few branches deeper than the rest, a mild case of imbalance.

Representing the Tree in C++ Code

In C++ a tree is built from two classes. A Node holds one node's data plus a pointer to each child, and a Tree holds a pointer to the root and provides the operations.

#include <iostream>
using namespace std;

class Node
   {
   public:
      // the search key, plus one more piece of data
      int iData;
      double dData;
      // links to the children; NULL means "no child on this side"
      Node* pLeftChild;
      Node* pRightChild;

      // a new node always starts life as a leaf
      Node(int id, double dd) : iData(id), dData(dd),
                                pLeftChild(NULL), pRightChild(NULL)
         { }

      // print the node's contents, for example {43, 43.5}
      void displayNode()
         {
         cout << "{" << iData << ", " << dData << "} ";
         }
   };

class Tree
   {
   private:
      // the only node the Tree object holds directly
      Node* pRoot;
      // a helper for remove(), shown later in this hour
      Node* getSuccessor(Node* pDelNode);
   public:
      Tree() : pRoot(NULL)
         { }
      Node* find(int key);
      void insert(int id, double dd);
      bool remove(int key);
      void traverse(int traverseType);
      void displayTree();
   };

iData is the key, and dData stands in for the rest of the record, which in a real program might be a name, an address and a salary. A NULL child pointer means that child doesn't exist. The constructor sets both pointers to NULL, so every new node starts out as a leaf. The book's Node has a constructor with no arguments and fills in the data afterward; passing the data in, as here, shortens the insertion code.

The Tree class stores only pRoot. Every node can be reached by following child pointers down from the root, and an empty tree simply has a NULL root. This hour covers find(), insert() and the ideas behind remove(); Hour 16 adds traversal and display.

Finding a Node

To find a key, start at the root and compare. If the key you want is smaller than the current node's key, move to the left child. If it is larger, move to the right child, and if the two are equal, you've found it. If the child you need is missing, the key isn't in the tree, since that empty spot is the only place it could have been.

A search for 50 in the same tree would take the same route as far as 57. There it would need 57's left child, find it missing, and report that 50 isn't in the tree. Here is the function.

Node* Tree::find(int key)
   {
   // begin at the top of the tree
   Node* pCurrent = pRoot;
   // go down one level per pass until we hit the key or run out of tree
   while(pCurrent != NULL && pCurrent->iData != key)
      {
      // smaller keys live on the left, larger or equal ones on the right
      if(key < pCurrent->iData)
         pCurrent = pCurrent->pLeftChild;
      else
         pCurrent = pCurrent->pRightChild;
      }
   // the matching node, or NULL if the key is not in the tree
   return pCurrent;
   }

pCurrent moves down one level per pass. The loop ends when it reaches a matching node or becomes NULL, and either way the function returns it. The book's version assumes the tree isn't empty and tests for NULL after each move; testing at the top of the loop, as here, also handles an empty tree. The caller gets a pointer, so it can display or change the node, as in if(pFound != NULL) pFound->displayNode();.

The search visits at most one node per level, and a balanced tree of N nodes has about log₂N levels, so finding is O(log N). The applet's 31-node tree never needs more than 5 comparisons, and a balanced million-node tree needs about 20. That is the same growth rate as binary search in an ordered array.

Inserting a Node

To insert a node, first find where it belongs by searching for the new key as if it were already there. The search ends by trying to move to a missing child, and that empty spot is where the new node goes, as a child of the last node visited.