{[['
']]}
']]}
Suppose you have a group of n numbers and would like to determine the
kth largest. This is known as the selection problem. Most students
who have had a programming course or two would have no difficulty writing a
program to solve this problem. There are quite a few "obvious" solutions.
One way to solve this problem would be to read the n numbers into an
array, sort the array in decreasing order by some simple algorithm such as
bubblesort, and then return the element in position k.
A somewhat better algorithm might be to read the first k elements into
an array and sort them (in decreasing order). Next, each remaining element is
read one by one. As a new element arrives, it is ignored if it is smaller than
the kth element in the array. Otherwise, it is placed in its correct spot
in the array, bumping one element out of the array. When the algorithm ends, the
element in the kth position is returned as the answer.
Post a Comment