algorithm of determines the two largest of a series

Question

i am trying to figure a algorithm problem that determines the two largest number of the a series of random 10 numbers. Thanks to your help.

Answer 1

Just go through the list and keep track of the two largest numbers, that is have two variables that are the the two largest elements so far while going through.

Answer 2

list = [random, random, random, ..., random]
largest := (list[0] > list[1]) ? list[0] : list[1]
secondlargest := (list[0] <= list[1]) ? list[0] : list[1]
for each num in list:
    if num >= largest:
        secondlargest := largest
        largest := num
    elseif num >= secondlargest:
        secondlargest := num
return {largest, secondlargest}

You aren't going to be able to avoid iterating across the entire list because it is not sorted, and therefore you are going to have to search in $O(n)$ time. If the list is sorted, it becomes pretty much a non-problem, but there is no sense in sorting it if all you want is the two largest (if you have to do other things it might be worth it though)

Answer 3

What you are looking for can be solved in $O(n)$.

This is called finding the k-th order statistic.The Wikipedia entry of Selection algorithm provides some insight.But probably a better discussion is presented in Chapter 9, Medians and Other statistics from Introduction to Algorithms, 2nd Ed.

Here is a well described randomized $O(n)$ approach : QuickSelect.

Answer 4

It might be worth noting that the naive way to find the $k$ largest elements requires $O(nk)$ operations, since updating the list of $k$ largest elements could take $O(k)$ operations. However, if these are stored in a heap then we get the better complexity $O(n \log k)$; this method is practical (i.e. actually outperforms the naive algorithm) for moderately sized $k$.

Edit: Debanjan's method shows how to solve this using $O(n + k\log k)$ operations, or $O(n)$ if we're not interested in the relative order of the $k$ largest elements. First you find the $k$th largest element using the classical $O(n)$ algorithm, and then you collect all elements at least as large as it is; if required, you then sort them.