How to sort lists of cards

Introduction

You might have learned that there exist various sorting algorithms, like bubble sort, quick sort, etc. Except in specific situations, like with very large lists (millions of elements) or specific data distributions (a lot of duplicates) the practical differences between the reasonable sorting algorithms are negligible. Best practice is to first use the default sorting implementation of the programming language you are using and only after making sure through benchmarking that this is the bottleneck, consider using something different.

Sorting in python

There are two ways to sort a list. The one modifies the original list in place, the other one makes a copy of the list and sorts that.

In place:

a = [1,5,3,4]
a.sort()
print (a)

[1, 3, 4, 5]

With a copy:

a = [1,5,3,4]
b = sorted(a)
print (a)
print (b)

[1, 5, 3, 4]
[1, 3, 4, 5]

Natural ordering and reversing it.

The sort functions above sort the lists by some sort of natural ordering, defined with the < operator. For numeric values from smaller to larger, strings compare lexicographically. Also sequences like lists and tuples are ordered lexicographically using comparison of corresponding elements, i.e., they are ordered the same as their first unequal element. For example [1,1,2] < [1,2] and [1,2] < [1, 2, 3] are both True. For all details, see https://docs.python.org/3/reference/expressions.html#value-comparisons

Often, you want the reverse of an ordering. This can be done by specifying reverse=True when sorting. For example:

a = [1,5,3,4]
b = sorted(a, reverse=True)
print (b)

[5, 4, 3, 1]

Sorting with a different key

Very often you have to sort lists with object that do not have a natural ordering, or the natural ordering is not what you want. In these case, you have to define the ordering.

How this is done, depends on the programming language. In many languages, like Java, Go, and C++ you would specify a < function to compare two elements.

In Python, however, you need to specify a function that converts elements in your sequence into something that can be compared. For example, if you need to sort a list of cards, ordered by how many points they are worth, you can do:

from schnapsen.deck import Card
from schnapsen.game import SchnapsenTrickScorer

a = [Card.ACE_CLUBS, Card.KING_DIAMONDS, Card.TEN_SPADES, Card.QUEEN_SPADES]
scorer = SchnapsenTrickScorer()

def key_function(c: Card) -> int:
    return scorer.rank_to_points(c.rank)
b = sorted(a, key=key_function)
print(b)

[Card.QUEEN_SPADES, Card.KING_DIAMONDS, Card.TEN_SPADES, Card.ACE_CLUBS]

Because the key functions are often short and only used once, one often writes them using a lambda function, like so:

b = sorted(a, key=lambda c: scorer.rank_to_points(c.rank))

Stable sorting

When using a key function, it is important to know what happens with elements that compare equal. For example, let's imagine we have two queens in the list. Both will have the same number of points, so which one will come first?

There are two common options. The first one is called unstable sorting, which means that there is no guarantee what will happen; sometimes it might be the one, sometimes the other. The second one is stable sorting; the one which was first in the original list will be first in the sorted list. Unstable sorting algorithms can be faster and use less memory (see, e.g. https://stackoverflow.com/q/810951 ), but the difference is not that large and Python's default is a stable sort.

So, if we have two queens, and want to preserve their order, we get the following (using scorer defined above):

a = [Card.ACE_CLUBS, Card.KING_DIAMONDS, Card.TEN_SPADES, Card.QUEEN_SPADES, Card.QUEEN_DIAMONDS, Card.QUEEN_CLUBS]
b = sorted(a, key=lambda c: scorer.rank_to_points(c.rank))
print(b)

[Card.QUEEN_SPADES, Card.QUEEN_DIAMONDS, Card.QUEEN_CLUBS, Card.KING_DIAMONDS, Card.TEN_SPADES, Card.ACE_CLUBS]

Two level sorting

Sometimes, we need to sort on two criteria, first the one, and in case of a tie, the other. This can be achieved thanks to the stable sorting! Let's imagine we sort a list of cards, first by their points, and then if cards have the same number of points, put DIAMONDS before all other suits. What we can do is first sort with the suit condition and then sort using the points (note that we first do the inner condition and then the outer one).

from schnapsen.deck import Suit

a = [Card.ACE_CLUBS, Card.KING_DIAMONDS, Card.TEN_SPADES, Card.QUEEN_SPADES, Card.QUEEN_DIAMONDS, Card.QUEEN_CLUBS]
b1 = sorted(a, key=lambda c: 0 if c.suit == Suit.DIAMONDS else 1 )
print(b1)

[Card.KING_DIAMONDS, Card.QUEEN_DIAMONDS, Card.ACE_CLUBS, Card.TEN_SPADES, Card.QUEEN_SPADES, Card.QUEEN_CLUBS]

b2 = sorted(b1, key=lambda c: scorer.rank_to_points(c.rank))
print(b)

[Card.QUEEN_DIAMONDS, Card.QUEEN_SPADES, Card.QUEEN_CLUBS, Card.KING_DIAMONDS, Card.TEN_SPADES, Card.ACE_CLUBS]

It is possible to do this in one sort operation as well. This would be ever so slightly faster and use less memory, but focus on code readability before trying this.

More efficient multi-level sorting

To do the multi-level sorting more efficiently, you can make use of the natural order of tuples (see above) and a custom key (see above). What you do is return a tuple where each of the components corresponds to one of the sorting levels.

Again, we sort a list of cards, first by their points, and then put DIAMONDS before all other suits. What we can do is use a tuple key, with first the key for the points and then a key for the suit.

def key_function(c: Card) -> int:
    score = scorer.rank_to_points(c.rank)
    suit_key = 0 if c.suit == Suit.DIAMONDS else 1
    return (score, suit_key)

a = [Card.ACE_CLUBS, Card.KING_DIAMONDS, Card.TEN_SPADES, Card.QUEEN_SPADES, Card.QUEEN_DIAMONDS, Card.QUEEN_CLUBS]
b = sorted(a, key=key_function)
print(b)

[Card.QUEEN_DIAMONDS, Card.QUEEN_SPADES, Card.QUEEN_CLUBS, Card.KING_DIAMONDS, Card.TEN_SPADES, Card.ACE_CLUBS]

Which is the same result we obtained above, but with only one sort operation.

Finding the lowest/highest element in a list

To find the highest or lowest in a list, one could first sort the list and then take the first element. However, finding the lowest/highest can be done more efficiently (in $O(n)$ instead of $O(n\log n)$ ) using the min and max functions. These functions also support the key argument, and are stable in the sense that the first highest/lowest will be returned, and other elements which compare equal will be ignored.

To find the card which gives most points, use

a = [Card.ACE_CLUBS, Card.KING_DIAMONDS, Card.TEN_SPADES, Card.QUEEN_SPADES]
b = max(a, key=lambda c: scorer.rank_to_points(c.rank))
print (b)

Card.ACE_CLUBS