Skip to content

3.5 Jednoduché řazení

Definice 3.9 (Problém řazení)

Problém řazení

  • Vstup: Číslo \(n\) a posloupnost čísel \(A = a_{1}, a_{2}, . . . , a_{n}\).
  • Výstup: Taková permutace \(A^{′} = a_{1}^{′}, a_{2}^{′}, . . . , a_{n}^{′}\) vstupní posloupnosti A,
    že platí \(a_{1}^{′} \leq a_{2}^{′} \leq ... \leq a_{n}^{′}\)
  • Příklad: \(n = 6, A = 23, 7, 19, 21, 5, 12, A^{′} = 5, 7, 12, 19, 21, 23\).
  • Obecně: ze vstupní posloupnosti vytvořit posloupnost hodnot v předdefinovaném pořadí.
  • Fundamentální problém v informatice.
  • Existuje řada přístupů a algoritmů.
  • Implicitně budeme uvažovat algoritmy řadicí vzestupně.

Taxonomie algoritmů pro řazení

(A) Základní operace:

  1. Řazení založené na pouze binární operaci porovnání-a-prohození (Compare-And-Exchange).
  2. Řazení založené na jiné operaci.

(B) Paměťová náročnost:

  1. In-place algoritmy (potřebují \(n\) + polylog(\(n\)) paměti).
  2. Out-of-place algoritmy.

(C) Stabilita:

  1. Stabilní algoritmy (stejně velké prvky se nikdy neprohodí).
  2. Nestabilní algoritmy (stejně velké prvky se mohou prohodit).

(D) Citlivost na hodnoty prvků vstupní posloupnosti:

  1. Datově citlivé algoritmy (časová složitost závisí na hodnotách prvků).
  2. Datově necitlivé algoritmy (časová složitost nezávisí na hodnotách prvků).

Kvadratické algoritmy řazení

  • Vstupní posloupnost se rozdělí na levou seřazenou a pravou neseřazenou část.
  • Na počátku je levá část prázdná a pravá část je celá vstupní posloupnost.
  • Po vložení prvku se hranice mezi seřazenou a neseřazenou částí posune o jednu pozici doprava.

Algoritmus 3.2 (SelectSort)

Algoritmus SelectSort

Z neseřazené pravé části se vybere minimum a prohodí se s jejím prvním prvkem, tj. přímo za seřazenou část.

Vlastnosti

  • Seřadí \(n\)-prvkové pole v čase \(Θ(n^{2})\)
  • in-place, nestabilní, datově necitlivý

Invariant: Po \(i\)-té iteraci je vlevo seřazená posloupnost délky \(i\) a vpravo zbývá \(n − i\) neseřazených prvků, které jsou \(\geq\) než čísla v levé části.

Algoritmus 3.3 (InsertSort)

Algoritmus InsertSort

Z neseřazené pravé části se vezme první prvek a vloží se zprava na správnou pozici v levé seřazené části.

Vlastnosti

  • Seřadí \(n\)-prvkové pole v čase \(O(n^{2})\)
  • in-place, stabilní, datově citlivý.

Invariant: Po \(i\)-té iteraci je vlevo seřazená posloupnost délky \(i + 1\) a vpravo zbývá \(n − 1 − i\) neseřazených prvků.

Algoritmus 3.4 (BubbleSort)

Algoritmus BubbleSort

  • Řazení probubláváním větších prvků doprava.

Idea

  • Postupně zleva doprava se porovnávají dvojice sousedních prvků a pokud jsou prvky dvojice v nesprávném pořadí, prohodí se.
  • Po prvním průchodu bubliny se největší prvek dostane na poslední místo.
  • Celý postup se opakuje nejvýše \((n − 1)\)-krát: pokaždé se seřazená podposloupnost vpravo prodlouží o jednu pozici doleva.
  • Pokud se během jednoho průchodu neprohodila žádná dvojice sousedů, už se nikdy žádná neprohodí a řazení skončilo.
  • Vhodný algoritmus, pokud je např. vstupní posloupnost z velké části seřazená

Algoritmus

BubbleSort
1
2
3
4
5
6
7
8
9
end := n
zmena := 1
Dokud zmena = 1:
    zmena := 0
    Pro j := 1 ... (end − 1):
        Pokud P [j] > P [j + 1]:
            prohoď P [j] a P [j + 1]
            zmena := 1
    end−−

Věta 3.8 (o korektnosti algoritmu BubbleSort)

Věta o korektnosti algoritmu BubbleSort

Algoritmus BubbleSort korektně seřadí \(n\)-prvkové pole.

Důkaz Věty 3.8
  1. Korektnost dokážeme indukčním důkazem následujícího invariantu.
  2. Invariant: nejpozději po \(i\)-té iteraci cyklu na řádcích \((3)\)–\((9)\) se \(i\) největších prvků pole nachází seřazeno na \(i\) posledních pozicích zprava.
  3. IZ: Invariant platí pro \(i = 1\). Po 1. iteraci je největší prvek celé posloupnosti zaručeně na poslední pozici.
  4. IK: Předpokládejme, že Invariant platí pro všechna \(j \lt i\) a tedy \(i − 1\) největších prvků se nachází seřazeno na posledních \(i − 1\) pozicích vpravo. Proveďme \(i\)-tou iteraci.
  5. Tím probublá největší hodnota levého zbytku doprava, levá část se zkrátí o jedna a pravá seřazená část se zvětší o jeden prvek, a invariant platí.

Věta 3.9 (o složitosti algoritmu BubbleSort)

Věta o složitosti algoritmu BubbleSort

BubbleSort seřadí \(n\)-prvkové pole v čase \(O(n^{2})\) a je in-place, stabilní, datově citlivý.

Důkaz Věty 3.9
  1. Iterací je nejvýše \(n − 1\), \(i\)-tá iterace trvá \(\Theta (n − i)\) kroků, což dává časovou složitost \(O(n^{2})\).
  2. Kromě vstupního pole potřebuje pouze \(O(1)\) paměti.
  3. Je stabilní, neboť podmínka na řádku \((6)\) zabrání prohození stejných prvků.
  4. Je datově citlivý, neboť končí, jakmile nedošlo během některé iterace ke změně. V nejlepším případě již seřazeného pole má složitost \(\Theta(n)\).