Why does the same key function produce different results for sorted vs list.sort?

user_17375517 0
Viewed 66

My mission is to sort the list by the frequency of numbers included in it. If a few numbers have an equal frequency - they should be sorted according to their natural order.
For example: [5, 2, 4, 1, 1, 1, 3] ==> [1, 1, 1, 2, 3, 4, 5] During the process of solving the problem, I wrote a function as follow:

lista = [3, 4, 11, 13, 11, 4, 4, 7, 3]
def func1(numbers: list):
    numbers.sort(key=lambda x:(-numbers.count(x), x))
    return numbers
    
result = func1(lista)
print(result)

but the result is [3, 3, 4, 4, 4, 7, 11, 11, 13], and then I wrote a function very similar to that

lista = [3, 4, 11, 13, 11, 4, 4, 7, 3]
def func2(numbers: list):
    return sorted(numbers,key=lambda x:(-numbers.count(x), x))

result = func2(lista)
print(result)

the result is [4, 4, 4, 3, 3, 11, 11, 7, 13], which is what I wanted My question is: what's different between list.sort function and sorted function

it is just a few part of my whole homework, please ignore the time complexity of my algorithm.

python
2 Answers

Because list.sort is an in-place algorithm, the content of the list during its .sort is arbitrary – an algorithm might have the list partially sorted, keep sorted items independently, or even behave differently depending on the "unsortedness". As a result, a key accessing a list during its .sort is not guaranteed to work as expected.

In specific, CPython makes the list appear empty during its .sort:

sort(*, key=None, reverse=False)

CPython implementation detail: While a list is being sorted, the effect of attempting to mutate, or even inspect, the list is undefined. The C implementation of Python makes the list appear empty for the duration, and raises ValueError if it can detect that the list has been mutated during a sort.

In contrast, sorted guarantees to produce a new list, leaving the old list unmodified and consistent in appearance during sorting.

You can inspect this behaviour by observing the key before using it:

def observe(arg, *hint):
    """Helper to inspect a value during its usage"""
    print(repr(arg), *hint)
    return arg

numbers = [1, 2, 1]
numbers.sort(key=lambda x: observe(numbers.count(x), "is the key for", x))
# 0 is the key for 1
# 0 is the key for 2
# 0 is the key for 1
sorted(numbers, key=lambda x: observe(numbers.count(x), "is the key for", x))
# 2 is the key for 1
# 1 is the key for 2
# 2 is the key for 1

Using the key function key=lambda x: (-numbers.count(x), x) in .sort means the key is of the form (0, x) – since the first key-part 0 is always equal, items are sorted by the second key-part, i.e. their value. This is equivalent to the standard sort key.

user_53499160

To answer your question about the difference between list.sort() and sorted(list):

They both sort the list you want. But list.sort() changes the original list object (changes the indices) while sorted(list) doesn't effect list itself but. I guess you'd want to create another object from the sorted() function if you didn't want to change the original list. For example, list2 = sorted(list)

user_149820890
Related