Byyou alsoyoucommon example:list--not oneofofinstructionbut oneinfor items that areChances are that
now, are aware of the importance
use another kind of
er. Here is a
actions,
lists your daily life.
grouped togeth-
Shopping List
1. Milk
2. Bread
3. Eggs
4. Butter
Or, if you've ever done a home improvement project, you might have developed a:
Tools Required List
1. Hammer
2. Saw
3. Screwdriver
If you write individual items on separate pieces of paper here and there, you might get them
confused, and end up going to the grocery store for a saw. A list prevents that from happening, by
presenting a convenient method of organizing and separating your data.
Sometimes a single list isn't powerful enough for a given purpose. In this case, we use a
table--a collection of related lists--like the following:
Phone Book
A. Name List B. Address List C. Phone List
1. Ellen Cole 1. 341 Totem Dr. 1. 212-555-2368
2. Joe Jones 2. 96 Elm Dr. 2. 212-555-0982
3. Fred Smith 3. 1412 Main St. 3. 212-555-1212
Notice that this table contains three separate (vertical) lists that are all related horizontally. For
example, to call someone, you would scan down the Name List for the appropriate name, then
look across that line to the Phone List to get the corresponding phone number. Could anything
be more convenient? Thanks to a little organization and structure, you can easily find what
you're looking for, even if the individual lists are hundreds of items long.
Who uses lists and tables? Virtually everyone, from farmers (weather tables) to accountants
(ledgers) to sports fans (player statistics). Here are a couple of computer-related examples: If
you use a spreadsheet program, you're using an electronic table; and if you write a computer
program involving a lot of data that "goes together," you might organize it as a list or table called
an array.
ISBN: 0-536-12326-8
Extended Prelude to Programming: Concepts and Design, Second Edition by Stewart Venit. Copyright © 2004 by Scott/Jones, Inc. Published by Scott/Jones, Inc., in conjunc-
tion with Addison Wesley, a division of Pearson Education.
1 CHAPTER SIX 2
Arrays: Lists and Tables
Although the value of a variable may change during execution of a program, in all
our programs so far, a single value has been associated with each variable name
at any given time. In this chapter, we will discuss the concept of an array--a collection
of variables of the same type, all of which are referenced by the same name. We
will discuss both one-dimensional arrays (lists) and two-dimensional arrays (tables),
concentrating on the former. This chapter describes how to set up arrays and how
to use them to accomplish various tasks. To be more specific, you will learn
1. About declaring and using one-dimensional arrays [Section 6.1].
2. To manipulate parallel arrays [Section 6.1].
3. To search an array for a specified element [Section 6.2].
4. To sort an array into a specified order [Section 6.2].
5. To represent character strings as arrays [Section 6.3].
6. To use arrays to manipulate sequential files [Section 6.3]
7. About declaring and using two-dimensional arrays [Section 6.4].
ISBN: 0-536-12326-8
Extended Prelude to Programming: Concepts and Design, Second Edition by Stewart Venit. Copyright © 2004 by Scott/Jones, Inc. Published by Scott/Jones, Inc., in conjunc-
tion with Addison Wesley, a division of Pearson Education.
6.1 3 One-dimensional Arraysarray is a list of related data of the same type (for
A one-dimensional
example, integers or strings) referred to by a single variable name. In this
section, we will discuss how to set up and manipulate these arrays, and
present several advantages of their use.
Array Basics
Since an array stores many data values under the same variable name,
we must have some way of referring to the individual variables (or ele-
ments) contained within it. To do so, programming languages follow the
6 array name by a number enclosed in parentheses or brackets to indicate
a particular element. For example, suppose that an array called Scores con-
tains the final exam scores for a certain class. Then, to refer to the third
score in this list (that is, to refer to the third element of the array Scores),
we use the expression Scores[3]. We read this expression as "Scores sub
3," and the value 3 is called the subscript for this array element.
An array element like Scores[3] is treated by the program as a single
(or simple) variable, and may be used in input, assignment, and output
statements in the usual way. Thus, to display the value of the third student's
final exam score, we use the statement:
Write Scores[3]
Or, to input the final exam scores of a class of 25 students, we could use
the loop
For K = 1 Step 1 To 25
Write "Enter score:"
Input Scores[K]
End For
In this program segment
1 On the first pass through the loop, the input prompt ("Enter score:")
is displayed and the Input statement pauses execution, allowing the
user to enter the first test score. This value is then assigned, since
K = 1, to the first element, Scores[1], of the array Scores.
1 On the second pass through the loop, the next value input is assigned
to Scores[2], the second element of Scores.
1 On the third pass through the loop, the value input is assigned to
Scores[3].
And so on.
Arrays are stored in a computer's memory in a sequence of consecutive stor-
PROGRAMMING age locations, one location for each array element. Thus, the computer must
POINTER know, prior to the first use of an array, how many storage locations to set aside
(or allocate) for that array. In program code, this is done by declaring the
ISBN: 0-536-12326-8
162 3 CHAPTER 6 Arrays: Lists and Tables
Extended Prelude to Programming: Concepts and Design, Second Edition by Stewart Venit. Copyright © 2004 by Scott/Jones, Inc. Published by Scott/Jones, Inc., in conjunc-
tion with Addison Wesley, a division of Pearson Education.
array in a statement at the beginning of the program or program module in
which it is used. This declaration statement varies from language to lan-
guage. Here's how an array named A, consisting of a maximum of 10 integer
values, would be declared in several popular programming languages:
Declaring arrays 1 In C++, the statement
int A[10]
allocates 10 locations referred to as A[0], A[1], ..., A[9].
1 In Pascal, the statement
A = array[1..10] of integer
1
allocates 10 locations referred to as A[1], A[2], ..., A[10].
In Visual Basic, the statement 6
DIM A(1 TO 10)
allocates 10 locations referred to as A(1), A(2), ..., A(10).
In this book, we will use the pseudocode
Declare A[10]
or, more specifically,
Declare A[10] Of Integers
to allocate 10 locations referred to as A[1], A[2], . . ., A[10]. In memory, this
array would occupy ten consecutive storage locations and, assuming that
the elements have been assigned the values 1, 4, 9, 16, . . ., the array can be
pictured as follows:
Address A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10]
Contents 1 4 9 16 25 36 49 64 81 100
The following example illustrates the declaration and use of an array.
EXAMPLE 1 This program uses arrays to find the average monthly rainfall for the year
2002 in a certain city once the user has entered the rainfall for each month.
After computing the average, the program displays the list of monthly rain-
falls and their average. (In this program, we show all the variable declara-
tions needed, not just those for the arrays.)
Declare Rain[12] Of Reals
Declare Sum, Average As Real
Declare K As Integer
Set Sum = 0
For K = 1 Step 1 To 12
Write "Enter rainfall for month ", K
Input Rain[K]
Set Sum = Sum + Rain[K]
End For
ISBN: 0-536-12326-8
6.1 One-dimensional Arrays 4 163
Extended Prelude to Programming: Concepts and Design, Second Edition by Stewart Venit. Copyright © 2004 by Scott/Jones, Inc. Published by Scott/Jones, Inc., in conjunc-
tion with Addison Wesley, a division of Pearson Education.
Set Average = Sum / 12
For K = 1 Step 1 To 12
Write "Rainfall for Month ", K, " is ", Rain[K]
End For
Write "The average monthly rainfall is ", Average
In this program, the array declaration
Declare Rain[12] Of Reals
specifies that Rain is to be an array consisting of 12 subscripted variables
of real type. The first For loop inputs the 12 rainfall figures (one for each
month) into the array Rain and adds their values. Then, after the aver-
6 age is computed, the second For loop displays the input data and the last
Write statement displays their average.
Parallel Arrays
In programming, we often use parallel arrays, arrays of the same size in
which elements with the same subscript are related. For example, suppose
we wanted to modify the program of Example 1 to find the average month-
ly rainfall and snowfall. If we store the snowfall figures for each month
in an array Snow, then Rain and Snow would be parallel arrays--for each
K, Rain[K] and Snow[K] are related data items; they both refer to the
same month. The next example further illustrates this idea.
EXAMPLE 2 This program segment inputs the names of salespersons and their total
sales for the month into two parallel arrays (Names and Sales) and deter-
mines which salesperson has the greatest sales (Max).
Declare Names[100], Sales[100]
Set Max = 0
Set K = 1
Write "Enter a salesperson's name and monthly sales."
Write "Enter *, 0 when done."
Input Names[K], Sales[K]
While Names[K] <> "*"
If Sales[K] > Max Then
Set Index = K
Set Max = Sales[Index]
End If
Set K = K + 1
Write "Enter name and sales (enter *, 0 when done)"
Input Names[K], Sales[K]
End While
Write "Maximum sales for the month: ", Max
Write "Salesperson: ", Names[Index]
In this program segment, we do not use a For loop to input the data
because the number of salespersons may vary from run to run. We do, how-
ever, still need a counter (K) to serve as a subscript for the array element
ISBN: 0-536-12326-8
164 3 CHAPTER 6 Arrays: Lists and Tables
Extended Prelude to Programming: Concepts and Design, Second Edition by Stewart Venit. Copyright © 2004 by Scott/Jones, Inc. Published by Scott/Jones, Inc., in conjunc-
tion with Addison Wesley, a division of Pearson Education.
FIGURE 1
Flowchart for Declare
Example 2 Names[100],
Sales[100]
Set
Max = 0,
K=1
Input 6
Names[1],
Sales[1]
Is No
Names[K] <>
"*" ?
Yes
Is No Display
Set
Sales[K] > Names[Index]
K=K+1
Max? Sales[Index]
Yes
Set Input End
Index = K Names[K]
Max = Sales[K] Sales[K]
currently being processed. The determination of the maximum sales is
done by the If-Then structure within the While loop. When a "new" max-
imum sales figure is found, the subscript of the array element at which this
occurs (Index) is recorded and Max is set equal to this new maximum
value. After looping through all salespersons, we display the largest sales
figure and the name of the salesperson who achieved it. (See Figure 1
for a pictorial description of the logic used to solve this problem.)
ISBN: 0-536-12326-8
6.1 One-dimensional Arrays 4 165
Extended Prelude to Programming: Concepts and Design, Second Edition by Stewart Venit. Copyright © 2004 by Scott/Jones, Inc. Published by Scott/Jones, Inc., in conjunc-
tion with Addison Wesley, a division of Pearson Education.
In Example 2, each element of the array Names is a character string and
PROGRAMMING each element of Sales is a number. (We say that "Names is an array of strings"
POINTER and "Sales is an array of numbers.") Thus, the array declarations of Example
2 could have been written:
Declare Names[100] Of Strings
Declare Sales[100] Of Reals
In writing pseudocode, we will not always state the type (for example, num-
bers or strings) in the array declaration, but in writing program code, the
array type must be given in the declaration statement because a different
amount of memory has to be allocated for each data type.
6 Some Advantages of Using Arrays
We close this section by describing some of the benefits of using arrays.
As you have already seen, arrays can reduce the number of variable names
needed in a program--we can use a single array instead of a collection of
simple variables to store related data. Arrays can also help create more
efficient programs. Once data are entered into an array, they can be
processed many times without having to be input again. The next exam-
ple illustrates this point.
EXAMPLE 3 Suppose that we want to average a set of numbers input by the user and
then determine how many of them are above the average. Without arrays,
we would have to enter the numbers, find their average, and then enter
them again to determine how many exceed the average. However, using
arrays, we need not reenter input, as demonstrated in the following program.
Declare X[100]
Set Sum = 0
Set Count1 = 0
Write "Enter a number (or 0 to quit): "
Input Num
While Num <> 0
Set Count1 = Count1 + 1
Set X[Count1] = Num
Set Sum = Sum + Num
Write "Enter another number or 0 to quit: "
Input Num
End While
Set Average = Sum / Count1
Set Count2 = 0
For K = 1 Step 1 To Count1
If X[K] > Average Then
Set Count2 = Count2 + 1
End If
End For
ISBN: 0-536-12326-8
166 3 CHAPTER 6 Arrays: Lists and Tables
Extended Prelude to Programming: Concepts and Design, Second Edition by Stewart Venit. Copyright © 2004 by Scott/Jones, Inc. Published by Scott/Jones, Inc., in conjunc-
tion with Addison Wesley, a division of Pearson Education.
Write "The average is:", Average
Write "The number of items above the average is: ", Count2
In the While loop, which inputs the numbers, the Count1 variable
serves as a subscript for the array X and also counts the number of items
input. Since we do not know the latter in advance, we must use a sentinel-
controlled loop here. However, when it's time to determine the number
of items above the average (Count2), we do know how many items have
been input. Hence, a For loop can be used now with a limit value of Count1.
Another benefit of using arrays is that they help create programs that
can be used with greater generality. When we use simple variables, their
number is fixed. However, because we do not have to use all the ele-
ments that were allocated to an array when it was declared, arrays give
6
us more flexibility, as illustrated in the next example.
EXAMPLE 4 Suppose that we want to input a list of names and display them in reverse
order. This is easy to do using arrays, even if the number of names to be
input is unknown at the time the program is written.
Declare Names[100]
Set Count = 0
Write "Enter a name. (Enter * to quit.)"
Input TempName
While TempName <> "*"
Set Count = Count + 1
Set Names[Count] = TempName
Write "Enter a name. (Enter * to quit.)"
Input TempName
End While
For K = Count Step 1 To 1
Write Names[K]
End For
This program segment inputs the list of names into the array Names
and then displays the elements of that array in reverse order by "step-
ping backward" through a For loop whose control variable (K) is also the
array subscript. (The purpose of the variable TempName is to temporar-
ily hold the string entered by the user. If that string is really a name--not
the sentinel value "*"--then the While loop is entered and the string is
assigned to the next array element.)
Reading Check 6.1
In Exercises 1 and 2, what is displayed when code corresponding to the
given pseudocode is executed? In Exercise 2, assume that Letter is an
array of characters and that the characters input are F, R, O, D, O.
ISBN: 0-536-12326-8
6.1 One-dimensional Arrays 4 167
Extended Prelude to Programming: Concepts and Design, Second Edition by Stewart Venit. Copyright © 2004 by Scott/Jones, Inc. Published by Scott/Jones, Inc., in conjunc-
tion with Addison Wesley, a division of Pearson Education.
1. Declare A[12] 2. Declare Letter[5]
Set A[2] = 10 For J = 1 Step 1 To 5
For K = 1 Step 1 To 3 Input Letter[J]
Set A[2 * K + 2] = K End For
Write A[2 * K] For J = 1 Step 2 To 5
End For Write Letter[J]
End For
3. The following program segment is supposed to find the average of
the numbers input. It contains one error. Find and correct it.
Declare A[100]
Set Sum = 0
6 For K = 1 Step 1 To 10
Input X[K]
Set Sum = Sum + X[K]
End For
Set Average = Sum / 10
4. Write a program segment that inputs 20 numbers and displays them
in reverse order.
5. State two advantages of using arrays, when possible, instead of a
collection of simple (unsubscripted) variables.
6.2 3 Searching andtoSorting Arrays
The need search a one-dimensional array (or list) to locate a given
item or to sort it in a specified order occurs relatively frequently in pro-
gramming. Consequently, there are many algorithms available to perform
each of these tasks. In this section, we will present simple techniques for
searching and sorting an array.
The Serial Search Technique
Suppose you have just arrived at the airport to meet an incoming pas-
senger. You know her flight number but not the arrival time or gate, so you
consult the posted flight information which is given in the following tab-
ular form:
Flight Origin Time Gate
43 Kansas City 4:15 pm 5
21 St. Louis 5:05 pm 4
35 Dubuque 5:30 pm 7
· · · ·
· · · ·
· · · ·
To find the arrival time and gate of your friend's flight, you scan down
the leftmost column of this table until you locate her flight number and
then move across that row to read the corresponding time and gate in
the last two columns.
ISBN: 0-536-12326-8
168 3 CHAPTER 6 Arrays: Lists and Tables
Extended Prelude to Programming: Concepts and Design, Second Edition by Stewart Venit. Copyright © 2004 by Scott/Jones, Inc. Published by Scott/Jones, Inc., in conjunc-
tion with Addison Wesley, a division of Pearson Education.
In carrying out this process, you have performed a table lookup. In
data processing terminology, the item you were seeking (your friend's
flight number) is called the search key, the list of all such items makes up
the table keys, and, in general, the data in the table are called the table val-
ues. The way in which you looked for the desired flight number, check-
ing them in the order listed, makes this a serial search.
Basic steps in a In writing a program to perform a serial search to find a given search
serial search key, we have to:
1. Load the table--input the data in the table, usually from a file (see
Chapter 5), into parallel arrays, one for each column of the table.
2. Search the array of table keys--compare the search key to the ele-
ments of this array, one by one, until a match occurs (or the end of the
array is reached).
6
3. Display the search key and corresponding table values or, if the
search key is not found in the array, display a message to this effect.
Use a Flag to Indicate a Successful Search In step 2 of the search procedure
TIP described above, we loop through the array of table keys to see if any element
is identical to the given search key. Either
1 The search will be successful--the item we are seeking (the search key) will
match one of the table keys.
or
1 The search will fail--no match will occur.
When we exit the loop and carry out step 3 of the procedure, we must know
which of these two possibilities has occurred so that the appropriate message
can be displayed. An elegant way to indicate whether or not the search was
successful is to use a variable known as a flag.
A flag is a variable that takes on one of two values, typically 0 and 1, and
is used to indicate whether or not a certain action has taken place. Usually,
a value of 0 indicates that the action has not occurred; a value of 1 indi-
cates that it has occurred. In a serial search, we set the flag equal to 0 prior
to the search (prior to entering the search loop) and, if a match does occur
within the loop, we change the flag's value to 1. Thus, when we exit the
loop, the value of the flag can be used to verify the success or failure of the
search and to display the proper message.
Pseudocode for a If a list of table keys is contained in an array (KeyData) with N ele-
serial search ments, the pseudocode for performing a serial search for an item called
Key is as follows.
Set the subscript (Index) of the current table key equal to 0
Set a flag (Found) equal to 0
ISBN: 0-536-12326-8
6.2 Searching and Sorting Arrays 4 169
Extended Prelude to Programming: Concepts and Design, Second Edition by Stewart Venit. Copyright © 2004 by Scott/Jones, Inc. Published by Scott/Jones, Inc., in conjunc-
tion with Addison Wesley, a division of Pearson Education.
While (Found = 0) And (Index < N)
Increment Index by 1: Set Index = Index + 1
If KeyData[Index] = Key Then
Set Found = 1
End If
End While
If Found = 1 Then
Display the array elements with subscript = Index
Else
Display a message that the search was unsuccessful
End If
6 FIGURE 2
Serial Search of Start
the Array
KeyData for
the Element Key
Set
Index = 0
Found = 0
Are
No Is No
Found = 0
Found = 1
And Index
?
Yes Yes
Display Display
Set
"Index" "not
Index =
array found"
Index + 1
elements message
Is
KeyData No
[Index] = End
Key?
Yes
Set
Found = 1
ISBN: 0-536-12326-8
170 3 CHAPTER 6 Arrays: Lists and Tables
Extended Prelude to Programming: Concepts and Design, Second Edition by Stewart Venit. Copyright © 2004 by Scott/Jones, Inc. Published by Scott/Jones, Inc., in conjunc-
tion with Addison Wesley, a division of Pearson Education.
In this pseudocode, the variable Index is used within the loop to hold
the current array subscript; the variable Found is a flag that indicates
whether or not the search has been successful. (We could have used a
For loop with counter Index running from 1 to N, but the While loop
allows us to exit as soon as a match is found.) Upon exit from the While
loop, a value of 1 for Found indicates that the search was successful--Key
has been found among the table keys--and Index gives its location (sub-
script) in KeyData. If the value of Found is 0 upon loop exit, the search
Key was not found and we display this fact. The flowchart in Figure 2
pictures the logic used in a serial search.
The next example provides a particular instance of the serial search
technique.
6
EXAMPLE 5 This program segment displays the test score for a particular student when
the student's identification number is input by the user. To do so, it search-
es an array, IDNumbers, of identification numbers for the ID number input
(IDKey), and
1 Displays the corresponding student name and test score contained
in two parallel arrays, Names and Scores, if the number IDKey is
found in the array IDNumbers.
or
1 Displays an appropriate message if the IDKey is not found in the array
IDNumbers.
We assume that the arrays IDNumbers, Names, and Scores have
already been declared and loaded with the necessary data (from a file) and
that the number of elements in each of these parallel arrays is N.
Write "Enter a student ID number: "
Input IDKey
Set Index = 0
Set Found = 0
While (Found = 0) And (Index < N)
Set Index = Index + 1
If IDNumbers[Index] = IDKey Then
Set Found = 1
End If
End While
If Found = 0 Then
Write "STUDENT ID NOT FOUND"
Else
Write "ID Number: ", IDKey
Write "Student name: ", Names[Index]
Write "Test score: ", Scores[Index]
End If
ISBN: 0-536-12326-8
6.2 Searching and Sorting Arrays 4 171
Extended Prelude to Programming: Concepts and Design, Second Edition by Stewart Venit. Copyright © 2004 by Scott/Jones, Inc. Published by Scott/Jones, Inc., in conjunc-
tion with Addison Wesley, a division of Pearson Education.
The first two statements of this program segment prompt for and
input the ID number for the student we are seeking. The remaining state-
ments search for this ID number and display the appropriate message
depending on whether or not it's found. (Compare this part of the pro-
gram segment to the general pseudocode given earlier in this section.)
The Bubble Sort Technique
In sorting data, we arrange it in some prescribed order. For numbers, the
"prescribed order" would be either ascending (from smallest to largest)
or descending (from largest to smallest); for names it would usually be
alphabetical.
6 As long as the number of items to be sorted is relatively small (say, few-
er than 100), the bubble sort algorithm provides a reasonably quick and
simple way of doing it. To apply this technique, we make several sweeps
(or passes) through the data, and on each pass
1 We compare all adjacent pairs of data items.
and
1 We interchange the data in an adjacent pair if they are not already in
the proper order.
We continue making passes until no interchanges are necessary in an
entire pass, which indicates that the data are now sorted.
To illustrate the bubble sort, let us first do a simple example by hand.
Figure 3 demonstrates the process for a data set consisting of the num-
bers 9, 13, 5, 8, 6. In each pass, we show the data at the start of the pass
on the left and the results of the four comparisons in the next four
columns. If an interchange takes place, the arrows cross, indicating which
items have been swapped.
The bubble sort gets its name from the fact that, as you can see in
Figure 3, the larger numbers "sink" to the bottom (the end) of the list and
the smaller ones "bubble" to the top. After the first pass, the largest num-
ber will be at the bottom of the list; after the second pass, the second
largest will be next to last; and so on. Thus, in sorting N items, it will take
at most N 1 passes through the list to sort them (and one additional
pass to determine that they are sorted).
Pseudocode for The bubble sort of an array A of N numbers in ascending order is
the bubble sort described in pseudocode as follows (a flowchart is given in Figure 4 on
page 174):
While the array A is not sorted
For K = 1 Step 1 To N 1
If A[K] > A[K + 1] Then
Interchange A[K] and A[K + 1]
End If
End For
End While
ISBN: 0-536-12326-8
172 3 CHAPTER 6 Arrays: Lists and Tables
Extended Prelude to Programming: Concepts and Design, Second Edition by Stewart Venit. Copyright © 2004 by Scott/Jones, Inc. Published by Scott/Jones, Inc., in conjunc-
tion with Addison Wesley, a division of Pearson Education.
FIGURE 3 First Pass
Bubble Sort of
the Numbers 9 9 9 9 9
9, 13, 5, 8, 6
13 13 5 5 5
5 5 13 8 8
8 8 8 13 6
6 6 6 6 13
Second Pass
9
5
5
9
5
8
5
8
5
8
6
8 8 9 6 6
6 6 6 9 9
13 13 13 13 13
Third Pass
5 5 5 5 5
8 8 6 6 6
6 6 8 8 8
9 9 9 9 9
13 13 13 13 13
Fourth Pass
No interchanges take place; the numbers are sorted.
This pseudocode is somewhat vague (and needs to be refined) regard-
ing two issues:
1. To interchange array elements A[K] and A[K+1], we temporarily copy
one of them to another location and then swap their values:
Set Temp = A[K]
Set A[K] = A[K + 1]
Set A[K + 1] = Temp
(Try it out; execute these statements with A[K] = 3 and A[K+1] = 5.)
Notice that we cannot swap the values using the pair of statements:
Set A[K] = A[K + 1]
Set A[K + 1] = A[K]
ISBN: 0-536-12326-8
6.2 Searching and Sorting Arrays 4 173
Extended Prelude to Programming: Concepts and Design, Second Edition by Stewart Venit. Copyright © 2004 by Scott/Jones, Inc. Published by Scott/Jones, Inc., in conjunc-
tion with Addison Wesley, a division of Pearson Education.
FIGURE 4
Bubble Sort of Start
the Array A in
Ascending
Order
Is Yes
A sorted End
?
No
6 Set
K=1
Is Yes
K>N1
?
No
Is
Yes Interchange
A[K] >
A[K] and
A[K+1]
A[K+1]
?
No
Set
K=K+1
This pair of statements sets both elements equal to the original value
of A[K + 1]!
2. To determine when the list is sorted, we borrow a trick from the seri-
al search algorithm given earlier in this section--we use a flag. In the
ISBN: 0-536-12326-8
174 3 CHAPTER 6 Arrays: Lists and Tables
Extended Prelude to Programming: Concepts and Design, Second Edition by Stewart Venit. Copyright © 2004 by Scott/Jones, Inc. Published by Scott/Jones, Inc., in conjunc-
tion with Addison Wesley, a division of Pearson Education.
bubble sort algorithm, a flag value of 0 indicates that during the latest
pass, an interchange did take place. We therefore initialize the flag to
0, and continue to reenter the While loop as long as its value remains
0. Once inside the loop, we set the flag equal to 1 and change it back
to 0 if an interchange takes place. If no interchange takes place (mean-
ing the data are sorted), the flag remains 1, and the loop
