- Velmi častá operace v mnoha různorodých algoritmech
- Slouží především pro usnadnění následného vyhledávání
- Používá se nejen v programování, ale i v běžném životě (často se setkáváme s abecedním pořadím, např. slova v rejstříku knihy, které usnadní nalezení požadovaného výrazu)
### Základní pojmy
- Pro řazení se v angličtině používá slovo „sort“
- Toto slovo má však dva odlišné významy
- Řazení – činnost, kdy přeskupíme prvky posloupnosti (nejčastěji uložené v poli) tak, aby mezi sousedními prvky platily vztahy „předchůdce-následník“ či „menší-větší“
- Např. seřadíme pole čísel podle velikosti od nejmenšího čísla k největšímu nebo seřadíme studenty podle příjmení od A do Z
- V předmětu KIV/PPA1 a navazujících předmětech budeme důsledně používat slovo „řazení“
- Třídění – činnost, kdy prvky z určité skupiny (množiny) rozdělujeme do podskupin podle nějaké společné vlastnosti
- Např. roztřídíme celá čísla na sudá a lichá V českém překladu se občas slovo **„třídění“ používá ve významu řazení => NEPOUŽÍVAT**!
- Klíč
- Řadit je možné prvky primitivních datových typů nebo instance
- Pokud řadíme instance, které mají obecně více atributů, pak typicky řadíme podle jednoho nebo několika z nich
- Atribut, podle kterého řadíme, se nazývá klíč
- Protože se řazení používá velmi často, existuje množství rozmanitých algoritmů, které se navzájem liší některými svými vlastnostmi, zejména svou rychlostí a složitostí implementace
#### Vlastnosti algoritmů řazení
- Směr řazení
- Řazení vzestupně
- Předchozí prvek je menší nebo roven následujícímu prvku
- Např. 1, 2, 3, 3, 3, 4, 6, 9, 9
- Častější směr řazení
- Řazení sestupně
- Předchozí prvek je větší nebo roven následujícímu prvku
- Např. 9, 9, 6, 4, 3, 3, 3, 2, 1
- Pokud nebude explicitně uvedeno jinak, budeme ve zbylém textu uvažovat řazení vzestupně
- Umístění řazených prvků
- **vnitřní řazení**
- **Všechny prvky**, které chceme seřadit, **jsou uloženy v jeden okamžik v operační paměti**
- Ve zbylém textu budeme **uvažovat pouze vnitřní řazení**
- Paměti je „dost“ – lze bez problémů řadit desítky milionů prvků
- **Vnější řazení**
- Řazených prvků je **extrémní množství** a **všechny najednou se do operační paměti nevejdou**
- Prvky jsou uloženy v jednom či více souborech nebo v databázi na vnější paměti (např. na pevném disku)
- **V jeden okamžik je v operační paměti pouze část prvků**
- Stabilita
- Stabilní řazení
- **Řazení je stabilní**, **pokud relativní pořadí prvků se stejnou hodnotou klíče zůstává v seřazeném poli** (posloupnosti) **stejné jako v původním poli** (posloupnosti)
- Např. pokud budu **řadit pole osob s atributy jméno a příjmení podle příjmení**, pořadí osob se stejným příjmením zůstane zachované
- Neseřazené osoby: Jana Volná, Tomáš Marný, Petr Dobrý, Martin Marný, Lenka Malá, Jitka Volná
- Seřazené osoby: Petr Dobrý, Lenka Malá, Tomáš Marný, Martin Marný, Jana Volná, Jitka Volná
- Nestabilní řazení
- Řazení je nestabilní, pokud se relativní pořadí prvků se stejnou hodnotou klíče může po seřazení pole změnit
- Např. pokud budu řadit pole osob s atributy jméno a příjmení podle příjmení, pořadí osob se stejným příjmením nemusí zůstat zachované
- Neseřazené osoby: Jana Volná, Tomáš Marný, Petr Dobrý, Martin Marný, Lenka Malá, Jitka Volná
- Seřazené osoby: Petr Dobrý, Lenka Malá, Tomáš Marný, Martin Marný, Jitka Volná, Jana Volná
- Má význam pouze u řazení objektů
- Pokud řadíme pole základních datových typů, vzájemná poloha dvou stejných prvků není důležitá
- Protože prvky stejné hodnoty stejně nemůžeme rozlišit
- „Je jedno, která trojka bude první a která druhá“
- Objekty se mohou shodovat v klíči, podle kterého jsme řadili, ale můžou se lišit (a často liší) v hodnotách dalších atributů
- Jejich pořadí může mít význam
- Složitost
- Vlastnost každého algoritmu (nejen algoritmu řazení)
- Dá se použít pro zhodnocení „jak rychlý“ daný algoritmus je nebo „kolik paměti“ daný algoritmus potřebuje
- Udává, jak roste časová (nebo paměťová) náročnost algoritmu v závislosti na velikosti vstupu
- V případě řadících algoritmů je velikost vstupu počet řazených prvků
- Podrobně viz předmět KIV/PPA2
### Základní algoritmy řazení
- U všech příkladů budeme předpokládat, že posloupnost prvků, kterou chceme seřadit, je uložená v poli
- Všechny zmíněné algoritmy procházejí pole, přičemž alespoň část pole se prochází opakovaně
- Pro průchod polem jsou využity dva vnořené cykly – typicky cykly for, nebo kombinace cyklů for a while
- Základní operace, které se provádějí v běžných algoritmech řazení, je porovnání prvků a prohození prvků
- Postupným prohazováním dvojic prvků na základě porovnání jejich hodnoty se z neseřazené posloupnosti uložené v poli stane seřazená posloupnost
- **Základní algoritmy řazení**
- Jsou **jednoduché na implementaci** (a tedy i na pochopení jejich principu)
- Všechny mají **časovou složitost Ο(n²)**
- Udává, jak roste čas potřebný pro seřazení posloupnosti prvků v závislosti na počtu prvků n (v nejhorším případě)
- Pokud bude algoritmus potřebovat čas t pro seřazení n prvků, bude pro seřazení 2n prvků potřebovat čas 4t
- Čas roste kvadraticky v závislosti na počtu prvků n
- **Pokročilé algoritmy řazení**
- Jsou složitější na implementaci a pochopení
- Mají **nižší časovou složitost (typicky Ο(nlog2n)**)
- Podrobně viz předmět KIV/PPA2
#### Řazení výběrem (selection sort)
- Též řazení výběrem mezního prvku, řazení s přímým výběrem
- Princip řešení
- V celém poli nalezneme index prvku s nejnižší hodnotou
- Vyměníme nalezený prvek s prvním prvkem pole (na indexu 0)
- V poli vyjma prvního prvku nalezneme index prvku s nejnižší hodnotou
- Vyměníme nalezený prvek s druhým prvkem pole (na indexu 1)
- Pokračujeme stejným způsobem pro další prvky, dokud nedosáhneme konce pole
- Vlastnosti **řazení výběrem**
- Řazení **je nestabilní**
- **Složitost Ο(n²)**
#### Řazení vkládáním (insertion sort)
- Princip řešení
- Pole máme rozdělené na seřazenou (na začátku jeden prvek) a neseřazenou část (na začátku všechny prvky kromě prvního (na indexu 0))
- Vezme se první prvek z neseřazené části a vloží se na správné místo do seřazené části
- Prvky v seřazené části větší než zařazovaný prvek se posunou o jedno místo doprava => seřazená část se zvětší o jeden prvek
- Opakuji, dokud není pole celé seřazené
- Vlastnosti **řazení vkládáním**
- Řazení **je stabilní**
- **Složitost Ο(n²)**
#### Řazení záměnou (bubble sort)
- Též bublinkové řazení
- Princip řešení
- Porovnáváme vždy dva sousední prvky, začínáme odzadu
- Pokud jsou prvky v nesprávném pořadí (prvek s nižším indexem je větší), prohodíme je
- Porovnávání a prohazování opakujeme, dokud nedojdeme na začátek pole
- Tím se nejmenší prvek dostane na začátek pole („vybublá nahoru“)
- V průběhu vybublání se i ostatní prvky částečně řadí
- Celý postup opakujeme znovu, ale pouze do druhého prvku pole
- Tím vybublá nahoru druhý nejmenší prvek
- Opakujeme pro třetí nejmenší prvek, atd.
- Předčasné ukončení
- Pokud nedojde při běhu vnitřního cyklu k žádné výměně, je pole seřazené a mohu skončit
- **Všechny** tři zmíněné algoritmy mají stejnou **složitost Ο(n²)**
- To neznamená, že jsou **všechny stejně efektivní**, pouze, že **doba řazení roste stejným tempem** (s druhou mocninou počtu řazených prvků)
- Všechny algoritmy řazení provádějí převážně **dvě základní operace**
- **Porovnání** – typicky porovnání dvou prvků
- **Přiřazení** – typicky při prohození dvou prvků (celkem tři přiřazení na jedno prohození)
- Různé řadící algoritmy provedou různý počet porovnání a přiřazení pro stejnou neseřazenou posloupnost
- Podle počtu provedených porovnání a přiřazení lze algoritmy porovnat
- Do algoritmů se přidají dva čítače
- Jeden pro počet porovnání a druhý pro počet přiřazení
- Inkrementují se „ručně“ (tj. je nutné inkrementaci ručně přidat do kódu) při každém provedeném porovnání/přiřazení
- **Základní algoritmy** řazení jsou **efektivní pro malé posloupnosti** (cca několik desítek prvků)
- Pro **větší množství prvků** se používají **algoritmy se složitostí Ο(nlog²n)**, které jsou typicky **obsažené v knihovních metodách většiny běžných programovacích jazyků**
### Řazení pole řetězců (lexikografické řazení)
- **Řazení řetězců funguje stejně** jako řazení základních datových typů **s výjimkou porovnání**
- Pro porovnání dvou prvků nelze použít operátory „```<```“ a „```>```“
- Je potřeba použít metodu instance třídy ```String compareTo()```, která vrací 0, kladnou či zápornou hodnotu podle pořadí porovnávaných řetězců v abecedě
- 0 – řetězce jsou stejné (včetně velikosti písmen)
- **Záporná hodnota** – řetězec, nad kterým je metoda volaná, je „menší“ než řetězec v parametru metody
- **Kladná hodnota** – řetězec, nad kterým je metoda volaná, je „větší“ než řetězec v parametru metody
- POZOR! – Kladné a záporné hodnoty jsou obecně různá kladná a záporná čísla v závislosti na obsahu řetězců – není to jen -1 a 1
#### Problémy s lexikografickým řazením
- Uspořádání podle abecedy však může mít neočekávané důsledky, typicky při řazení názvů souborů (což je nejčastěji podle názvu)
- Pokud seřadíme čísla ```1, 40, 10, 3, 17, 4```, očekáváme výsledek ```1, 3, 4, 10, 17, 40```
- Pokud ale budeme řadit řetězce (názvy souborů) ```"1.txt", "40.txt", "10.txt", "3.txt", "17.txt", "4.txt"```, dostaneme výsledek ```"1.txt", "10.txt", "17.txt", "3.txt", "4.txt", "40.txt"```
- Toto seřazení je **důsledkem porovnání řetězců**
- Běžné porovnávání řetězců implementované i v metodě ```compareTo()``` probíhá postupně podle jednotlivých znaků od začátku řetězce
- Pokud se řetězce shodují v prvním znaku, porovnají se podle druhého znaku atd.
- Jednotlivé znaky se porovnávají podle jejich hodnot
- Jakmile se narazí na znak, který není shodný, hodnota tohoto znaku určí výsledek porovnání řetězců
- Např. při porovnání řetězců ```"Jana"``` a ```"Janicka"``` rozhodnou až znaky ```'a'``` a ```'i'``` na indexu 3 protože ```'a'``` má nižší hodnotu než ```'i'```, „menší“ (tj. blíže začátku abecedy) je řetězec ```"Jana"```
- Pokud je jeden řetězec předponou druhého, je „menší“ ten kratší řetězec (např. ```"Jan"``` je „menší“ než ```"Jana"```)
- Pokud se porovná řetězec ```"10.txt"``` a ```"3.txt"```, tak hned první znaky (na indexu 0) jsou rozdílné – ```'1'``` a ```'3'```
- Protože ```'1'``` je menší než ```'3'```, je řetězec ```"10.txt"``` „menší“ než řetězec ```"3.txt"```, i když číslo 3 je menší než 10
- Řešení –**doplnit nevýznamové nuly**, které jsou však z hlediska lexikografického řazení významové => místo ```"3.txt"``` použít ```"03.txt"```
### Řazení pole objektů
- Pole objektů lze řadit **stejnými algoritmy** jako pole základních datových typů
- **Je** ale **nutné určit**, **podle čeho se mají jednotlivé instance porovnávat** (tj. **určit, co bude klíčem**)
- Podle jednoho atributu
- Podle více atributů (víceúrovňové řazení)
#### Řazení podle jednoho atributu
- Jediný rozdíl oproti řazení pole základních datových typů je, že porovnáváme hodnoty atributů, nikoliv samotné instance
- Pokud je atribut základního datového typu, použijeme přímo operátory porovnání „```<```“ a „```>```“
- Pokud je atribut referenční proměnná na instanci jiné třídy, musíme použít porovnání definované pro danou třídu
- Např. pro třídu ```String``` je to metoda ```compareTo()```
- Poměrně často se může stát, že chceme řadit pole objektů podle více atributů
- Např. osoby podle příjmení a následně podle jména
- Osoby se tedy seřadí podle příjmení, a pokud mají stejné příjmení, seřadí se ještě podle jména
- Je možné udělat v řazení komplexnější podmínku pro prohození prvků obsahující všechny atributy, podle kterých chceme řadit
- Tento postup podstatně znepřehledňuje samotné řazení, zvláště pokud je atributů, podle kterých řadíme, větší množství
- Je vhodnější udělat metodu pro porovnání dvou instancí stejné třídy, která bude vracet hodnoty indikující, která instance je „větší“
- Tato metoda může obsahovat i poměrně složitou podmínku skládající se z porovnání několika atributů
- Díky umístění v metodě instance nebude znepřehledňovat kód řazení
- Metodu můžeme po vzoru třídy ```String``` nazvat ```compareTo()``` a může vracet hodnoty ```0```, ```1``` a ```-1```
- Metoda ```compareTo()``` se využívá i při řazení objektů knihovní metodou řazení
- Metoda ```compareTo()``` se může využít i při řazení podle jediného atributu
#### Víceúrovňové řazení provedené postupně (nepoužívat)
- Další možnost seřazení pole objektů podle více atributů je seřadit ho nejprve podle jednoho atributu a následně podle dalšího
- Je potřeba použít stabilní algoritmus řazení
- Nejprve se pole seřadí podle nejméně důležitého atributu (u osoby podle jména)
- Následně se pole seřadí podle více důležitého atributu (u osoby podle příjmení)
- Protože pořadí prvků se stejným klíčem zůstává při použití stabilního řazení nezměněno, seřazení podle méně důležitého atributu (jména) zůstane zachováno (pro osoby se stejným příjmením)
- Tento postup vyžaduje zopakovat řazení dvakrát a je proto rozumné ho nevyužívat, pokud není nezbytně nutno
- Pokud však není možné řadit podle více atributů najednou (např. v GUI MS Access), tento postup se může hodit
### Metody řazení v Java Core API
- V **naprosté většině případů není důvod si programovat algoritmus řazení**– využijí se **knihovní metody pro řazení** z třídy ```Arrays``` (nebo ```Collections```) z balíku ```java.util```
- Pro pole základních datových typů i pole objektů se používají metody ```Arrays.sort(pole)``` a ```Arrays.sort(pole, indexOd, indexDo)```
- Metody jsou překryté pro pole všech základních datových typů a pole objektů
- Metoda s indexy řadí pouze část pole od indexu ```indexOd``` (včetně) do indexu ```indexDo``` (vyjma)
#### Řazení polí základních datových typů metodou z Java Core API
- Řazení pole základních datových typů **nevyžaduje žádnou speciální úpravu**, **pouze se zavolá metoda řazení**
- Metody ```sort()``` pro pole základních datových typů obsahují **algoritmus quick sort**
- Je **velmi rychlý**
- Má **složitost Ο(nlog²n)** (v průměrném případě)
- **Není stabilní** – u základních datových typů nepodstatné
- Viz předmět KIV/PPA2
#### Řazení polí objektů metodou z Java Core API
- Aby bylo možné **řadit pole objektů** knihovními metodami řazení, **je potřeba, aby třída implementovala rozhraní** ```Comparable<Třída>```
- Mnoho knihovních tříd to dělá, a dají se tak řadit knihovními metodami – např. ```String```
- Podrobnosti viz předměty KIV/PPA2 a KIV/OOP
- Existuje i alternativní možnost, umožňující řadit podle různých kritérií podle toho, které řazení aktuálně potřebujeme
- Je potřeba, aby třída měla rozšířenou hlavičku
- ```public class Třída implements Comparable<Třída>```
- Je potřeba, aby třída obsahovala metodu pro porovnání dvou instancí třídy
- ```public int compareTo(Třída třída)```
- Tato metoda musí vracet zápornou hodnotu, pokud je instance, nad kterou se metoda volá, „menší“ než instance v parametru metody, kladnou hodnotu, pokud je „větší“, a nula, pokud jsou obě instance stejné
- Podle čeho se instance porovnávají, **záleží na těle metody** ```compareTo()```, může to být podle jednoho či více atributů
### Kopie pole
- Protože při knihovním řazení metodami ```Arrays.sort()``` dojde přímo k seřazení zadaného pole, může se hodit pole před řazením zkopírovat, abychom měli uloženou seřazenou i neseřazenou posloupnost
- Pole lze překopírovat ručně
- Vytvořit nové pole stejného typu o stejné velikosti jako původní pole
- V cyklu ```for``` projít původní pole a do prvků nového pole přiřadit odpovídající prvky původního pole
- **Pole lze překopírovat využitím knihovní metody** ```Arrays.copyOf(pole, nováDélkaPole)```
- **Metoda je rychlejší** než ruční kopírování
- Metoda umožňuje **pole** také **zkrátit** nebo **prodloužit** (**při zadání jiné délky** než původní délky pole)
- Při zadání **menší délky** se **pole ořízne**
- Při zadání **větší délky** se **prvky navíc nastaví na hodnotu** ```0, 0.0, false``` nebo ```null``` **podle typu pole**
#### Kopie polí základních datových typů
- Při kopírování polí základních datových typů, kdy jednotlivé hodnoty jsou přímo prvky pole, dostaneme „plnohodnotnou“ kopii pole
- Pokud provedeme změnu prvku v kopii pole, změna se nijak neprojeví v původním poli
#### Kopie polí objektů
- Při **kopírování polí objektů** jsou v prvcích pole uloženy **pouze reference na jednotlivé instance**
- Zkopírováním pole se **zkopírují pouze reference**, které ale **stále ukazují na původní instance**
- Pokud provedu změnu atributu prvku v kopii pole, projeví se tato změna i v odpovídajícím prvku původního pole (protože se stále jedná o stejnou instanci)
