Sortowanie w Pythonie

WPROWADZENIE

Opis sortowania w Pythonie można znaleźć w Sorting HOWTO w dokumentacji Pythona.

Python posiada wbudowaną funkcję sorted(), która z obiektu iterowalnego tworzy nową listę posortowaną.

Listy mają wbudowaną metodę do stabilnego sortowania elementów IN PLACE. Stosowany algorytm nosi nazwę timsort, a stworzył go Tim Peters w roku 2002 [Wikipedia]. Jest to algorytm hybrydowy, bazujący na merge sort i insertion sort. Jest też nazywany algorytmem adaptacyjnym. Algorytm timsort jest standardowym algorytmem sortowania w Pythonie od wersji 2.3. Stosowany jest także do sortowania macierzy w Java SE 7 i na platformie Android.

# Jeżeli L to lista, to mamy wywołanie postaci
# L.sort(cmp=None, key=None, reverse=False)   # Py2
# L.sort(/, *, key=None, reverse=False)   # Py3, keywords only

string_list.sort()   # sortowanie listy napisów (duże litery najpierw)

# Potrzebujemy case-insensitive sort.
# Stary sposób - określamy funkcję porównującą dwa obiekty.

string_list.sort(cmp=lambda x, y: cmp(x.lower(), y.lower()))

# Nowy sposób (Py2.4) - podajemy klucz, czyli jakby sposób 
# patrzenia na obiekt. Nazwa "str" występuje jako nazwa klasy.
# Sortowanie jest stabilne.

string_list.sort(key=str.lower)

# Sortowanie pod względem długości napisów, malejąco.

string_list.sort(key=len, reverse=True)

# Sortowanie obiektów względem atrybutów.

student_list.sort(key=lambda student: student.grade)
import operator
student_list.sort(key=operator.attrgetter("grade"))

# Sortowanie listy krotek względem pewnej pozycji.

pair_list.sort(key=lambda pair: pair[1])

import operator
pair_list.sort(key=operator.itemgetter(1))

# Sortowanie listy elementów L na bazie wartości ze słownika D.
sorted(L, key=D.get)

# Transforming a comparison function to a key function.
from functools import cmp_to_key   # Py3.2+

alist.sort(key=cmp_to_key(cmp_function))
sorted(iterable, key=cmp_to_key(locale.strcoll))  # locale-aware sort order

W bardziej złożonych sytuacjach można korzystać ze schematu DSU (Decorate, Sort, Undecorate) [Receptury].

ŁĄCZENIE SEKWENCJI POSORTOWANYCH

Istnieje ładne rozwiązanie w Recepturach (19.14, s. 737). Metoda sort() potrafi skorzystać z faktu, że podsekwencje są posortowane. Z drugiej strony, ta metoda działa ogólnie nawet dla nieposortowanych podsekwencji.

# Sortowanie przy założeniu, że sekwencje mieszczą się w pamięci.
# Usage: res = smallmerge(seq1, seq2, seq3)
def smallmerge(*subsequences):
    result = []
    for seq in subsequences:
        result.extend(seq)
    result.sort()
    return result

Jeżeli sekwencje są duże (nie mieszczą się w pamięci), to proponowane rozwiązanie korzysta z generatorów i sterty.

SORTOWANIE OBIEKTÓW WG ATRYBUTÓW

from operator import attrgetter

class Person:

    def __init__(self, name, money=0):
        self.name = name
        self.money = money

    def __repr__(self):
        return "Person({0!r}, {1})".format(self.name, self.money)

persons = []
persons.append(Person("Adam", 50))
persons.append(Person("Edek", 10))
persons.append(Person("Lolek", 20))
persons.append(Person("Bolek", 10))

# Sortowanie wg nazwiska.
persons.sort(key=lambda x: x.name)   # atrybut zaszyty na stałe
persons.sort(key=lambda x: getattr(x, "name"))   # atrybut można przekazać do sortowania
persons.sort(key=attrgetter("name"))
# [Person('Adam', 50), Person('Bolek', 10), Person('Edek', 10), Person('Lolek', 20)]

# Sortowanie wg zarobków.
persons.sort(key=lambda x: x.money)
persons.sort(key=lambda x: getattr(x, "money"))
persons.sort(key=attrgetter("money"))
# [Person('Edek', 10), Person('Bolek', 10), Person('Lolek', 20), Person('Adam', 50)]

# Sortowanie wg zarobków, potem nazwiska.
persons.sort(key=lambda x: (x.money, x.name))
persons.sort(key=lambda x: (getattr(x, "money"), getattr(x, "name")))
persons.sort(key=attrgetter("money", "name"))
# Zwraca krotkę (person.money, person.name).
# [Person('Bolek', 10), Person('Edek', 10), Person('Lolek', 20), Person('Adam', 50)]

WZORZEC DSU

Jeżeli w Pythonie musimy posortować dane, to najlepiej znaleźć sposób na wykorzystanie wbudowanej w listy Pythona metody sort(). Często stosowanym rozwiązaniem jest implementacja wzorca DSU (Decorate, Sort, Undecorate; dekoruj-sortuj-usuń dekorację), opisanego w [Receptury]. Wzorzec opiera się na tym, że w Pythonie sekwencje są porównywane leksykograficznie.

# Wzorzec DSU na przykładzie sortowania stringów
# bez uwzględniania wielkości liter.
def case_insensitive_sort(string_list):
    alist = [(x.lower(), i, x) for (i, x) in enumerate(string_list)]  # dekoruj
    # Użycie 'i' daje sortowanie stabilne, a także pozwala sortować elementy,
    # które nie mogą być sortowane bezpośrednio, np. liczby zespolone.
    alist.sort()                                   # sortuj
    #return [t[2] for t in alist]          # usuń dekorację
    return [x for (low, i, x) in alist]   # usuń dekorację