Sort-priority In Python With Help Of Closure Function

I read a Python text book which has the following closure function used in combination with sort. This sorting function is supposed to prioritize numbers which belong the special g

Solution 1:

A sort key is a function that generates stand-in values for you to sort. The order imposed after sorting the stand-in values will be imposed on the originals. Sort keys are applied once to each element of the list. So instead of sorting into the order mandated by

[8, 3, 1, 2, 5, 4, 7, 6]

you are sorting into the order mandated by

[helper(8), helper(3), helper(1), helper(2), helper(5), helper(4), helper(7), helper(6)]

helper is called once for each element of the list, effectively as if you did

[helper(x) for x in values]

Now you are sorting into the order mandated by

[(1, 8), (0, 3), (1, 1), (0, 2), (0, 5), (1, 4), (0, 7), (1, 6)]

Making the elements into a tuple allows you to "tag" elements of the set {2, 3, 5, 7} with zeros, which will always sort before an element "tagged" with a one. That's because the "tag", which is the first element of each tuple, is compared first.

When the keys are sorted, the actual values are placed in the same order.

Newer versions of Python don't support comparators at all, unlike C and Java, for example: it's simply unnecessary. A properly constructed key function can do everything a comparator can do, and only needs to be evaluated once per element, instead of multiple times. Of course the keys themselves still need to be compared the same number of times.

Sort keys also allow you to sort lists of elements that don't have a natural sorting (don't support comparison operators like <). With the right key, you can even sort lists containing elements of different types that can't normally be compared to each other.

On a side note, booleans are a special subclass of integers in Python: False == 0 and True == 1. Since these are the tags you're using to split the keys into categories, you can rewrite helper to avoid the conditional:

defhelper(x):
    return (x notin group, x)

Appendix

To help you understand key sorting better, here's an implementation that does effectively the same thing as passing a key to the sort method, but not in-place (so more like the sortedbuilt-in):

def my_sorted(iterable, key):
    iterable = list(iterable)
    elements = [(key, index) for index, key in enumerate(iterable)]
    elements.sort()
    return [iterable[index] for _, index in elements]

This does the following:

1. Convert the input into something that can be indexed (a sequence), since not all iterables can be indexed out of the box.
2. Compute the key of each element, and the index in the original list. This will allow you to extract the elements into the correct order once you've sorted the keys. It also provides an additional layer of stability to the sort. Python's default Timsort is already stable, but any ties among the keys will be broken by the index.
3. Sort the list of keys and indices by key.
4. Extract the element corresponding to each sorted element from the original sequence, and return the result.

Solution 2:

The key parameter in sort() requires a function, and it applies that function to each list element that's being sorted. In your example, each element of values is passed into helper(), which then checks to see if that element is in group. Sort is then comparing the list of tuples, and the tuples with a first element of 0 are always going to come before the tuples with a first element of 1.

Source: https://wiki.python.org/moin/HowTo/Sorting#Key_Functions

Solution 3:

Summary:

Because a function like that, has an argument for the item, btw it's equivalent to lambda x: .. maybe you're more familiar with that, so you're sorting values by that function basically direct helper in sort is equivalent to lambda x: helper(x) maybe more familiar, Btw it's not a tuple it's a set because it contains curly-braces and doesn't contain colons

So to answer your questions one by one:

1) Where is the actual value of x parameter in the helper(x) being passed?

It applies that method to each function and as you know from above, equivalent to lambda x: helper(x).

2) I understand that Python compares 0-to-0 index first, then 1-to-1 index, etc. in the tuple; but not quite sure how the returned tuple being used in comparison in this case.

Well, because you're returning the value in the helper function so that's how it's gonna sort by.