Informally, an * algorithm* is any well-defined computational procedure that takes some value, or set of values, as

We can also view an algorithm as a tool for solving a well-specified * computational problem*. The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes a specific computational procedure for achieving that input/output relationship.

**Input:** A sequence of *n* numbers *a*_{1}*, a*_{2}*, . . . , a _{n}*

**Output:*** *A permutation (reordering) of the input sequence such that .

Given an input sequence such as 31, 41, 59, 26, 41, 58, a sorting algorithm returns as output the sequence 26, 31, 41, 41, 58, 59. Such an input sequence is called an * instance* of the sorting problem. In general, an

An algorithm is said to be* correct* if, for every input instance, it halts with the correct output. We say that a correct algorithm

An algorithm can be specified in English, as a computer program, or even as a hardware design. The only requirement is that the specification must provide a precise description of the computational procedure to be followed.

In this book, we shall typically describe algorithms as programs written in a * pseudocode* that is very much like C, Pascal, or Algol. If you have been introduced to any of these languages, you should have little trouble reading our algorithms. What separates pseudocode from "real" code is that in pseudocode, we employ whatever expressive method is most clear and concise to specify a given algorithm. Sometimes, the clearest method is English, so do not be surprised if you come across an English phrase or sentence embedded within a section of "real" code. Another difference between pseudocode and real code is that pseudocode is not typically concerned with issues of software engineering. Issues of data abstraction, modularity, and error handling are often ignored in order to convey the essence of the algorithm more concisely.

We start with * insertion sort*, which is an efficient algorithm for sorting a small number of elements. Insertion sort works the way many people sort a bridge or gin rummy hand. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left, as illustrated in Figure 1.1.

Our pseudocode for insertion sort is presented as a procedure called INSERTION-SORT, which takes as a parameter an array *A*[1 . . *n*] containing a sequence of length *n* that is to be sorted. (In the code, the number *n *of elements in *A* is denoted by *length*[*A*].) The input numbers are * sorted in place*: the numbers are rearranged within the array

INSERTION-SORT (A)

1forj2tolength[A]

2dokeyA[j]

3 InsertA[j] into the sorted sequenceA[1 . .j- 1].

4ij- 1

5whilei >0 andA[i]>key

6doA[i+ 1]A[i]

7ii- 1

8A[i+ 1]key

We use the following conventions in our pseudocode.

1. Indentation indicates block structure. For example, the body of the **for** loop that begins on line 1 consists of lines 2-8, and the body of the **while** loop that begins on line 5 contains lines 6-7 but not line 8. Our indentation style applies to **if-then-else** statements as well. Using indentation instead of conventional indicators of block structure, such as **begin** and **end** statements, greatly reduces clutter while preserving, or even enhancing, clarity.^{1}

2. The looping constructs **while, for**, and **repeat** and the conditional constructs **if**, **then**, and **else** have the the same interpretation as in Pascal.

3. The symbol indicates that the remainder of the line is a comment.

4. A multiple assignment of the form *i ** j ** e* assigns to both variables *i *and* j* the value of expression *e*; it should be treated as equivalent to the assignment *j ** e* followed by the assignment *i ** j*.

5. Variables (such as *i, j*, and *key*) are local to the given procedure. We shall not use global variables without explicit indication.

6. Array elements are accessed by specifying the array name followed by the index in square brackets. For example, *A*[*i*] indicates the *i*th element of the array* A*. The notation ". ." is used to indicate a range of values within an array. Thus, *A*[1*. . j*] indicates the subarray of *A* consisting of elements *A*[1], *A*[2], . . . , *A*[*j*].

7. Compound data are typically organized into * objects*, which are comprised of

A variable representing an array or object is treated as a pointer to the data representing the array or object. For all fields *f* of an object *x*, setting *y ** x* causes *f*[*y*]* = f*[*x*]. Moreover, if we now set *f*[*x*] 3, then afterward not only is *f*[*x*] = 3, but *f*[*y*] = 3 as well. In other words, *x* and *y* point to ("are") the same object after the assignment *y * x*.*

Sometimes, a pointer will refer to no object at all. In this case, we give it the special value NIL.

8. Parameters are passed to a procedure * by value*: the called procedure receives its own copy of the parameters, and if it assigns a value to a parameter, the change is

Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of nondecreasing order.

Consider the **searching problem:**

**Input:** A sequence of *n* numbers *A* = *a*_{1}, *a*_{2}, . . . ,*a*_{n} and a value *v*.

**Output:** An index *i* such that *v = A*[*i*] or the special value NIL if *v* does not appear in *A*.

Write pseudocode for * linear search*, which scans through the sequence, looking for

Consider the problem of adding two *n*-bit binary integers, stored in two *n*-element arrays *A* and *B*. The sum of the two integers should be stored in binary form in an (*n* + 1)-element array *C*. State the problem formally and write pseudocode for adding the two integers.

* Analyzing* an algorithm has come to mean predicting the resources that the algorithm requires. Occasionally, resources such as memory, communication bandwidth, or logic gates are of primary concern, but most often it is computational time that we want to measure. Generally, by analyzing several candidate algorithms for a problem, a most efficient one can be easily identified. Such analysis may indicate more than one viable candidate, but several inferior algorithms are usually discarded in the process.

Before we can analyze an algorithm, we must have a model of the implementation technology that will be used, including a model for the resources of that technology and their costs. For most of this book, we shall assume a generic one-processor,* random-access machine*

The time taken by the INSERTION-SORT procedure depends on the input: sorting a thousand numbers takes longer than sorting three numbers. Moreover, INSERTION-SORT can take different amounts of time to sort two input sequences of the same size depending on how nearly sorted they already are. In general, the time taken by an algorithm grows with the size of the input, so it is traditional to describe the running time of a program as a function of the size of its input. To do so, we need to define the terms "running time" and "size of input" more carefully.

The best notion for * input size* depends on the problem being studied. For many problems, such as sorting or computing discrete Fourier transforms, the most natural measure is the

The * running time* of an algorithm on a particular input is the number of primitive operations or "steps" executed. It is convenient to define the notion of step so that it is as machine-independent as possible. For the moment, let us adopt the following view. A constant amount of time is required to execute each line of our pseudocode. One line may take a different amount of time than another line, but we shall assume that each execution of the

We start by presenting the INSERTION-SORT procedure with the time "cost" of each statement and the number of times each statement is executed. For each *j* = 2, 3, . . . , *n*, where *n* = *length*[*A*], we let *t _{j}* be the number of times the

T(n) =c_{1}n+c_{2}(n- 1) +c_{4}(n- 1) +c_{5}(n- 1) +c_{8}(n- 1)

= (c_{1}+c_{2}+c_{4}+c_{8})n- (c_{2}+c_{4}+c_{5}+c_{8}).

This running time can be expressed as *an* + *b* for *constants* *a* and *b* that depend on the statement costs *c _{i}*; it is thus a

This worst-case running time can be expressed as *an*^{2} + *bn*+ *c* for constants *a*, *b*, and *c* that again depend on the statement costs *c _{i}*; it is thus a

In some particular cases, we shall be interested in the * average-case* or

Consider sorting *n* numbers stored in array *A* by first finding the smallest element of *A* and putting it in the first entry of another array *B*. Then find the second smallest element of *A* and put it in the second entry of *B.* Continue in this manner for the *n* elements of *A.* Write pseudocode for this algorithm, which is known as * selection sort*. Give the best-case and worst-case running times of selection sort in -notation.

Consider linear search again (see Exercise 1.1-3). How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in -notation? Justify your answers.

Consider the problem of evaluating a polynomial at a point. Given *n *coefficients *a*_{0}, *a*_{1}, . . . , *a _{n}* - 1 and a real number

Express the function *n*^{3}/1000 - 100*n*^{2} - 100*n* + 3 in terms of -notation.

How can we modify almost any algorithm to have a good best-case running time?

There are many ways to design algorithms. Insertion sort uses an * incremental* approach: having sorted the subarray

Many useful algorithms are * recursive* in structure: to solve a given problem, they call themselves recursively one or more times to deal with closely related subproblems. These algorithms typically follow a

The divide-and-conquer paradigm involves three steps at each level of the recursion:

**Divide **the problem into a number of subproblems.

**Combine **the solutions to the subproblems into the solution for the original problem.

The * merge sort* algorithm closely follows the divide-and-conquer paradigm. Intuitively, it operates as follows.

**Divide: **Divide the *n*-element sequence to be sorted into two subsequences of *n*/2 elements each.

**Conquer: **Sort the two subsequences recursively using merge sort.

**Combine: **Merge the two sorted subsequences to produce the sorted answer.

The key operation of the merge sort algorithm is the merging of two sorted sequences in the "combine" step. To perform the merging, we use an auxiliary procedure MERGE(*A,p,q,r*), where *A* is an array and *p,* *q, *and *r* are indices numbering elements of the array such that *p* *q* < *r*. The procedure assumes that the subarrays *A*[*p*. .*q*] and *A*[*q* + 1. .*r*] are in sorted order. It * merges* them to form a single sorted subarray that replaces the current subarray

MERGE-SORT(A,p,r)

1ifp<r

2thenq(p+r)/2

3 MERGE-SORT(A,p,q)

4 MERGE-SORT(A, q+ 1,r)

5 MERGE(A,p,q,r)

To sort the entire sequence *A* = *A*[1],*A*[2], . . . ,*A*[*n*], we call MERGE-SORT(*A*, 1, *length*[*A*]), where once again *length*[*A*] = *n*. If we look at the operation of the procedure bottom-up when *n* is a power of two, the algorithm consists of merging pairs of 1-item sequences to form sorted sequences of length 2, merging pairs of sequences of length 2 to form sorted sequences of length 4, and so on, until two sequences of length *n*/2 are merged to form the final sorted sequence of length *n*. Figure 1.3 illustrates this process.

When an algorithm contains a recursive call to itself, its running time can often be described by a * recurrence equation* or

In Chapter 4, we shall see how to solve common recurrences of this form.

Write pseudocode for MERGE(*A,p,q,r*).

Use mathematical induction to show that the solution of the recurrence

Referring back to the searching problem (see Exercise 1.1-3), observe that if the sequence *A* is sorted, we can check the midpoint of the sequence against *v* and eliminate half of the sequence from further consideration. **Binary search*** *is an algorithm that repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is (lg *n*).

Observe that the **while** loop of lines 5-7 of the INSERTION-SORT procedure in Section 1.1 uses a linear search to scan (backward) through the sorted subarray A[1 . . *j* - 1]. Can we use a binary search (see Exercise 1.3-5) instead to improve the overall worst-case running time of insertion sort to (*n* lg *n*)?

Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size *n*, insertion sort runs in 8*n*^{2} steps, while merge sort runs in 64*n* 1g *n* steps. For which values of *n *does insertion sort beat merge sort? How might one rewrite the merge sort pseudocode to make it even faster on small inputs?

1-1 Comparison of running times

1-2 Insertion sort on small arrays in merge sort

Although merge sort runs in (*n* lg *n*) worst-case time and insertion sort runs in (*n*^{2}) worst-case time, the constant factors in insertion sort make it faster for small *n*. Thus, it makes sense to use insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which *n*/*k* sublists of length *k* are sorted using insertion sort and then merged using the standard merging mechanism, where* k* is a value to be determined.

* b.* Show that the sublists can be merged in (

* d.* How should

Let A[1 . . *n*] be an array of *n* distinct numbers. If *i* < *j* and *A*[*i*] > *A*[*j*], then the pair (*i, j*) is called an * inversion* of

* a.* List the five inversions of the array 2, 3, 8, 6, 1.

Knuth [123] provides an encyclopedic treatment of many sorting algorithms. His comparison of sorting algorithms (page 381) includes exact step-counting analyses, like the one we performed here for insertion sort. Knuth's discussion of insertion sort encompasses several variations of the algorithm. The most important of these is Shell's sort, introduced by D. L. Shell, which uses insertion sort on periodic subsequences of the input to produce a faster sorting algorithm.