Řazení prvků patří mezi časté operace, které se v programátorské praxi vyskytují. Problematika řazení1) 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 rychle2).
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 shoda3) (ří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 sorted4).
# 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.
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']