Triedenie zlučovaním
Triedenie zlučovaním je interaktívny pokus z aplikácie Algoritmy v akcii, bezplatnej simulácie zo StudyFi Lab, ktorá beží priamo v prehliadači.
Triedenie zlučovaním rozdelí pole na polovice, každú zoradí rovnakým spôsobom (rekurziou) a potom dve zoradené polovice zlúči do jednej: vždy vezme menší z čelných prvkov. Polenie dá log₂ n úrovní a každá úroveň spracuje všetkých n prvkov, takže časová zložitosť je vždy O(n log n). Pri zhode berie prvok z ľavej polovice, preto je stabilné.
Vyskúšaj: Skús obrátené a potom takmer zoradené pole s rovnakou veľkosťou. Počet porovnaní sa zmení len málo — na poradí vstupu takmer nezáleží.
Časté otázky
Čo ukazuje pokus „Triedenie zlučovaním“?
Triedenie zlučovaním rozdelí pole na polovice, každú zoradí rovnakým spôsobom (rekurziou) a potom dve zoradené polovice zlúči do jednej: vždy vezme menší z čelných prvkov. Polenie dá log₂ n úrovní a každá úroveň spracuje všetkých n prvkov, takže časová zložitosť je vždy O(n log n). Pri zhode berie prvok z ľavej polovice, preto je stabilné.
Ako si vyskúšať „Triedenie zlučovaním“?
Skús obrátené a potom takmer zoradené pole s rovnakou veľkosťou. Počet porovnaní sa zmení len málo — na poradí vstupu takmer nezáleží.
Učíš sa na test?
Nahraj svoje poznámky a StudyFi z nich urobí kartičky, testy a podcasty.