258 lines
19 KiB
Markdown
258 lines
19 KiB
Markdown
# Ř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**
|
||
|