# Řazení

- 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
- Vlastnosti **řazení záměnou**
	- Řazení **je stabilní**
	- **Složitost Ο(n²)**

#### Porovnání základních algoritmů řazení

- **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()```

#### Víceúrovňové řazení provedené najednou (běžný postup)

- 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)
	- Jedná o tzv. **mělkou kopii pole**