Diplomová práce

Adaptive Sorting Algorithms

Bc. Daniel Timko
Anotace

Všeobecný algoritmický problém triedenia je už desaťročia vyriešený asymptoticky optimálnymi algoritmami, ako sú Heapsort alebo Merge Sort. Reálne dáta sú ale často už čiastočne usporiadané a tradičné triediace algoritmy nedokážu túto skutočnosť využiť. Adaptívne triediace algoritmy sú navrhnuté tak, aby túto vlastnosť vstupu využili a zlepšili praktickú efektivitu triedenia. Prínos tejto diplomovej …více

Abstract

The general algorithmic problem of sorting has been solved for decades with asymptotically optimal algorithms like Heapsort or Merge Sort. However, much of real-world data is already partially ordered to some degree, and traditional algorithms may fail to take advantage of this. Adaptive sorting algorithms are designed to exploit this input property and improve the practical efficiency of sorting. …více

Klíčová slova
adaptive sorting sorting algorithms presortedness Natural Merge Sort Timsort Powersort benchmark performance analysis Python
Zadání práce
Cílem diplomové práce je představit jednotným způsobem adaptivní řadící algoritmy, konkrétně  Natural Merge Sort, Timsort a Powersort. Prezentace algoritmů bude doplněna pseudokódy a ilustrativními příklady. Druhou část práce tvoři extenzivní experimentální porovnání popsaných algoritmů. Pro tento účel navrhne diplomant sadu testovacích posloupností s různými charakteristikami (velikost, míra předuspořádání) s cílem charakterizovat vstupy, pro které jsou jednotlivé algoritmy (ne)efektivní.
Administrativní informace
Práce zkontrolována:
22. 5. 2025 09:11, prof. RNDr. Ivana Černá, CSc., učo 1419
Plný text práce
1 MB / soubor PDF
Přílohy (1)
Jazyk práce
angličtina angličtina
Termín obhajoby
18. 6. 2025
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Ivana Černá, CSc., učo 1419
KTP FI MU

Oponent

RNDr. Nikola Beneš, Ph.D., učo 72525
KPSK FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Nasazení a provoz softwarových systémů

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.