Analysis of Algorithms : An Active Learning Approach

54 SEARCHING AND SELECTION ALGORITHMS

for j = 2 to N-(i-1) do

if list[j] > largest then

largest = list[j]

largestLocation = j

end if

end for

Swap( list[N-(i-1)], list[largestLocation] )

end for

return largest

What is the complexity of this process? On each pass, we initialize largest

to the first element of the list, and then we compare largest to every other

element. On the first pass, we do N
 1 comparisons. On the second pass, we

doN
 2 comparisons. On the Kth pass, we do N
K comparisons. So, to

find the Kth largest element, we will do

comparisons, which is O(K*N). You should also see that if K is greater than
N/2, it would be faster to look for the N
Kth smallest value. This process
will be reasonably efficient for values of K that are close to either end of the
list, but there is a more efficient way to accomplish this process for values of K
in the middle of the list.
Because we only want the Kth largest value, we don’t really need to know
the exact position for the values that are the largest through the K
1 st largest;
we only need to know that they are larger. If we choose an element of the list,
we can partition the list into two parts—those values that are greater than the
one chosen and those that are less than it. If we rearrange the list so that all of
the larger values are after the chosen value and all of the smaller ones are before
it, the chosen value will wind up in some position P in our list, meaning it is
thePth largest value. To do this partitioning, we will need to compare this value
with all of the others, doing N
1 comparisons. If we are lucky and P = K,
we are done. If K is less than P, we want a larger value and will repeat this pro-
cess on the second partition. If K is greater than P, we want a smaller value and
will use the first partition, but we need to reduce K by the number of values
we have eliminated in the larger partition. This gives the following recursive
algorithm:
KthLargestRecursive( list, start, end, K )
list the list of values

Ni–

i=1

K

∑ NK

KK*()– 1

2

= * –----------------------------