Lab 9: Searching for the right sort - Canisius College



Lab 9: Searching for the Right Sort

OBJECTIVES Investigate sorting and searching algorithms and watch them work.

REFERENCES Software needed:

1) a web browser (Internet Explorer or Netscape)

2) applets from the lab website:

a.) Searching

b.) Sorting

c.) Palgo

Textbook reference: Chapter 9

BACKGROUND Chapter 9, “Abstract Data Types and Algorithms,” gets deeper into programming with abstract data types and data structures. Two programming tasks that it focuses on are searching and sorting, illustrating various algorithms for both.

ACTIVITY Searching and sorting are venerable, respected topics in computer

PART 1: science. In fact, volume 3 of Donald Knuth’s famous series of books, The Art of Computer Programming, focuses exclusively on searching and sorting.

You’ll be using several applet to explore searching and sorting. The Palgo applet provides a complete programming language with arrays (called lists). Start the applet, select Example 8 — Sorting, and run the program. Here’s a screenshot:

[pic]

Study the code shown in the screenshot. Can you figure out which of the three sorting algorithms discussed in the textbook was used for this sorting program? Your choices are selection sort (pp. 288-289), bubble sort (pp. 290-291) or quicksort (pp. 291-295).

Notice that the array holding the integers in this program is identified by the variable a. This variable is set to an empty array by the first line:

a = list()

Then the elements are filled in, one by one:

a[0] = 5

The length of the array can be discovered by the length function:

len = length(a)

Unlike some older, better known languages like C, the programming language in Palgo is fairly easy and forgiving, . In C you have to declare the size of an array when you create it. There are some deep reasons why C requires this but Palgo doesn’t — the main reason is that Palgo is interpreted while C is compiled. The difference between these two ways of translating high level code is discussed on pp. 226-228 of the textbook.

Experiment with the Palgo sorting program. As an extra challenge, you might try to encode one of the other sorting or searching algorithms into Palgo language and get it to run (much easier said than done, due to the nature of programming!) If you run Palgo as a standalone application (see page x), you can save your programs in a file on disk.

PART 2: Now we will play with the Sorting applet. Start your browser and open the Sorting applet. The large text area is where you type in a list of numbers. You can load several example datasets by pulling down the menu near the bottom and clicking on Load Example. Then choose a sorting algorithm by pulling on the Sort Choice menu in the middle of the window, then finally Sort by pressing the Sort button.

[pic]

Each of the three algorithms colors the cells slightly differently as they work. The selection sort colors each cell pink as it examines it. If it decides to swap two cells, it briefly colors that cell red. The gray cells at the top represent the already sorted sublist.

Look at several datasets and use the three different sorting algorithms on them, watching them as they work. The text area above the sort button tells the total number of comparisons that the program used while sorting. This can begin to give you a feel for which algorithm is best, and under which conditions it is best.

Of course, there are more than three different sorting algorithms! There is shell sorting, insertion sorting, radix sorting, heap sorting, merge sorting and others. Even with all these choices, quicksort is perhaps used most often in the “real world.” It is found in databases and in the Unix system’s sort utility and many other places.

PART 3: Closely related to sorting is searching, where we are trying to find whether a piece of information (such as a number, a character string, or a picture) resides in a collection. Collections are often, but not always, implemented by arrays. Sometimes collections have so many millions of items in them that trees or even more exotic data structures are needed. Trees are discussed on pp. 300-309 of your textbook and a searching algorithm that is appropriate only for trees is shown in the green box at the bottom of p. 305.

Start the Search applet and press Example 1. This example uses the sequential search algorithm to search for the number 20 in the list. Since 20 is not to be found there, the Search applet will have to go through the maximum amount of work to find out this fact and report to us.

[pic]

The number of comparisons that it made is reported in the text area above the Search button.

Type in some numbers that are found in the list and click on search. This applet intentionally runs slow so you can watch it at work. In real applications, of course, you would want the fastest program you could get, and animating the search would not be necessary.

Experiment with binary versus sequential search. What generalizations can you make about their relative speeds? What additional requirements does binary search make on the dataset?

Imagine what a sequential search algorithm would look like, then compare that to the pseudocode for a binary search on p. 296. What can you say about the relative complexity of the algorithms?

DIRECTIONS Follow these directions.

EXERCISE 1: 1.) Start the Sorting applet.

2.) Make a little table in which you can record the performance of the three algorithms on the four different datasets:

[pic]

3.) Run the applet 12 times and record the numbers that show up in the information text area.

4.) Which algorithm is usually the fastest?

5.) Is any one algorithm always faster than the others?

6.) Are any two algorithms similar?

7.) Did the four datasets cover all the major “cases” you can think of, or are there others? If so, describe them.

EXERCISE 2: 1.) Start the Search applet.

2.) Run both examples and note how many comparisons were made.

3.) Keep the algorithm at binary search. Type in 62 and click the search button. Write down how many tries the program made.

4.) Now type in 79 and rerun the algorithm. Write down how many tries the program made.

5.) What differences between the sequential search algorithm and the binary search algorithm can you make from this comparison?

DELIVERABLES Turn in your answers to the above experiments on a piece of paper.

DEEPER Just like sorting, there are many search algorithms besides

INVESTIGATION sequential and binary searching (and tree searching presented on p. 305). Think about how you search for a name in a telephone book. You don’t need to live in New York City or Los Angeles to realize that nobody in their right mind uses sequential search on the telephone book! But just exactly what do people do? What algorithm do they employ? Is it binary search? Can you describe the algorithm in English, even if it is too hard to write out in code?

Think about searching the telephone book again. What kinds of additional information is present to help humans find names in the phone book? How are phone books organized?

Finally, think about finding information in your school’s library. You probably have a computer system with an on-line catalog but not too long ago, libraries had huge filing cabinets full of 3x5 index cards. (In fact, some folks get downright nostalgic for those drawers of musty-smelling card…) Such indexes now live on (relatively scent-free) computer hard disks.

Think about the steps you would have to go through to find a specific piece of information or a quotation. What indexes would you search? What happens when the index leads you to the book itself? What then? How might all this change in the upcoming years as computerization advances?

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download