Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest.pdf), страница 6

What separates pseudocodefrom "real" code is that in pseudocode, we employ whatever expressive method is most clearand concise to specify a given algorithm. Sometimes, the clearest method is English, so do notbe 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 nottypically concerned with issues of software engineering.

Issues of data abstraction,modularity, and error handling are often ignored in order to convey the essence of thealgorithm more concisely.We start with insertion sort, which is an efficient algorithm for sorting a small number ofelements. Insertion sort works the way many people sort a hand of playing cards. We startwith an empty left hand and the cards face down on the table. We then remove one card at atime from the table and insert it into the correct position in the left hand.

To find the correctposition for a card, we compare it with each of the cards already in the hand, from right toleft, as illustrated in Figure 2.1. At all times, the cards held in the left hand are sorted, andthese cards were originally the top cards of the pile on the table.Figure 2.1: Sorting a hand of cards using insertion sort.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 besorted.

(In the code, the number n of elements in A is denoted by length[A].) The inputnumbers are sorted in place: the numbers are rearranged within the array A, with at most aconstant number of them stored outside the array at any time. The input array A contains thesorted output sequence when INSERTION-SORT is finished.INSERTION-SORT(A)1 for j ← 2 to length[A]2do key ← A[j]345678▹ Insert A[j] into the sorted sequence A[1i ← j - 1while i > 0 and A[i] > keydo A[i + 1] ← A[i]i ← i - 1A[i + 1] ← keyj - 1].Loop invariants and the correctness of insertion sortFigure 2.2 shows how this algorithm works for A = 5, 2, 4, 6, 1, 3 .

The index j indicatesthe "current card" being inserted into the hand. At the beginning of each iteration of the"outer" for loop, which is indexed by j, the subarray consisting of elements A[1 j - 1]constitute the currently sorted hand, and elements A[j + 1 n] correspond to the pile of cardsstill on the table. In fact, elements A[1 j - 1] are the elements originally in positions 1through j - 1, but now in sorted order. We state these properties of A[1 j -1] formally as aloop invariant:•At the start of each iteration of the for loop of lines 1-8, the subarray A[1consists of the elements originally in A[1 j - 1] but in sorted order.j - 1]Figure 2.2: The operation of INSERTION-SORT on the array A = 5, 2, 4, 6, 1, 3 . Arrayindices appear above the rectangles, and values stored in the array positions appear within therectangles.

(a)-(e) The iterations of the for loop of lines 1-8. In each iteration, the blackrectangle holds the key taken from A[j], which is compared with the values in shadedrectangles to its left in the test of line 5. Shaded arrows show array values moved one positionto the right in line 6, and black arrows indicate where the key is moved to in line 8. (f) Thefinal sorted array.We use loop invariants to help us understand why an algorithm is correct.

We must showthree things about a loop invariant:•••Initialization: It is true prior to the first iteration of the loop.Maintenance: If it is true before an iteration of the loop, it remains true before thenext iteration.Termination: When the loop terminates, the invariant gives us a useful property thathelps show that the algorithm is correct.When the first two properties hold, the loop invariant is true prior to every iteration of theloop. Note the similarity to mathematical induction, where to prove that a property holds, youprove a base case and an inductive step.

Here, showing that the invariant holds before the firstiteration is like the base case, and showing that the invariant holds from iteration to iteration islike the inductive step.The third property is perhaps the most important one, since we are using the loop invariant toshow correctness.

It also differs from the usual use of mathematical induction, in which theinductive step is used infinitely; here, we stop the "induction" when the loop terminates.Let us see how these properties hold for insertion sort.••Initialization: We start by showing that the loop invariant holds before the first loopiteration, when j = 2.[1] The subarray A[1 j - 1], therefore, consists of just the singleelement A[1], which is in fact the original element in A[1]. Moreover, this subarray issorted (trivially, of course), which shows that the loop invariant holds prior to the firstiteration of the loop.Maintenance: Next, we tackle the second property: showing that each iterationmaintains the loop invariant.

Informally, the body of the outer for loop works bymoving A[ j - 1], A[ j - 2], A[ j - 3], and so on by one position to the right until theproper position for A[ j] is found (lines 4-7), at which point the value of A[j] is inserted(line 8). A more formal treatment of the second property would require us to state andshow a loop invariant for the "inner" while loop. At this point, however, we prefer notto get bogged down in such formalism, and so we rely on our informal analysis toshow that the second property holds for the outer loop.•Termination: Finally, we examine what happens when the loop terminates.

Forinsertion sort, the outer for loop ends when j exceeds n, i.e., when j = n + 1.Substituting n + 1 for j in the wording of loop invariant, we have that the subarray A[1n] consists of the elements originally in A[1 n], but in sorted order. But thesubarray A[1 n] is the entire array! Hence, the entire array is sorted, which meansthat the algorithm is correct.We shall use this method of loop invariants to show correctness later in this chapter and inother chapters as well.Pseudocode conventionsWe use the following conventions in our pseudocode.1. Indentation indicates block structure. For example, the body of the for loop that beginson line 1 consists of lines 2-8, and the body of the while loop that begins on line 5contains lines 6-7 but not line 8. Our indentation style applies to if-then-elsestatements as well.

Using indentation instead of conventional indicators of blockstructure, such as begin and end statements, greatly reduces clutter while preserving,or even enhancing, clarity.[2]2. The looping constructs while, for, and repeat and the conditional constructs if, then,and else have interpretations similar to those in Pascal.[3] There is one subtledifference with respect to for loops, however: in Pascal, the value of the loop-countervariable is undefined upon exiting the loop, but in this book, the loop counter retainsits value after exiting the loop.

Thus, immediately after a for loop, the loop counter'svalue is the value that first exceeded the for loop bound. We used this property in ourcorrectness argument for insertion sort. The for loop header in line 1 is for j ← 2 tolength[A], and so when this loop terminates, j = length[A]+1 (or, equivalently, j = n+1,since n = length[A]).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 valueof expression e; it should be treated as equivalent to the assignment j ← e followed bythe assignment i ← j.5. Variables (such as i, j, and key) are local to the given procedure. We shall not useglobal variables without explicit indication.6. Array elements are accessed by specifying the array name followed by the index insquare brackets. For example, A[i] indicates the ith element of the array A. Thenotation " " is used to indicate a range of values within an array.

Thus, A[1 j]indicates the subarray of A consisting of the j elements A[1], A[2], . . . , A[j].7. Compound data are typically organized into objects, which are composed of attributesor fields. A particular field is accessed using the field name followed by the name ofits object in square brackets.

For example, we treat an array as an object with theattribute length indicating how many elements it contains. To specify the number ofelements in an array A, we write length[A]. Although we use square brackets for botharray indexing and object attributes, it will usually be clear from the context whichinterpretation is intended.A variable representing an array or object is treated as a pointer to the datarepresenting 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 assignmenty ← x.Sometimes, a pointer will refer to no object at all. In this case, we give it the specialvalue NIL.8. Parameters are passed to a procedure by value: the called procedure receives its owncopy of the parameters, and if it assigns a value to a parameter, the change is not seenby the calling procedure.

When objects are passed, the pointer to the data representingthe object is copied, but the object's fields are not. For example, if x is a parameter of acalled procedure, the assignment x ← y within the called procedure is not visible to thecalling procedure. The assignment f [x] ← 3, however, is visible.9. The boolean operators "and" and "or" are short circuiting. That is, when we evaluatethe expression "x and y" we first evaluate x. If x evaluates to FALSE, then the entireexpression cannot evaluate to TRUE, and so we do not evaluate y.

If, on the otherhand, x evaluates to TRUE, we must evaluate y to determine the value of the entireexpression. Similarly, in the expression "x or y" we evaluate the expression y only if xevaluates to FALSE. Short-circuiting operators allow us to write boolean expressionssuch as "x ≠ NIL and f[x] = y" without worrying about what happens when we try toevaluate f[x] when x is NIL.Exercises 2.1-1Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array A =31, 41, 59, 26, 41, 58 .Exercises 2.1-2Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead ofnondecreasing order.Exercises 2.1-3Consider the searching problem:••Input: A sequence of n numbers A = a1, a2, . .

. , an and a value v.Output: An index i such that v = A[i] or the special value NIL if v does not appear inA.Write pseudocode for linear search, which scans through the sequence, looking for v. Using aloop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfillsthe three necessary properties.Exercises 2.1-4Consider the problem of adding two n-bit binary integers, stored in two n-element arrays Aand B. The sum of the two integers should be stored in binary form in an (n + 1)-elementarray C. State the problem formally and write pseudocode for adding the two integers.[1]When the loop is a for loop, the moment at which we check the loop invariant just prior tothe first iteration is immediately after the initial assignment to the loop-counter variable andjust before the first test in the loop header.