QuickSort

  • Náhodně z pole vyberu pivota (ideálně skoromedián)

  • Vlevo od pivota jsou menší prvky, vpravo větší

  • Navíc, efektivnější řešení:

    • Pointer jde zleva, druhý pointer z prava
    • Posouvají se ke středu, případně swapnou prvky
    • Kde se potkají, tam je pivot

  • Strom rekurzivních volání má hloubku

  • V součtu přes všechny hladiny proto časová složitost

  • Hardware-friendly algoritmus

    • Máme i další algoritmy s podobnou časovou složitostí
    • Ty ale třeba využívají další pomocná pole, nebo randomně skáčou v poli
    • QS je proto lepší, že projíždí sekvenčně, CPU ho dokáže lépe optimalizovat a predikovat

  • Jakmile nějaké 2 prvky mezi sebou porovná, už je nikdy neporovná znovu

Analýza

Indikátor

  • Indikátor je náhodná veličina, pokud nabývá pouze hodnot 0 nebo 1
  • Zda něco nastalo nebo ne
  • Počítáme pravděpodobnost, jestli náhodná veličiny vrátí 0 nebo 1
  • Střední hodnota indikátoru = pravděpodobnost , že vrátí 1

Věta o linearitě střední hodnoty

Součet harmonické řady

  • Pro součet harmonické řady platí, že
  • její součet je zhruba
  • (a víme, že )

Důkaz věty o analýze QuickSortu

  • Vstupní posloupnost:

  • Výstupní posloupnost: tedy seřazená

  • Pro každou dvojici v posloupnosti zavedeme

    • pokud během řazení došlo k porovnání s
    • jinak
    • Indikátor, jestli byly prvky spolu porovnány

  • Pravděpodobnost

    • Tady pravděpodobnost, že se dva prvky porovnají
    • To nastane pouze tehdy, když jeden z nich byl zvolen za pivota
    • A žádný prvek mezi nimi (v seřazené posloupnosti) za pivota zvolen nebyl

  • Střední hodnota

  • = celkový počet všech porovnání

Složitost QuickSortu v průměru přes všechny vstupy

  • Vybírání pivota z pevné deterministické pozice není odolné proti hnusnému vstupu
  • Proto je lepší volit náhodnou pozici pivota
  • Nebo vstup zpermutovat (zrandomizovat pozice)
  • Poté se v průměru bude chovat vždycky relativně dobře

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25