Python: Output list = x largest numbers of input list

Question

I am trying to write a function called "k_largest(input,output)" which takes two Python lists of numbers and then fills the output list with the largest numbers of the input list in ascending order, depending on the size of the output list.

The test is:

input = [50, 30, 60, 10, 0, 40]
output = [0, 0, 0]
k_largest(input,output)
print(output)

Answer:

[40, 50, 60]

This is my code: (The merge_sort function is just used to sort the input list into descending order.)

def k_largest(input, output):
    merge_sort(input)
    input = input[:len(output)]
    input = input[::-1]
    output = list(input)
    print (output)

def merge_sort(list):
    count = 0
    for index in range(1, len(list)):
        value = list[index]
        i = index - 1
        while i >= 0:
            if value > list[i]:
                list[i+1] = list[i]
                list[i] = value
                i = i - 1
                count = count + 1
            else:
                break

For some reason my code is just outputting the original output list instead of the new output list.

For example:

[0, 0, 0]

Instead of:

[40, 50, 60]

I'm pretty sure there's a more effective way of doing this as well.

Avoid using `list` as a variable name, as it shadows the built-in method `list()`. — Burhan Khalid, Oct 18 '15 at 06:08
Just use [`heapq.nlargest`](https://docs.python.org/library/heapq.html) — Cristian Ciupitu, Oct 18 '15 at 11:32

AChampion · Accepted Answer · 2015-10-18T06:12:24.230

You are not replacing the values in output, just assigning a new list to the function's output label, so the calling output will always be [0, 0, 0].
You need to use the slice assignment to get an inplace update:

output[:] = input

That way the argument passed in is updated.

If you return the sorted list in ascending ordering then you can take the last len(output) vs the first and reversing, e.g.:

output[:] = input[-len(output):]  # last 3 items

Note: you should not call your argument to merge_sort() list as this clashes with Python's list type.

However, I'm not a great fan of this type of side effect and would rather pass in a length and return a list, e.g.:

def k_largest(input, n):
    return sorted(input)[-n:]

>>> input = [50, 30, 60, 10, 0, 40]
>>> output = k_largest(input, 3)
>>> print(output)
[40, 50, 60]

If you really must assign to output:

def k_largest(input, output):
    output[:] = sorted(input)[-len(output):]

>>> input = [50, 30, 60, 10, 0, 40]
>>> output = [0]*3
>>> k_largest(input, output)
>>> print(output)
[40, 50, 60]

Aaron Brick · Answer 2 · 2015-10-19T15:10:21.407

1

sorted(input)[:len(output)]

the above line of code provides a new reference to a slice of the sorted list.

edited Oct 19 '15 at 15:10

answered Oct 18 '15 at 05:16

Aaron Brick

236
2
11

score 1 · Answer 3 · edited May 23 '17 at 12:25

@Newbie:

To fill the output list with the largest numbers of the input list in ascending order, depending on the size of the output list, you could try

def k_largest(input, output):
    merge_sort(input)
    input = input[:len(output)]
    input = input[::-1]
    output[:len(output)] = input[:len(output)]
    print (output)

The reason your original program displayed [0, 0, 0] instead of [40, 50, 60] has to do with the way objects are passed in python and the way mutable objects are handled in the called functions. Here's a nice explanation on that https://stackoverflow.com/a/986145/1709397

To be more brief, by reassigning the argument output in the function k_largest(...) with the below statement, we caused it to point to a new location in memory.

def k_largest(input, output):
    ...
    output = list(input)
    ...

Therefore, the reference to the original list is lost.

Python: Output list = x largest numbers of input list

3 Answers3