Objevitel nebo vynálezce | John von Neumann |
---|---|
Datum objevu | 1945 |
Související problémy | Třídění podle srovnání ( en ) , stabilní třídicí algoritmus ( en ) |
Datové struktury | Algoritmus sloučení tabulky ( v ) |
Na začátku | Timsort |
Nejhorší případ | |
---|---|
Průměrný | |
Nejlepší případ |
Nejhorší případ | |
---|---|
Nejlepší případ |
V počítačové vědě je sloučení třídění nebo dichotomické třídění stabilním srovnávacím algoritmem třídění . Jeho časová složitost pro vstup velikosti n je řádově n log n , což je asymptoticky optimální. Toto třídění je založeno na algoritmické technice rozděl a panuj . Hlavní operací algoritmu je slučování , které spočívá ve spojení dvou seřazených seznamů do jednoho. Účinnost algoritmu vychází ze skutečnosti, že lze v lineárním čase sloučit dva seřazené seznamy.
Sloučené třídění je přirozeně popsáno na seznamech a na takových strukturách je nejjednodušší i nejrychlejší. Funguje to však také na polích . Jednodušší verze sloučeného řazení na tabulkách má efektivitu srovnatelnou s rychlým tříděním , ale nefunguje na místě : je zapotřebí další dočasná oblast dat, která má stejnou velikost jako položka (složitější verze mohou být provádí se na místě, ale jsou pomalejší). Na seznamech je jeho složitost optimální, lze jej implementovat velmi jednoduše a nevyžaduje kopii v dočasné paměti.
Ze dvou seřazených seznamů lze snadno sestavit seřazený seznam obsahující prvky vyplývající z těchto dvou seznamů (jejich * fúze *). Princip tohoto algoritmu sloučení je založen na tomto pozorování: nejmenší prvek seznamu, který má být sestaven, je buď nejmenší prvek prvního seznamu, nebo nejmenší prvek druhého seznamu. Můžeme tedy vytvořit prvek seznamu po prvku odstraněním někdy prvního prvku prvního seznamu, někdy prvního prvku druhého seznamu (ve skutečnosti menšího ze dvou za předpokladu, že žádný ze dvou seznamů není prázdný., jinak je reakce okamžitá).
Tento proces se nazývá fúze a je jádrem třídicího algoritmu vyvinutého níže.
Algoritmus je přirozeně popsán rekurzivně.
V pseudokódu:
entrée : un tableau T sortie : une permutation triée de T fonction triFusion(T[1, …, n]) si n ≤ 1 renvoyer T sinon renvoyer fusion(triFusion(T[1, …, n/2]), triFusion(T[n/2 + 1, …, n])) entrée : deux tableaux triés A et B sortie : un tableau trié qui contient exactement les éléments des tableaux A et B fonction fusion(A[1, …, a], B[1, …, b]) si A est le tableau vide renvoyer B si B est le tableau vide renvoyer A si A[1] ≤ B[1] renvoyer A[1] ⊕ fusion(A[2, …, a], B) sinon renvoyer B[1] ⊕ fusion(A, B[2, …, b])Algoritmus končí, protože velikost pole, které má být tříděno, se v průběhu volání striktně snižuje. Sloučení A a B je tam, kde a je velikost A a b je velikost B. Sloučený druh pole T je kde n je velikost pole T. Symbol ⊕ zde označuje zřetězení obrazů.
Následující algoritmus je podrobný, takže je možné jej přeložit do jakéhokoli imperativního jazyka . Seznam k seřazení má velikost n . Pro stručnost a efektivitu algoritmu se předpokládá, že seznam, který má být seřazen, obsahuje alespoň 2 prvky a že:
Ve všech případech je seznam seřazen po předání odkazu p jako parametru, tj. Následný odkaz p bude nejmenší v seznamu. Trochu méně stručné popisy, ale osvobozené od těchto strukturálních omezení, existují.
fonction trier(p, n) Q := n/2 (division entière) P := n-Q si P >= 2 q := trier(p, P) si Q >= 2 trier(q, Q) sinon q := p.suivant fin q := fusionner(p, P, q, Q) renvoyer q fin fonction fusionner(p, P, q, Q) pour i allant de 0 à taille(p)-1 faire si valeur(p.suivant) > valeur(q.suivant) déplacer le maillon q.suivant après le maillon p si Q = 1 quitter la boucle Q := Q-1 sinon si P = 1 tant que Q >= 1 q := q.suivant Q := Q-1 fin quitter la boucle fin P := P-1 fin p := p.suivant fin renvoyer q finPosun následujícího odkazu q. Po odkazu p vyžaduje dočasný ukazatel t . Pokud je seznam jednoduše zřetězený, pohyb se provádí touto výměnou odkazů:
t := q.suivant q.suivant := t.suivant t.suivant := p.suivant p.suivant := tPokud je seznam dvojnásobně zřetězený a kruhový, pohyb se provádí touto výměnou odkazů:
t := q.suivant q.suivant := t.suivant q.suivant.précédent := q t.précédent := p t.suivant := p.suivant p.suivant.précédent := t p.suivant := tTakto popsaný algoritmus lze velmi snadno hybridizovat s jinými druhy. To se provádí přidáním podmínky na první řádek funkce řazení ( p , n ). Na malých dílčích seznamech má za úkol nahradit všechny operace, které následují, určitou kvadratickou složitostí, ale v praxi rychlejší. V následujícím lze potom podmínky P> = 2 a Q> = 2 odstranit.
S tabulkami to můžeme třídit na místě nebo ne. Schematicky pak existují tři možnosti správy paměti:
Sloučit [1; 2; 5] a [3; 4]: první prvek sloučeného seznamu bude prvním prvkem jednoho ze dvou vstupních seznamů (buď 1 nebo 3), protože jde o seřazené seznamy.
Pojďme si projít následující volání tri_fusion([6, 1, 2, 5, 4, 7, 3]) :
tri_fusion([6, 1, 2, 5, 4, 7, 3]) [6, 1, 2, 5] [4, 7, 3] tri_fusion([6, 1, 2, 5]) [6, 1] [2, 5] tri_fusion([6, 1]) [6] [1] tri_fusion([6]) --> [6] tri_fusion([1]) --> [1] '''fusion''' de [6] et [1] : [1, 6] --> [1, 6] tri_fusion([2, 5]) [2] [5] tri_fusion([2]) --> [2] tri_fusion([5]) --> [5] '''fusion''' de [2] et [5] : [2, 5] --> [2, 5] '''fusion''' de [1, 6] et [2, 5] : [1, 2, 5, 6] --> [1, 2, 5, 6] tri_fusion([4, 7, 3]) [4] [7, 3] tri_fusion([4]) --> [4] tri_fusion([7, 3]) [7] [3] tri_fusion([7]) --> [7] tri_fusion([3]) --> [3] '''fusion''' de [7] et [3] : [3, 7] --> [3, 7] '''fusion''' de [4] et [3, 7] : [3, 4, 7] --> [3, 4, 7] '''fusion''' de [1, 2, 5, 6] et [3, 4, 7] : [1, 2, 3, 4, 5, 6, 7] --> [1, 2, 3, 4, 5, 6, 7]Všimněte si, že funkce sloučení je vždy volána na seřazených seznamech.