Python: Sort

Sort Methods

These methods change the list variable in-place. That is, they only work on a variable, and modifies it.

listVar.reverse()

Reverses the items of listVar in-place.

listVar.sort()

Sort the items of listVar in-place.

listVar.sort(f)

Using predicate function f to sort. f takes 2 args, and return {1, 0, -1}, but any int works. The sign indicates order.

listVar.sort(key=f)

Sort by using f to extract a key for comparison. f is feed a element in the list. Value of f is compared using cmp().

listVar.sort(key=f, reverse=boolean)

Specify ascending or descending.

Sort Function: Return a Copy

sorted(list)

Return a sorted copy of the list. Does not modify original list.

li = [1,9,2,3]

li2 = sorted(li)

print(li)   # [1, 9, 2, 3]
print(li2)  # [1, 2, 3, 9]

Sort Method, Sort In-Place

list.sort()

Sort list in-place. Return None. (The original list is modified.)

li = [1,9,3]

# sort in-place
li.sort()

# the variable is modified
print(li)
# [1, 3, 9]

Sort by Column/Key

You can sort by specifying a optional parameter “key”. This is most useful for sorting a matrix.

# sort a matrix by 2nd column

li = [[2,6],[1,3],[5,4]]

li.sort(key=lambda x:x[1])

print(li)  # [[1, 3], [5, 4], [2, 6]]

Sort and Reverse

Another optional parameter is “reverse”.

# sort a matrix, by 2nd column, reverse order

li = [[2,6],[1,3],[5,4]]

li.sort(key=lambda x:x[1], reverse=True)

print(li);
# prints [[2, 6], [5, 4], [1, 3]]

Sort by An Ordering Function

Here's a more complex example. Suppose you have a list of strings.

You want to sort them by the number embedded in them.

You need to define a ordering function, and pass it to sort. The function should takes two strings, and compare the integer inside the string. Here's the solution:

# sort by custom order

import re

li = [
"my283.jpg",
"my23i.jpg",
"web7-s.jpg",
"fris88large.jpg",
]

# compare number inside string
def myKey (myString):
    return float(re.findall(r"\d+", myString)[0]) # return number part in string

li.sort(key = myKey)

print(li)
# ["web7-s.jpg", "my23i.jpg", "fris88large.jpg", "my283.jpg"]

Here, we defined a function “myKey” to tell sort about the key to use.

Math of Ordering

In general, the function f used to determine the order of any two element must satisfy some constraints:

• f(a,a)==0
• if f(a,b)==0 then f(b,a)==0
• if f(a,b)==0 and f(b,c)==0, then f(a,c)==0.
• if f(a,b)==-1 and f(b,c)==-1, then f(a,c)==-1.
• if f(a,b)==-1, then f(b,a)==1.

If the comparison function does not behave as the above, then it is not consistent. It means that the result ordered list may actually be different depending the order of the original list or how the language happens to implement sort.

The significance of all this is that in real software you may want to sort a list of complex object by a specialized ordering. For example, you may want to sort a list of triangles in 3D space by their orientation. Or, sorting image selections in a photo-editing program. It is in advanced cases like these, understanding the basic math about ordering is important. Otherwise, you might have a inconsistent result yet unable to locate any flaws in your code.

The order-deciding function given by the user is called a “predicate” in computer science. (A predicate function is any function that returns either true or false) And, it is usually defined inline using a pure function construct called “lambda”.

~2006 Thanks to Lasse Vågsæther Karlsen for informing me the existence of the sorted() function in Python 2.4.