Speciální řadící algoritmy

  • Dokážou seřadit čísel v nejhorším případě rychleji než v čase
  • Nepracují v porovnávacím modelu RAM, ale pro řazení využívají s výhodou nějakou speciální vlastnost vstupu
  • Nelze je tedy použít na seřazení obecné vstupní posloupnosti čísel

CountingSort

  • Pro řazení celých čísel (int) z množiny

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

    1. Spočítá, kolikrát se ve vstupním poli každé číslo vyskytuje (histogram)
    1. Nad tímto počtem výskytů vypočte prefixovým součtem pozice
    1. Přesune prvky na pozice

../Attachments/Pasted image 20230124173948.png

  • Časová složitost je
  • Pro má lineární složitost

LexCountingSort

  • Podobný jako CountingSort
  • Nepotřebuje na vstupu malé integery, ale umí řadit -tice (např. víceciferná čísla, řetězce apod.)
  • Řadíme je slovníkově (lexikogragicky)
  • Nejdříve data sesortíme podle nejméně důležité cifry, poté podle 2. nejméně důležité atd.
    • Je potřeba stabilita třídícího procesu
  • Využijeme toho, že CountingSort je stabilní

../Attachments/Pasted image 20230125151728.png

  • Časová složitost je

Příklad běhu

../Attachments/Pasted image 20230125151903.png

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