How to find k biggest numbers from a list of n numbers assuming n > k

Question

I am looking for some code in Python which could return k largest numbers from an unsorted list of n numbers. First I thought to do this by sorting the list first, but this might turn out to be very bulky.

For example the list from which I want to find k largest number be list1

> list1 = [0.5, 0.7, 0.3, 0.3, 0.3, 0.4, 0.5]

Here n = 7 and if k = 3, that is if I want to find 3 largest numbers from a list of 7 numbers then output should be 0.5, 0.7, 0.5

How can this be done?

Answer 1

Python has all batteries included - use heapq module :)

from heapq import nlargest

data = [0.5, 0.7, 0.3, 0.3, 0.3, 0.4, 0.5]
print nlargest(3, data)

it's also faster than sorting the whole array, because it's using partial heapsort

Answer 2

It can be done like this:

>>> list1
[0.5, 0.7, 0.3, 0.3, 0.3, 0.4, 0.5]
>>> list2 = list1[:] #make a copy of list1
>>> k = 3
>>> result = []
>>> for i in range(k):
        result.append(max(list2)) #append largest element to list of results
        list2.remove(max(list2)) # remove largest element from old list
>>> result
[0.7, 0.5, 0.5]
>>> 

Answer 3

Assuming you don't want to modify list1, you make a sorted copy:

In [1]: list1 = [0.5, 0.7, 0.3, 0.3, 0.3, 0.4, 0.5]

In [2]: list2 = sorted(list1)

In [3]: list2
Out[3]: [0.3, 0.3, 0.3, 0.4, 0.5, 0.5, 0.7]

In list2, the largest numbers are the last numbers, so we'll use slicing:

In [4]: list2[-3:]
Out[4]: [0.5, 0.5, 0.7]

The links I've added point to Pythons documentation. As a beginner, you should start with having a look at the tutorial. After that, the library reference is what you'll be needing most, because the large standard library is one of the things that makes python so nice.