Řazení prvků patří mezi časté operace, které se v programátorské praxi vyskytují. Problematika řazení¹⁾ je velmi důkladně teoreticky zpracována a zkušený programátor by měl být obeznámen alespoň se základními vlastnostmi hlavních řadicích algoritmů a podle okolností správně volit odpovídající řešení.

Naše časové možnosti nám nedovolují zabývat se tímto tématem hlouběji, přejdeme přímo k základním prostředkům pro řazení v jazyce Python. Budeme předpokládat, že úkolem je seřadit seznam prvků podle nějakého kritéria. To je možné pouze v případě, že libovolné dva prvky seznamu lze porovnat (tj. určit, který z nich je větší, případně zda se rovnají). Z předchozích hodin víme, že je možné porovnávat dvě čísla (dokonce i int a float navzájem), ale také dva řetězce či dva seznamy podle lexikografického uspořádání (nikoli však např. číslo s řetězcem).

Objektový typ list (seznam) má pro tento účel metodu sort, která upraví (přeskupí) seznam tak, že jeho prvky utvoří uspořádanou posloupnost.

cisla = [15, 4, 11, 8, -3, 5, 2, 1, 10]
cisla.sort()
cisla          # => [-3, 1, 2, 4, 5, 8, 10, 11, 15]

V jednoduché podobě metoda sort nedostává žádné parametry, pak jsou prvky seznamu uspořádány vzestupně (platí, že následník prvku je vždy větší nebo roven svému předchůdci).

Obecně je pravdou, že neexistuje „nejlepší“ řadicí algoritmus, který je naprosto univerzálně vhodný na všechny oblasti použití. Na druhé straně lze říci, že ve většině běžných případů (např. všechny prvky se nám zároveň vejdou do operační paměti počítače) odvede představená metoda sort svou práci velmi dobře - efektivně a rychle²⁾.

Několik dalších příkladů řazení seznamů.

# shodné prvky se mohou v seznamu opakovat
cisla = [5, 4, 2, 6, 5, 5, 8, 1]
cisla.sort()
cisla          # => [1, 2, 4, 5, 5, 5, 6, 8]
 
# 'int' a 'float' se mohou vyskytovat v seznamu zároveň
cisla = [2.5, -0.21, 1, 0.98, 3, 3.0, 0.21]
cisla.sort()
cisla          # => [-0.21, 0.21, 0.98, 1, 2.5, 3, 3.0]
 
# řazení seznamu řetězců
barvy = ['red', 'white', 'black', 'blue', 'yellow']
barvy.sort()
barvy          # => ['black', 'blue', 'red', 'white', 'yellow']

Ve své základní podobě probíhá řazení metodou sort vzestupně. Pomocí volitelného parametru reverse logického typu je možné pořadí obrátit - seznam je uspořádán v klesajícím (přesněji nerostoucím) pořadí.

cisla.sort(reverse = True)
cisla          # => [3, 3.0, 2.5, 1, 0.98, 0.21, -0.21]
 
barvy.sort(reverse = True)
barvy          # => ['yellow', 'white', 'red', 'blue', 'black']

Metoda sort nemá návratovou hodnotu (resp. vrací None), výsledkem její činnosti je přeuspořádání samotného objektu.

Poměrně často potřebujeme seřadit prvky seznamu podle jiného pravidla než je prosté porovnání hodnoty čísel či lexikografické uspořádání řetězců. K tomuto účelu má metoda sort volitelný parametr key. Pomocí něj se definuje funkce či metoda, která pro každý prvek poskytuje nějakou návratovou hodnotu, a právě na základě výsledků se provádí výsledné řazení.

# seřadíme čísla podle jejich absolutní hodnoty
cisla = [2, -5, 1, -4, 3, -2, 0]
cisla.sort(key = abs)
cisla          # => [0, 1, 2, -2, 3, -4, -5]

V tomto případě je výsledný seznam uspořádán nikoliv podle vlastní hodnoty čísel, nýbrž podle jejich absolutní hodnoty, tj. podle návratové hodnoty funkce abs (-4 je až za 3, protože platí abs(3) < abs(-4)). Novým poznatkem je pro nás i skutečnost, že i funkce či metody lze pomocí jména předávat jako parametry. Další ukázky následují.

# seřazení řetězců podle délky, tj. návratové hodnoty funkce 'len'
barvy.sort(key = len)
barvy          # => ['red', 'blue', 'white', 'black', 'yellow']
 
# seřazení řetězců bez ohledu na velikost písmen
#   na každý prvek se aplikuje řetězcová metoda 'lower', výsledné
#   řetězce jsou pak řazeny normálně lexikograficky
seznam = ['Juk', 'haló', 'KUKU', 'Baf', 'BAF', 'ahoj', 'Nazdar']
seznam.sort(key = str.lower)   # metoda objektu 'str'
seznam         # => ['ahoj', 'Baf', 'BAF', 'haló', 'Juk', 'KUKU', 'Nazdar']
# pro porovnání normálně seřazený seznam
seznam.sort()
seznam         # => ['BAF', 'Baf', 'Juk', 'KUKU', 'Nazdar', 'ahoj', 'haló']
#   volitelné parametry 'key' a 'reverse' je možné použít najednou
seznam.sort(key = str.lower, reverse = True)
seznam         # => ['Nazdar', 'KUKU', 'Juk', 'haló', 'Baf', 'BAF', 'ahoj']

Při použití metody jako řadicího kritéria je nutno pomocí tečkové notace uvést i objektový typ, ke kterému metoda patří. Za povšimnutí stojí také skutečnost, že pořadí prvků při řazení se nezmění, pokud při porovnání návratových hodnot funkce nastane shoda³⁾ (říká se, že řadicí algoritmus je stabilní).

Již dříve jsme hovořili o problematice kódování znaků a řazení řetězců a upozorňovali na složitost implementace řazení podle národních zvyklostí. Nyní si ukážeme, jak správně seřadit seznam řetězců podle pravidel češtiny.

Využijeme k tomu standardní modul locale, který obhospodařuje veškeré národně a místně specifické činnosti (kromě námi použitého porovnávání řetězců také např. formátování číselných, finančních a datových údajů). Po importování modulu je nutné nastavit požadované národní prostředí pomocí setlocale, pro češtinu je předdefinován řetězec cs_CZ. Modul locale poskytuje mimo jiné i funkci strxfrm, která transformuje řetězec do podoby zaručující požadované řazení. Tuto funkci můžeme přímo použít jako parametr key pro řadicí metodu sort či funkci sorted⁴⁾.

ceske_razeni.py

# modul pro nastavení národního prostředí
import locale
locale.setlocale(locale.LC_ALL, "cs_CZ") # čeština, Česko
 
seznam = ['candát', 'šakal', 'čmelák', 'liška', 'srna', 'lín', 'chroust']
# třídění bez nastavení národního prostředí
seznam.sort()
print(seznam)
# třídění podle pravidel češtiny
seznam.sort(key = locale.strxfrm)
print(seznam)

Program poskytl následující výstup, kromě správného pořadí písmen s diakritikou na druhém řádku si povšimněte i správného zařazení ch (z hlediska řazení se jedná o jedno písmeno!).

['candát', 'chroust', 'liška', 'lín', 'srna', 'čmelák', 'šakal']
['candát', 'čmelák', 'chroust', 'lín', 'liška', 'srna', 'šakal']

V dosavadních příkladech jsme použili vestavěné funkce či metody jazyka, nic nám však nebrání použít i vlastní funkci. Taková funkce musí zpracovat prvek předaný pomocí pozičního parametru a výsledek poskytnout jako návratovou hodnotu.

Řekněme, že bychom chtěli seřadit seznam slov podle počtu výskytů písmene a. Napíšeme si funkci pocet_a s jedním řetězcovým parametrem a návratovou hodnotou typu int a s její pomocí již snadno seřadíme zadaný seznam.

razeni.py

def pocet_a(prvek):
    return prvek.count('a')
 
seznam = ['rada', 'klíč', 'klacek', 'abrakadabra', 'tralala']
seznam.sort(key = pocet_a)
print(seznam)

s výsledkem ['klíč', 'klacek', 'rada', 'tralala', 'abrakadabra'].

Pro situace, kdy potřebujeme seřazený seznam položek, ale chceme zachovat zdrojová data v původní podobě, nám Python nabízí funkci sorted. Té předáváme zdrojová data ve formě seznamu (obecněji dokonce data ve formě objektu, jehož položky můžeme postupně procházet - z nám známých datových typů také řetězec) jako poziční parametr, pojmenované parametry reverse a key je možno použít výše popsaným způsobem. Návratovou hodnotou funkce je nově vytvořený seznam, původní data zůstávají nezměněna.

# seřazení čísel při zachování původního seznamu
cisla = [2, -5, 1, -4, 3, -2, 0]
cisla2 = sorted(cisla)
cisla2        # => [-5, -4, -2, 0, 1, 2, 3]
#   vlastní kritérium řazení, sestupné pořadí
cisla3 = sorted(cisla, key = abs, reverse = True)
cisla3        # => [-5, -4, 3, 2, -2, 1, 0]
 
# vytvoření seřazeného seznamu znaků zdrojového řetězce
sorted("Python 3")    # => [' ', '3', 'P', 'h', 'n', 'o', 't', 'y']