Analysis of Algorithms : An Active Learning Approach

2.4 PROGRAMMING EXERCISE 55

start the index of the first value to consider
end the value of the last value to consider
K the element of this list that we want.

if start < end then
Partition( list, start, end, middle )
if middle = K then
return list[middle]
else
if K < middle then
return KthLargestRecursive( list, middle+1, end, K )
else
return KthLargestRecursive( list, start, middle-1, K-middle )
end if
end if
end if

If we assume that on average the partition process will divide the list into two

roughly equal halves, we will do about N + N/2 + N/4 + N/8 + ... + 1 com-

parisons, which is about 2N comparisons. So, this process is linear and indepen-

dent of K. We will see the partitioning process in more detail when we discuss

quicksort in Chapter 3 and will do a more detailed analysis of it at that time.

2.3.1

1. Given five distinct values, the median would be the value in the third posi-
   tion if they were sorted. We will see in Chapter 3 that sorting a list of five
   elements would take seven comparisons. Prove that the median can be
   found more efficiently, namely, with no more than six comparisons.


2. The algorithms in this section can also be used to find the median of a list
   by looking for the N/2 largest element. Show that the worst case for this
   choice will take O(N^2 ) time.

2.4 Programming Exercise

1. Create a function based on sequential search and a program that will test it.
   Use method 3 of Appendix C to generate a list of random numbers in the
   range of 1 to N that you can use for your search, where N could be any
   number between 100 and 1000. Your program should have a global counter,
   which should be initialized to zero at the beginning of the program and

■2.3.1 EXERCISES