SIBT COMP 125

Week 8 Tutorial Exercises

  1. Suppose we have a declaration 
	my_array : ARRAY[STRING]

The following code fragment puts some strings in the array 

	!!my_array.make(1,8)
	my_array.put("cat", 1)
	my_array.put("dinosaur", 2)
	my_array.put("caterpillar", 3)
	my_array.put("aardvark", 4)
	my_array.put("elephant", 5)
	my_array.put("bonobo", 6)
	my_array.put("baboon", 7)
	my_array.put("cayman", 8)

Sort this array into lexicographic order using selection sort. How many comparisions do you need to make ? Now sort it with bubble sort. Which sorting method uses the least number of comparisons and will this always be the case?
  1. Once the above array is sorted, use a binary search to search for "caterpillar" and "alligator". Compare the number of comparisons needed for binary search compared to linear search to find the proposed items in this array. Which searching method is better for this array? Does this apply to all arrays?
  2. Consider the following array of integers (the top row is the index, and the bottom row the value in that location):

Value

1

2

2

3

3

4

 
4
 
5
 
6
 
6

Index

1

2

3

4

5

6

7

8

9

10

Perform a linear search for 2 and then for 3. Which 2 and which 3 do you find ?

Perform a binary search for 2 and then for 3. Which 2 and which 3 do you find ?

Can you think of a way to overcome this problem?
  1. Consider an Eiffel class STUDENT, which has features

Modify the SELECTION_SORT code given in lectures so that it sorts an ARRAY[STUDENT] into order of ascending age. The feature age is called the key of the sort.