Section 7.4. Sorting and Searching


[Page 356 (continued)]

7.4. Sorting and Searching

A sort is an algorithm for ordering an array. Of the many different techniques for sorting an array we discuss two, the bubble sort and the Shell sort. Both require the interchange of values stored in a pair of variables. If varl, var2, and temp are all variables of the same data type (such as all String), then the statements

temp = varl varl = var2 var2 = temp


assign var1's value to var2 and var2's value to var1.


[Page 357]

Example 1.

The following program alphabetizes two words supplied in text boxes:

Private Sub btnAlphabetize_Click(...) Handles btnAlphabetize.Click   'Alphabetize two words   Dim firstWord, secondWord, temp As String   firstWord = txtFirstWord.Text   secondWord = txtSecondWord.Text   If (firstWord > secondWord) Then   'Swap the two words     temp = firstWord     firstWord = secondWord     secondWord = temp   End If   txtResult.Text = firstWord & " before " & secondWord End Sub


[Run, type "beauty" and "age" into the text boxes, and click the button.]

Bubble Sort

The bubble sort is an algorithm that compares adjacent items and swaps those that are out of order. If this process is repeated enough times, the list will be ordered. Let's carry out this process on the list Pebbles, Barney, Wilma, Fred, and Dino. The steps for each pass through the list are as follows:

  1. Compare the first and second items. If they are out of order, swap them.

  2. Compare the second and third items. If they are out of order, swap them.

  3. Repeat this pattern for all remaining pairs. The final comparison and possible swap are between the next-to-last and last items.

The first time through the list, this process is repeated to the end of the list. This is called the first pass. After the first pass, the last item (Wilma) will be in its proper position. Therefore, the second pass does not have to consider it and so requires one less comparison. At the end of the second pass, the last two items will be in their proper position. (The items that must have reached their proper position have been underlined.) Each successive pass requires one less comparison. After four passes, the last four items will be in their proper positions, and hence, the first will be also.


[Page 358]

Example 2.
(This item is displayed on pages 358 - 359 in the print version)

The following program alphabetizes the names Pebbles, Barney, Wilma, Fred, and Dino. Sorting the list requires a pair of nested loops. The inner loop performs a single pass, and the outer loop controls the number of passes.

Dim person() As String = {"Pebbles", "Barney", "Wilma", "Fred", "Dino"} Private Sub frmFlintstones_Load(...) Handles MyBase.Load   'Display unsorted list   For i As Integer = 0 To 4     lstPeople.Items.Add(person(i))   Next End Sub Private Sub btnSort_Click(...) Handles btnSort.Click   'Bubble sort names   Dim temp As String 
[Page 359]
For passNum As Integer = 1 To 4 'Number of passes is 1 less than 'number of items For i As Integer = 1 To 5 - passNum 'Each pass needs 1 less comparison If (person(i - 1) > person(i)) Then temp = person(i - 1) person(i - 1) = person(i) person(i) = temp End If Next Next 'Display alphabetized list lstPeople.Items.Clear() For i As Integer = 0 To 4 lstPeople.Items.Add(person(i)) Next End Sub


[Run, and click the button.]

Example 3.
(This item is displayed on pages 359 - 361 in the print version)

Table 7.5 contains facts about the 10 most populous states with listings in ascending order by state abbreviation. The following program sorts the table in descending order by population. Data are read from a file into an array of structures by the form's Load event procedure. When btnDisplayStats is clicked, the array is sorted based on the population field.

Table 7.5. The 10 most populous states.

State

Per Capita Income

% College Graduates

Population in Millions

CA

$32,678

27.5

33.9

FL

$28,493

22.8

16.0

GA

$28,438

23.1

8.2

IL

$32,755

27.1

12.4

MI

$29,538

23.0

9.9

NJ

$38,153

30.1

8.4

NY

$35,884

28.7

19.0

OH

$28,619

24.6

11.4

PA

$30,617

24.3

12.3

TX

$28,486

23.9

20.9

Note: Column 3 gives the percentage of residents age 25 or older with a college degree.



[Page 360]
Structure District Dim name As String Dim income As Double Dim collegeGrad As Double Dim population As Double End Structure Dim state(9) As District Private Sub frmStates_Load(...) Handles MyBase.Load 'Assume the data for state name, income, % college grads, 'and population in millions are in the file "STATES.TXT" 'First four lines of file contain the data CA, 32678, 27.5, 33.9 Dim sr As IO.StreamReader = IO.File.OpenText("STATES.TXT") For i As Integer = 0 To 9 state(i).name = sr.ReadLine state(i).income = CDbl(sr.ReadLine) state(i).collegeGrad = CDbl(sr.ReadLine) state(i).population = CDbl(sr.ReadLine) Next sr.Close() End Sub Private Sub btnDisplayStats_Click(...) Handles btnDisplayStats.Click SortData() ShowData() End Sub Sub ShowData() 'Display ordered table Dim fmtStr As String = "{0,-4}{1,11:C0}{2,8:N1}{3,9:N1}" lstStats.Items.Clear() For i As Integer = 0 To 9 lstStats.Items.Add(String.Format(fmtStr, state(i).name, _ state(i).income, state(i).collegeGrad, state(i).population)) Next End Sub Sub SortData() 'Bubble sort table in descending order by population For passNum As Integer = 1 To 9 For index As Integer = 1 To 10 - passNum If (state(index - 1).population < state(index).population) Then SwapData(index) End If Next Next End Sub
[Page 361]
Sub SwapData(ByVal index As Integer) 'Swap entries Dim temp As District temp = state(index - 1) state(index - 1) = state(index) state(index) = temp End Sub


[Run, and click the button.]

Shell Sort

The bubble sort is easy to understand and program. However, it is too slow for really long lists. The Shell sort, named for its inventor, Donald L. Shell, is much more efficient in such cases. It compares distant items first and works its way down to nearby items. The interval separating the compared items is called the gap. The gap begins at one-half the length of the list and is successively halved until eventually each item is compared with its neighbor as in the bubble sort. The algorithm for a list of n + 1 items referred to as item 0 through item I is as follows.

  1. Begin with a gap of g = Int([n + 14]/2).

  2. Compare items 0 and g, items 1 and 2 +g, 2 and 2+g,..., n-g and n. Swap any pairs that are out of order.

  3. Repeat Step 2 until no swaps are made for gap g.

  4. Halve the value of g.

  5. Repeat Steps 2, 3, and 4 until the value of g is 0.

The Shell sort is illustrated in what follows, in which crossing arrows indicate that a swap occurred:

Initial Gap = Int([Number of Items]/2) = Int(5/2) = 2


[Page 362]

Because there was a swap, use the same gap for the second pass.

Again, there was a swap, so keep the current gap.

There were no swaps for the current gap of 2, so

Next Gap = Int([Previous Gap]/2) = Int(2/2) = 1.

Because there was a swap (actually two swaps), keep the same gap.

Because there were no swaps for the current gap, then

Next Gap = Int([Previous Gap]/2) = Int(1/2) = 0,

and the Shell sort is complete.


[Page 363]

Notice that the Shell sort required 17 comparisons to sort the list, whereas the bubble sort required only 10 comparisons for the same list. This illustrates the fact that for very short lists, the bubble sort is preferable; however, for lists of 30 items or more, the Shell sort will consistently outperform the bubble sort. Table 7.6 shows the average number of comparisons required to sort arrays of varying sizes.

Table 7.6. Efficiency of bubble and Shell sorts.

Array Elements

Bubble Sort Comparisons

Shell Sort Comparisons

5

10

15

10

45

57

15

105

115

20

190

192

25

300

302

30

435

364

50

1225

926

100

4950

2638

500

124,750

22,517

1000

499,500

58,460


Example 4.
(This item is displayed on pages 363 - 365 in the print version)

The following program uses the Shell sort to alphabetize the parts of a running shoe. (See Figure 7.5.) The data are read into an array whose size is large enough to guarantee sufficient space. In the form's Load event procedure, the variable numParts provides the subscripts for the array and serves as a counter. The final value of numParts is available to all procedures because the variable was created in the Declarations section of the Code window. The Sub procedure SortData uses a flag to indicate if a swap has been made during a pass.

Figure 7.5. Running shoe.



[Page 364]
Dim part(50) AsString Dim numParts As Integer Private Sub frmShoe_Load(...) HandlesMyBase.Load 'Read names of parts numParts = 0 'Number of parts Dim sr As IO.StreamReader = IO.File.OpenText("SHOEPART.TXT") Do While (sr.Peek <> -1) And (numParts < part.GetUpperBound(0)) part(numParts) = sr.ReadLine numParts += 1 Loop sr.Close() End Sub Private Sub btnDisplay_Click(...) Handles btnDisplay.Click 'Sort and display parts of running shoe SortData() ShowData() End Sub Sub SortData() 'Shell sort shoe parts Dim gap As Integer, doneFlag As Boolean Dim temp As String gap = CInt(Int(numParts / 2)) Do While gap >= 1 Do doneFlag = True For index As Integer = 0 To numParts - 1 - gap If part(index) > part(index + gap) Then temp = part(index) part(index) = part(index + gap) part(index + gap) = temp doneFlag = False End If Next Loop Until doneFlag = True 'Also can be Loop UntildoneFlag gap = CInt(Int(gap / 2)) 'Halve the length of the gap Loop End Sub Sub ShowData() 'Display sorted list of parts lstParts.Items.Clear() For i As Integer = 0 To numParts - 1 lstParts.Items.Add(part(i)) Next End Sub



[Page 365]

[Run, and click the button.]

Searching

Suppose we had an array of 1000 names in alphabetical order and wanted to locate a specific person in the list. One approach would be to start with the first name and consider each name until a match was found. This process is called a sequential search. We would find a person whose name begins with "A" rather quickly, but 1000 comparisons might be necessary to find a person whose name begins with "Z." For much longer lists, searching could be a time-consuming matter. However, there is a method, called a binary search, that shortens the task considerably.

Let us refer to the sought item as quarry. The binary search looks for quarry by determining in which half of the list it lies. The other half is then discarded, and the retained half is temporarily regarded as the entire list. The process is repeated until the item is found. A flag can indicate if quarry has been found.

The algorithm for a binary search of an ascending list is as follows (Figure 7.6 shows the flowchart for a binary search):

  1. At each stage, denote the subscript of the first item in the retained list by first and the subscript of the last item by last. Initially, the value of first is 0, the value of last is one less than the number of items in the list, and the value of flag is False.

  2. Look at the middle item of the current list, the item having the subscript middle = Int((first + last)/2).

  3. If the middle item is quarry, then flag is set to True and the search is over.

  4. If the middle item is greater than quarry, then quarry should be in the first half of the list. So the subscript of quarry must lie between first and middle -1. That is, the new value of last is middle -1.


    [Page 366]

    Figure 7.6. Flowchart for a binary search.

  5. If the middle item is less than quarry, then quarry should be in the second half of the list of possible items. So the subscript of quarry must lie between middle +1 and last. That is, the new value of first is middle +1.


  6. [Page 367]
  7. Repeat Steps 2 through 5 until quarry is found or until the halving process uses up the entire list. (When the entire list has been used up, first > last.) In the second case, quarry was not in the original list.

Example 5.
(This item is displayed on pages 367 - 368 in the print version)

In the following program the array firm() contains the alphabetized names of up to 100 corporations. The program requests the name of a corporation as input and uses a binary search to determine whether the corporation is in the array.

Dim firm(99) As String Dim numFirms As Integer Private Sub frmCompanies_Load(...) Handles MyBase .Load   'Fill array with data from FIRMS.TXT, which contains   'the names of up to 100 companies   Dim sr As IO.StreamReader = IO.File.OpenText("FIRMS.TXT")   numFirms = 0   Do While (sr.Peek <> -1) And (numFirms < firm.GetUpperBound(0))     firm(numFirms) = sr.ReadLine     numFirms += 1   Loop   sr.Close() End Sub Private Sub btnSearch_Click(...) Handles btnSearch.Click   Dim corp, result As String   corp = txtCorporation.Text.ToUpper   result = ""   BinarySearch(corp, result)   'Display results of search   txtResult.Text = corp & " " & result End Sub Sub BinarySearch(ByVal corp As String, ByRef result As String)   'Array firm() assumed already ordered alphabetically   'Binary search of firm() for corp   Dim first, middle, last As Integer   Dim foundFlag As Boolean = False   first = 0   last = numFirms - 1   Do While (first <= last) And (Not foundFlag)     middle = CInt(Int((first + last) / 2))     Select Case firm(middle).ToUpper       Case corp         foundFlag = True 
[Page 368]
Case Is > corp last = middle - 1 Case Is < corp first = middle + 1 End Select Loop If foundFlag Then result = "found" Else result = "not found" End If End Sub


[Run, type "IBM" into the text box, and click the button.]

Suppose the array contains 100 corporations and the corporation input in Example 5 is in the second half of the array. On the first pass, middle would be assigned Int((0 + 99)/2) = Int(49.5) = 49 and then first would be altered to 49 + 1 = 50. On the second pass, middle would be assigned Int((50 + 99)/2) = Int(74.5) = 74. If the corporation is not the array element with subscript 74, then either last would be assigned 73 or first would be assigned 75, depending on whether the corporation appears before or after the 74th element. Each pass through the loop halves the range of subscripts containing the corporation until the corporation is located.

In Example 5, the binary search merely reported whether an array contained a certain item. After finding the item, its array subscript was not needed. However, if the search had been carried out on an array of structures (as in Table 7.5), the subscript of the found item could be used to retrieve the related information for the other members. This process, called a table lookup, is used in the following example.

Example 6.
(This item is displayed on pages 368 - 370 in the print version)

The following program uses a binary search procedure to locate the data for a state from Example 3 requested by the user. The program does not include a sort of the text file STATES.TXT, because the file is already ordered alphabetically by city name.

Structure District   Dim name As String   Dim income As Double   Dim collegeGrad As Double   Dim population As Double End Structure 
[Page 369]
Dim state(9) As District Private Sub frmStates_Load(...) Handles MyBase.Load 'Assume that the data for state name, per capita income, '% college grads, and population in millions 'have been placed in the file "STATES.TXT" 'First four lines of file contain the data CA 32678,27.5,33.9 Dim sr As IO.StreamReader = IO.File.OpenText("STATES.TXT") For i As Integer = 0 To 9 state(i).name = sr.ReadLine state(i).income = CDbl(sr.ReadLine) state(i).collegeGrad = CDbl(sr.ReadLine) state(i).population = CDbl(sr.ReadLine) Next sr.Close() End Sub Private Sub btnDisplayStats_Click(...) Handles btnDisplayStats.Click 'Search for state in the populous states table Dim searchState As String, result As Integer searchState = mtxtState.Text.ToUpper result = FindState(searchState) If result >= 0 Then ShowData(result) Else MsgBox(searchState & " not in file", 0, "Not Found") End If End Sub Function FindState(ByVal searchState As String) As Integer 'Binary search table for state name Dim first, middle, last As Integer first = 0 last = 9 Do While (first <= last) middle = CInt(Int((first + last) / 2)) Select Case city(middle).name.ToUpper Case searchState Return middle Case Is > searchState last = middle - 1 Case Is < searchState first = middle + 1 End Select Loop Return -1 End Function
[Page 370]
Sub ShowData(ByVal result As Integer) 'Display the data for the specified state Dim fmtStr As String = "{0,-4}{1,11:C0}{2,8:N1}{3,9:N1}" txtStats.text = String.Format(fmtStr, state(result).name, _ state(result).income, state(result).collegeGrad, _ state(result).population.) End Sub


[Run, type "OH" into the masked text box, and click the button.]

Comments

  1. Suppose that our bubble sort algorithm is applied to an ordered list. The algorithm will still make n - 1 passes through the list. The process could be shortened for some lists by flagging the presence of out-of-order items as in the Shell sort.

  2. In Example 3, an array of structures already ordered by one member was sorted by another member. Usually, an array of structures is sorted by the member to be searched when accessing the member. This member is called the key member.

  3. Suppose that an array of 2000 items is searched sequentiallythat is, one item after anotherin order to locate a specific item. The number of comparisons would vary from 1 to 2000, with an average of 1000. With a binary search, the number of comparisons would be at most 11, because 211 >2000.

  4. The method ToUpper converts all the characters in a string to uppercase. ToUpper is useful in sorting and searching arrays of strings when the alphabetic case (upper or lower) is unimportant. For instance, Example 5 includes ToUpper in the Select Case comparisons, and so the binary search will locate "Mobil" in the array even if the user entered "MOBIL".

  5. Visual Basic has a built-in sort routine that can be used to sort arrays. The statement

    Array.Sort(arrayName)

    sorts arrayName into ascending order. For instance, in Example 2 the event procedure can be replaced with the following code.

    Private Sub btnSort_Click(...) Handles btnSort.Click   Dim name() As String = {"Pebbles", "Barney", "Wilma", _                         "Fred", "Dino"}   Array.Sort(name)   'Display alphabetized list   lstNames.Items.Clear() 
    [Page 371]
    For i As Integer = 0 To 4
    lstNames.Items.Add(name(i)) Next End Sub

    Array.Sort cannot be used with arrays of structures and therefore is not adequate for our purposes.

Practice Problems 7.4

1.

The pseudocode for a bubble sort of an array of n items follows. Why is the terminating value of the outer loop n-1 and the terminating value of the inner loop n-j?

 For j As Integer = 1 To n - 1   For k As Integer = 1 To n - j     If [(k-1)st and kth items are out of order] Then [swap them]   Next Next


2.

Complete the table that follows by filling in the values of each variable after successive passes of a binary search of an array of 20 items, where the sought item is in the position 13.

First

Last

Middle

0

19

9

10

19

 


Exercises 7.4

In Exercises 1 through 4, determine the output displayed in the list box when the button is clicked.

1.

Private Sub btnDisplay_Click(...) Handles btnDisplay.Click   Dim p As Integer = 100   Dim q As Integer = 200   Dim temp As Integer = p   p = q   q = temp   lstOutput.Items.Add(p)   lstOutput.Items.Add(q) End Sub


2.

Dim gag() As String = {"Stan"," Oliver"} Private Sub btnDisplay_Click(...) Handles btnDisplay.Click  Dim temp As String   If gag(1) < gag(0) Then    temp = gag(1) 
[Page 372]
gag(1) = gag(0)
gag(0) = temp End If lstOutput.Items.Add(gag(0)) lstOutput.Items.Add(gag(1)) End Sub


3.

Private Sub btnDisplay_Click(...) Handles btnDisplay.Click  Dim x, y, temp As Double  Dim swappedFlag As Boolean = False  x = 7  y = 11  If y > x Then    temp = x    x = y    y = temp    swappedF1ag = True  End If  lstOutput.Items.Add(x)  lstOutput.Items.Add(y)  If swappedFlag Then    lstOutput.Items.Add("Numbers interchanged.")  End If End Sub


4.

Dim a(2) As Integer Private Sub btnDisplay_Click(...) Handles btnDisplay.Click  Dim temp As Integer  For j As Integer = 0 To 1   For k As Integer = 0 To 2 - j    If a(k) > a(k + 1) Then     temp = a(k)     a(k) = a(k + 1)     a(k + 1) = temp    End If   Next  Next  For j As Integer = 0 To 2    lstOutput.Items.Add(a(j))  Next End Sub Private Sub frmNumbers_Load(...) Handles MyBase.Load    Dim sr As IO.StreamReader = IO.File.OpenText("DATA.TXT")    For j As Integer = 0 To 2      a(j) = CInt(sr.ReadLine)    Next    sr.Close() End Sub 


(Assume that the three lines of the file DATA.TXT contain the following entries: 7, 4, 3.)


[Page 373]

In Exercises 5 and 6, identify the errors.

5.

Dim c(3), d(3) As Integer Private Sub btnDisplay_Click(...) Handles btnDisplay.Click   'Swap two items   c(3) = d(3)   d(3) = c(3)   lstOutput.Items.Add(c(3))   lstOutput.Items.Add(d(3)) End Sub Private Sub frmNumbers_Load(...) Handles MyBase.Load   Dim sr As IO.StreamReader = IO.File.OpenText("DATA.TXT")   For i As Integer = 0 To 3     c(i) = CInt(sr.ReadLine)     d(i) = CInt(sr.ReadLine)   Next   sr.Close() End Sub


(Assume that the eight lines of the file DATA.TXT contain the following entries:1, 2, 3, 4, 5, 6, 7, 8.)

6.

Dim a(2), b(2) As Integer Private Sub btnDisplay_Click(...) Handles btnDisplay.Click   'Swap the two arrays   Dim temp(2) As Integer   a = b   b = a End Sub Private Sub frmNumbers_Load(...) Handles MyBase.Load   Dim sr As IO.StreamReader = IO.File.OpenText("DATA.TXT")   For i As Integer = 0 To 2     a(i) = CInt(sr.ReadLine)     b(i) = CInt(sr.ReadLine)   Next   sr.Close() End Sub


(Assume that the six lines of the file DATA.TXT contain the following entries:1, 3, 5, 7, 9, 11.)

7.

Which type of search would be best for the following array?


[Page 374]
8.

Which type of search would be best for the following array?

9.

Consider the items Tin Man, Dorothy, Scarecrow, and Lion in that order. After how many swaps in a bubble sort will the list be in alphabetical order?

10.

How many comparisons will be made in a bubble sort of six items?

11.

How many comparisons will be made in a bubble sort of n items?

12.

Modify the program in Example 2 so that it will keep track of the number of swaps and comparisons and display these numbers before ending.

13.

Rework Exercise 9 using the Shell sort.

14.

How many comparisons would be made in a Shell sort of six items if the items were originally in descending order and were sorted in ascending order?

15.

If a list of six items is already in the proper order, how many comparisons will be made by a Shell sort?

16.

Suppose a list of 5000 numbers is to be sorted, but the numbers consist of only 1, 2, 3, and 4. Describe a method of sorting the list that would be much faster than either the bubble or Shell sort.

17.

What is the maximum number of comparisons required to find an item in a sequential search of 16 items? What is the average number of comparisons? What is the maximum number of comparisons required to find an item in a binary search of 16 items?

18.

Redo Exercise 17 with 2n items, where is any positive integer.

In Exercises 19 through 26, write a program (or procedure) to complete the stated task.

19.

Exchange the values of the variables x, y, and z so that x has y's value, y has z's value, and z has x's value.

20.

Display the names of the seven dwarfs in alphabetical order. For the contents of a text file use Doc, Grumpy, Sleepy, Happy, Bashful, Sneezy, and Dopey.

21.

The nation's capital has long been a popular staging area for political, religious, and other large public rallies, protest marches, and demonstrations. The events in Table 7.7 have drawn the largest crowds, according to estimates from D.C., U.S. Park, or Capitol police. Read the data into an array of structures and display a similar table with the event names in alphabetical order. Note: The data is contained in the file EVENTS.TXT.

22.

Table 7.8 presents statistics on the five leading sneaker brands. Read the data into an array of structures, and display a similar table with wholesale revenue in descending order.

23.

Accept 10 words to be input in alphabetical order, and store them in an array. Then accept an 11th word as input, and store it in the array in its correct alphabetical position.


[Page 375]

Table 7.7. Large Public Displays of Emotion in Washington, D.C.

Event

Crowd Estimate (in thousands)

Lyndon Johnson inauguration (1/23/65)

1,200

Bicentennial fireworks (7/4/76)

1,000

Desert Storm rally (6/8/91)

800

Bill Clinton inauguration (l/20/93)

800

Beach Boys concert (7/4/85)

625

Washington Redskins victory parade (2/3/88)

600

Vietnam moratorium rally (11/15/69)

600

Ronald Reagan inauguration (1/20/81)

500

U.S. Iran hostage motorcade (l/28/81)

500


Table 7.8. 2004 U.S.market share in sneakers.

Brand

Wholesale Revenue (in millions)

Percentage Share of U.S. Market

Adidas USA

792

8.9

Fila

392

4.4

New Balance

1024

11.5

Nike

3231

36.3

Reebok

1086

12.1

Source: Morgan Stanley Dean Witter Research.


24.

An airline has a list of 200 flight numbers (between 1 and 1000) in ascending order in the file FLIGHTS.TXT. Accept a number as input and do a binary search of the list to determine if the flight number is valid.

25.

Allow a number n to be input by the user. Then accept as input a list of numbers. Place the numbers into an array and apply a bubble sort.

26.

Rework Exercise 25, but use a flag to detect the presence of out-of-order items as in the Shell sort.

27.

Write a program that accepts a word as input and converts it into Morse code. The dots and dashes corresponding to each letter of the alphabet are as follows:

A .

H . . . .

O

V . . .

B . . .

I . .

P . .

W .

C ..

J .

Q .

X . .

D . .

K .

R . .

Y .

E .

L . . .

S . . .

Z . .

F . . .

M

T

 

G .

N .

U . .

 



[Page 376]
28.

Write a program that accepts an American word as input and performs a binary search to translate it into its British equivalent. Use the following list of words for data, and account for the case when the word requested is not in the list:

American

British

American

British

attic

loft

ice cream

ice

business suit

lounge suit

megaphone

loud hailer

elevator

lift

radio

wireless

flashlight

torch

sneakers

plimsolls

french fries

chips

truck

lorry

gasoline

petrol

zero

nought


29.

Write a program that accepts a student's name and seven test scores as input and calculates the average score after dropping the two lowest scores.

30.

Suppose letter grades are assigned as follows:

97 and above

A+

7476

C

9496

A

7073

C-

9093

A

6769

D+

8789

B+

6466

D

8486

B

6063

D

8083

B

059

F

7779

C+

  


Write a program that accepts a grade as input and displays the corresponding letter.

Hint: This problem shows that when you search an array, you don't always look for equality. Set up an array of structures with the member range containing the values 97, 94, 90, 87, 84, ..., 0 and the member letter containing A+, A, A , B+,...,F. gNext, perform a sequential search to find the first structure such that the value of the range member is less than or equal to the input grade.

31.

The median of a set of n measurements is a number such that half the n measurements fall below the median, and half fall above. If the number of measurements n is odd, the median is the middle number when the measurements are arranged in ascending or descending order. If the number of measurements n is even, the median is the average of the two middle measurements when the measurements are arranged in ascending or descending order. Write a program that requests a number n and a set of n measurements as input and then displays the median.

32.

Write a program with two buttons labeled Ascending Order and Descending Order that displays the eight vegetables in V8® in either ascending or descending alphabetic order. The vegetables (tomato, carrot, celery, beet, parsley, lettuce, watercress, and spinach) should be stored in a class-level array.

Solutions to Practice Problems 7.4

1.

The outer loop controls the number of passes, one less than the number of items in the list. The inner loop performs a single pass, and the jth pass consists of n j comparisons.


[Page 377]
2.

First

Last

Middle

0

19

9

10

19

14

10

13

11

12

13

12

13

13

13





An Introduction to Programming Using Visual Basic 2005
Introduction to Programming Using Visual Basic 2005, An (6th Edition)
ISBN: 0130306541
EAN: 2147483647
Year: 2006
Pages: 164

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net