Egyesítés rendezése

Egyesítés rendezési animáció

Felfedező vagy feltaláló	John von Neumann
A felfedezés dátuma	1945
Kapcsolódó kérdések	Rendezés összehasonlítás alapján ( en ) , stabil rendezési algoritmus ( en )
Adatszerkezetek	Táblázat , egyesítési algoritmus ( in )
Kezdetekor	Timsort

Az idő összetettsége

Legrosszabb esetben	$O (n \ log n)$
Átlagos	$O (n \ log n)$
Legjobb eset	$O (n \ log n)$

A tér összetettsége

Legrosszabb esetben	$Mi)$
Legjobb eset	$O (1)$

A számítástechnika , egyesítés válogatás , vagy dichotóm válogatás, egy stabil összehasonlítás rendezési algoritmus . Az n méretű bemenet időbeli összetettsége n log n nagyságrendű , ami aszimptotikusan optimális. Ez a rendezés az osztás és meghódítás algoritmikus technikán alapszik . Az algoritmus fő művelete az összevonás , amely két rendezett lista összekapcsolásából áll. Az algoritmus hatékonysága abból adódik, hogy két rendezett lista lineáris időben egyesíthető.

Az összeolvadás rendezését természetesen leírják a listák, és az ilyen struktúrákon egyszerre van a legegyszerűbb és leggyorsabb. Ugyanakkor tömbökön is működik . A táblák egyesítésének egyszerűbb verziója hatékonyságában összehasonlítható a gyors rendezéssel , de nem működik a helyén : további, ideiglenes adatterületre van szükség, amely akkora, mint a bemenet (bonyolultabb verziók elvégezhetők a következőn: de lassabbak). A listákon összetettsége optimális, nagyon egyszerűen megvalósítható, és nem igényel másolatot az ideiglenes memóriában.

Intuíció

Két rendezett listából könnyen fel lehet építeni egy rendezett listát, amely tartalmazza a két listából származó elemeket (azok * fúziója *). Az összevonás-rendezési algoritmus elve ezen a megfigyelésen alapszik: a felépítendő lista legkisebb eleme vagy az első lista legkisebb eleme, vagy a második lista legkisebb eleme. Így felépíthetjük a listaelemet elemenként úgy, hogy néha eltávolítjuk az első lista első elemét, néha a második lista első elemét (valójában a kettő közül a kisebbet, feltételezve, hogy a két lista egyik sem üres., egyébként a válasz azonnali).

Ezt a folyamatot fúziónak hívják, és az alábbiakban kidolgozott rendezési algoritmus középpontjában áll.

Algoritmus

Az algoritmust természetesen rekurzív módon írják le.

Ha a tömbnek csak egy eleme van, akkor az már rendezve van.
Ellenkező esetben válassza a táblázatot két nagyjából egyenlő részre.
Rekurzívan rendezze a két részt az egyesítés rendezési algoritmussal.
Egyesítse a két rendezett tömböt egy rendezett tömbbe.

Álkódban:

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])

Az algoritmus azért fejeződik be, mert a rendezendő tömb mérete szigorúan csökken a hívások során. A egyesítési A és B jelentése ahol a a mérete a és b jelentése a mérete B. A egyesítési fajta egy tömb T jelentése ahol n a méret a tömb T. A szimbólum ⊕ itt jelöli összefűzöttjével festmények. ${\ displaystyle O (a + b)}$ $O (n \ log n)$

Végrehajtás listákon

A következő algoritmus részletes, így lefordítható bármely imperatív nyelvre . A rendezni kívánt lista mérete n . Az algoritmus tömörsége és hatékonysága érdekében feltételezzük, hogy a rendezendő listának legalább 2 eleme van, és hogy:

vagy egyszerűen láncolt, nem kör alakú, és előtte p gyökér link van (a listán kívül, de az első elemére mutat);
vagy egyszerűen láncolt és kör alakú;
vagy kétszeresen láncolt és kör alakú.

A lista minden esetben a paraméterként átadott p hivatkozás után rendeződik , vagyis a p utód linkje lesz a legkisebb a listában. Kicsit kevésbé tömör, de ezektől a strukturális korlátoktól mentes leírások léteznek.

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 fin

A következő link elmozdulása q után egy p link ideiglenes t mutatóra van szükség . Ha a lista egyszerűen láncolva van, a mozgást a linkek cseréje hajtja végre:

t := q.suivant q.suivant := t.suivant t.suivant := p.suivant p.suivant := t

Ha a lista kétszeresen láncolt és kör alakú, akkor a mozgást a linkek ezen cseréje hajtja végre:

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 := t

Az így ismertetett algoritmus nagyon könnyen hibridizálható más fajtákkal. Ez egy feltétel hozzáadásával történik a rendezési függvény legelső sorában ( p , n ). Kis allistákon az a szerepe, hogy az összes műveletet valamilyen másodfokú bonyolultsággal, de a gyakorlatban gyorsabban helyettesítse. A következőkben a P> = 2 és a Q> = 2 feltételek eltávolíthatók.

Megvalósítás táblákon

Asztalokkal a helyszínen rendezhetjük vagy sem. Ekkor vázlatosan három lehetőség van a memóriakezelésre:

A kezelést a helyszínen végezzük. Először a helyben lévő elempárok vagy triádok rendezésével kezdjük, majd a szomszédos listákat összeillesztjük a helyükre. Az egyesítési eljárás ezután egy olyan altömbre vonatkozik, amely két listát tartalmaz egymás után. A helyükön való egyesülés érdekében az első lista áthelyezésének egyszerű végrehajtása a második egy vagy több elemének beillesztésekor lassú (hasonlóan a beszúrás rendezéséhez ). Más gyorsabb algoritmusok léteznek, de bonyolultak és gyakran nem stabilak (nem tartják be az előző sorrendet). Lásd az alábbi külső linket.
A kezelést félig a helyszínen végezzük. Kezdjük az elempárok vagy triádok hely szerinti rendezésével, majd összeolvadunk. Az egyesítés során elkészítjük az ideiglenes memóriában található első lista másolatát (másolatot készíthetünk a két listáról, de ez nem szükséges). Így nincs többé szükségünk az adatok áthelyezésére, egyszerűen átmásolunk egy elemet az első listából (ideiglenes memóriából) vagy a második listából (amelyet a helyén tartunk). Ez a megoldás gyorsabb (gyorsabb, mint egy halom rendezés, de lassabb, mint egy gyors rendezés ).
A rendezéshez a tömbdel megegyező méretű ideiglenes területet használunk. Ezután egyesíthetjük az egyik táblázatot a másikhoz. Egyetlen elem rendezése ekkor azt jelenti, hogy átmásolja az egyik tábláról a másikra, két elem rendezése pedig keresztmetszet vagy nem stb. Ezúttal az egyesítés során, amikor az első vagy a második lista első elemét lemásoljuk, nem kell sem az adatokat eltolni, sem az első listát másolni. Ennek a megoldásnak a bonyolultsága összehasonlítható a gyors rendezéssel , anélkül, hogy hátránya lenne a másodfokú legrosszabb esetnek. Ez az egyesítési rendezés több példányt készít, mint egy gyors rendezés, de kevesebb összehasonlítást végez.

Tulajdonságok

A szükséges összehasonlítások száma kb . $n \ log n$
A szükséges memóriahely O (n) -ben van, hacsak nem forgatja el az elemeket.

Lehetséges optimalizálások

A memóriahasználatot tekintve:
- A felhasznált memória n / 2 elemre korlátozható, ha a két lista közül az elsőt másolja át ideiglenes memóriába;
- Korlátozhatja az O (1) -re használt memóriát, ha nem másolja az elemeket. Egyesítheti az első lista közepétől a második közepéig haladó elemek elforgatásával.
A végrehajtás sebességét illetően:
- Megadhatja az egyik tömbből a másikba másolás sebességét, miközben csak egy ideiglenes tömböt használ, amelynek mérete n / 2. Legyen A rendezéshez a tömb első és B második fele, C pedig az n / 2 méretű ideiglenes tömb. Az A és C, majd A és B. közötti elemek másolásával válogatunk. Végül a B és C pontban kapott listákat az egész AB tömbbe egyesítjük.

Példa

Egyesítési művelet

Egyesítés [1; 2; 5] és [3; 4]: Az összevont lista első eleme a két bemeneti lista egyikének első eleme lesz (1 vagy 3), mivel ezek rendezett listák.

Hasonlítsd össze az 1-et és a 3-at: az 1 kisebb
- [2; 5] - [3; 4] → [1]
Hasonlítsa össze a 2-et és a 3-at: 2 kisebb
- [5] - [3; 4] → [1; 2]
Hasonlítsa össze az 5. és a 3. → a 3 kisebb
- [5] - [4] → [1; 2; 3]
Hasonlítsd össze az 5-öt és a 4-et: a 4 kisebb
- [5] → [1; 2; 3; 4]
Az egyesülés eredménye:
- [1; 2; 3; 4; 5]

Rendezés, teljes eljárás

Futtassuk át a következő hívásokat 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]

Ne feledje, hogy az egyesítés függvényt mindig rendezett listákon hívják meg.

Lásd is

Külső linkek

(en) A Java a rendezési fúzió egyik változatát használja a trisz objektumgyűjteményeihez
(en) Merge válogatás helyben : egy cikk az egyesítés rendezéséről, de nem stabil (fájl PostScript formátumban) $O (n \ log n)$
(en) Merge válogatás a helyén: okos algoritmus a Java-ban az egyesítés rendezéséhez a helyben és stabilan, az elforgatások segítségével
(en) Az egyesítés válogatásának dinamikus ábrázolása

Hivatkozások

Steven Skiena, Az algoritmus Design kézikönyv , Springer Science + Business Media ,2008, 730 p. ( ISBN 978-1-84800-069-8 ) , p. 122