Zobecněný odhad složitosti

Uvažujeme pouze členy nejvyššího řádu, vynecháváme multiplikativní konstanty

Využíváme notaci velkého O,

Značení

• - maximum (Asymptotická horní mez O)
• - minimum (Asymptotická dolní mez Omega)
• - maximum i minimum, těsnost (Asymptotická těsná mez Théta)

Složitosti ve vzestupném pořadí:

1. Konstantní
2. Logaritmická - většinou jako důsledek půlení intervalů
3. Odmocninová
4. Lineární
5. Mocninná - většinou jako důsledek vnořených cyklů
6. Exponenciální
7. Faktoriál

1. Porovnává 2 sousední prvky
2. Pokud jsou v nesprávném pořadí, prohodí je. Takto porovnává, dokud největší prvek "nevybublá" nahoru a není už seřazený
3. Takto ve vlnách opakuje dokola

1. Nejprve projdeme celé pole a vybereme min
2. Pak min prohodíme s prvním prvkem, získáme první zatříděný prvek
3. Od druhého prvku opět projdeme celé pole a vybereme min
4. Pak min prohodíme s druhým prvkem, získáme druhý zatříděný prvek
5. Takto se opakuje, dokud není celé setříděné

Algoritmus

1. První prvek v poli považujeme za seřazený
2. Další prvek (z neseřazené části "vyjmeme ven" a uložíme do paměti/proměnné mem), tím vznikne volné místo za seřazenou částí
3. Prvky seřazené části od konce porovnáváme s mem
   1. Pokud jsou větší než mem, posune je v poli doprava
   2. Pokud je prvek menší než mem (nebo jsme na začátku pole), vloží mem za něj (resp. na začátek pole)
4. Pokračuje krokem 2., dokud existují další neseřazené prvky

Časová:

Paměťová: In-place, stabilní, citlivý

I když časové a paměťové vlastnosti vypadají stejné jako BubbleSort, InsertSort nedělá prohazování, jen posunutí v poli o jednu pozici. Tyto operace jsou efektivnější a rychlejší.

Dokáže řadit, i když mu v průběhu přicházejí další a další data (tzv. "online řazení")

Založen na metodě Rozděl a panuj, využívá rekurzi

Algoritmus

1. (Rozdělení) Rekurzivně rozděluje pole na poloviny, dokud nezůstane pole velikosti 1 (to považujeme za seřazené)
2. (Slévání) O krok výše tyto dvě "podpole" sléváme dohromady
   1. V každém máme index
   2. Posouváme indexy, porovnáváme hodnoty prvků
   3. Ten menší prvek vložíme na začátek nového seřazeného pole a posuneme index

Časová:

Paměťová: (na pomocné pole), stabilní, necitlivý

Podobný MergeSortu

Nepotřebuje pomocné pole, žádný prostor navíc

Algoritmus

1. Zvolí se pivot - ideálně to je medián, ale většinou ho neznáme. Bere se buď náhodný prvek, nebo vždy první (či poslední)
2. Rozdělí vstup na části - levou (< pivot), střední (pivot) a pravou (> pivot)
3. Obě části se řadí rekurzivně, střední (pivot) je považována za seřazenou

Časová: Nejhůře , typicky

Paměťová: "In-place", nestabilní, necitlivý

• In-place z hlediska, že nepotřebuje pomocné pole, prohazuje prvky v původním
• Overhead rekurze ale spotřebovává paměť zásobníku, tam je

Řazení celých čísel z množiny

Omezení rozsahu vstupu je právě tou speciální vlastností

Prvky vůbec neporovnává, namísto toho využívá indexy v poli jako přihrádky

Algoritmus

1. Spočítá, kolikrát se ve vstupním poli každé číslo vyskytuje (histogram)
2. Nad tímto polem počtů výskytů pak vypočte prefixovým součtem pozice, kde budou po seřazení začátky oblastí tvořených stejnými čísly
3. Projde podruhé vstupní pole, pro každý prvek určí jeho pozici, na které se má nacházet po seřazení. Na tuto pozici ho přesune

Časová:

Paměťová: , stabilní, necitlivý

• Není in-place, potřebuje externí paměť, a to dost
• Necitlivý na uspořádání vstupu, citlivý na rozsah hodnot (to číslo )

Lexikograficky řadí -tice (např. víceciferná čísla, řetězce apod.)

Využívá toho, že CountingSort je stabilní

Algoritmus

1. Seřadíme podle poslední pozice pomocí CountingSortu
2. Opakujeme s předchozí pozicí

Časová:

Paměťová: , stabilní, necitlivý

• Necitlivý na uspořádání vstupu, citlivý na parametry