Összefésüléses rendezés
Összefésüléses rendezés | |
![]() | |
Példa összefésüléses rendezésre (szerző: Swfung8). A listát az algoritmus először egyelemű részekre osztja, majd minden listát a szomszédos listával hasonlít össze, hogy rendezze, és összeegyesítse a két szomszédos listát. Végül minden elemet rendez és összeegyesít az algoritmus. | |
Kategória | rendezési algoritmus |
Adatstruktúra | tömb |
Legrosszabb időbonyolultság | |
Legjobb időbonyolultság | tipikus, természetes változat |
Átlagos idő bonyolultság | |
Legrosszabb tár bonyolultság | , segédváltozóval további , láncolt segédlistával további [1] |
Optimális | igen |
A számítástechnikában a merge sort (gyakran egybeírva, mergesort néven szerepel) hatékony, általános célú, az összehasonlító rendezések sorába tartozó rendezési algoritmus. Legtöbbször stabil rendezést valósít meg, vagyis az egyenlő elemek sorrendje a kimeneten ugyanaz, mint a bemeneten. Az oszd meg és uralkodj-elvű összefésüléses rendezés algoritmusát Neumann János 1945-ben gondolta ki. Az alulról felfelé építkező összefésülések részletes leírását és elemzését Goldstine és Neumann közölte, már 1948-ban.[2]
Algoritmus
Egy összefésüléses rendezés működése:
- A rendezetlen lista n egyelemű allistára való osztása, melyeket rendezettnek tekint az algoritmus.
- Allisták összefésülése új, rendezett allisták kiadásához, míg egy allista nem marad. Ez a rendezett lista.
Felülről lefelé építkező algoritmus
A felülről lefelé történő összefésüléses rendezést megvalósító C-szerű példakód indexeket használ az algoritmushoz, mely folyamatosan szétválasztja a listát, amíg az allistaméret 1 nem lesz, majd azokat rendezett listává egyesíti. A másolást az egyesítési irány ismétlési szintenkénti váltogatásával kerüli el (kivéve egy szintén elkerülhető egyszeri kezdeti másolást). Ennek megértésének megkönnyítéséhez tekinthető egy kételemű tömb. Elemei átkerülnek B tömbbe, majd vissza A-ba. 4 elem esetén az egyelemű listák elérésekor azok A-ból átkerülnek B-be, majd a következő szintben e kételemű sorozatok kerülnek A-ba. Ez a minta folytatódik minden ismétlődési szinttel.
// „A” tömbben vannak a rendezendő elemek, „B” munkatömb. void TopDownMergeSort(A[], B[], n) { CopyArray(A, 0, n, B); // „A”-ból „B”-be való egyszeri másolás TopDownSplitMerge(A, 0, n, B); // B adatainak rendezése A-ba } // A két sorozatra osztása, azok B-be rendezése, majd a sorozatok egyesítése B-ből A-ba // iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set). void TopDownSplitMerge(B[], iBegin, iEnd, A[]) { if (iEnd - iBegin <= 1) //legfeljebb 1 elemű sorozat esetén return; // tekintse rendezettnek // split the run longer than 1 item into halves iMiddle = (iEnd + iBegin) / 2; // iMiddle = középpont // A szakaszainak rendezése B-be TopDownSplitMerge(A, iBegin, iMiddle, B); // bal oldali szakasz rendezése TopDownSplitMerge(A, iMiddle, iEnd, B); // jobb oldali szakasz rendezése // az eredmény másolása B-ből A-ba TopDownMerge(B, iBegin, iMiddle, iEnd, A); } // bal fél: A[iBegin:iMiddle-1] // jobb fél: A[iMiddle:iEnd-1] // eredmény: B[iBegin:iEnd-1] void TopDownMerge(B[], iBegin, iMiddle, iEnd, A[]) { i = iBegin, j = iMiddle; // Amíg a bal vagy a jobb szakasz tartalmaz elemet… for (k = iBegin; k < iEnd; k++) { // Ha van bal oldali szakaszfej, mely a jobb oldalinál kisebb if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) { B[k] = A[i]; i += 1; } else { B[k] = A[j]; j += 1; } } } void CopyArray(A[], iBegin, iEnd, B[]) { for (k = iBegin; k < iEnd; k++) B[k] = A[k]; }
Az egész tömböt a TopDownMergeSort(A, B, length(A)) rendezi.
Alulról felfelé való megvalósítás
A listát n allistából álló tömbnek tekintett C-szerű példakód alulról felfelé való összefésüléses rendezésre, mely az allistákat fésüli össze két puffer közt:
// „A”-ban vannak a rendezendő elemek, „B” munkatömb void BottomUpMergeSort(A[], B[], n) { // Az egyes 1 elemű listák már rendezettek. // Fokozatosan hozzon létre 2, 4, 8 stb. elemű rendezett listákat a teljes tömb rendezéséig. for (width = 1; width < n; width *= 2) { // „A” width hosszúságú listákkal rendelkezik. for (i = 0; i < n; i += 2 * width){ // Két sorozat egyesítése: A[i:i+width-1] és A[i+width:i+2*width-1] egyesítése B-be // vagy A[i:n-1] másolása B-be (ha i+width >= n) BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B); } // B-ben 2*width hosszú sorozatok vannak. // B másolása A-ba a következő iterációhoz. // Hatékonyabb lenne A és B szerepeinek cseréje. CopyArray(B, A, n); // A-ban vannak a 2width hosszú listák. }} // A bal lista: A[iLeft:iRight-1]. // A jobb lista: A[iRight:iEnd-1]. void BottomUpMerge(A[], iLeft, iRight, iEnd, B[]) { i = iLeft, j = iRight; // Amíg valamely szakaszban vannak elemek… for (k = iLeft; k < iEnd; k++) { // Ha a bal lista feje létezik, és kisebb a jobb listáénál. if (i < iRight && (j >= iEnd || A[i] <= A[j])) { B[k] = A[i]; i += 1; } else { B[k] = A[j]; j += 1; } } } void CopyArray(B[], A[], n){for (i = 0; i < n; i++)A[i] = B[i];}
Listahasználó felülről lefelé való megvalósítás
Pszeudokód felülről lefelé való algoritmushoz, mely a bemeneti listát triviális rendezettségig osztja kisebb allistákra, majd az allistákat egyesíti, miközben a láncon egyre feljebb halad.
function merge_sort(list m): // Alapeset. 0 vagy 1 elemű lista triviálisan rendezett. if length of m ≤ 1 then return m // Rekurzív eset. Először ossza fel a listát azonos méretű allistákra, melyek a lista két feléből állnak. Itt feltételezzük, hogy a listák 0-tól kezdődnek. var left := empty list var right := empty list for each x with index i in m do if i < (length of m)/2 then add x to left else add x to right // A két allista rekurzív rendezése. left := merge_sort(left) right := merge_sort(right) // A rendezett allisták egyesítése. return merge(left, right)
Itt a merge függvény egyesíti a bal és a jobb allistákat.
function merge(left, right): var result := empty list while left is not empty && right is not empty: if first(left) ≤ first(right): append first(left) to result left := rest(left) else: append first(right) to result right := rest(right) // A bal és a jobb részek pontosan egyikében maradhat elem: ezeket távolítsa el (az alábbi ciklusokból csak egybe lép az algoritmus). while left is not empty: append first(left) to result left := rest(left) while right is not empty: append first(right) to result right := rest(right) return result
Alulról felfelé haladó megvalósítás listákkal
Az alulról felfelé haladó rendezési algoritmus pszeudokódja látható itt kis hivatkozástömbbel, ahol az array[i] vagy méretű listára hivatkozás, vagy nil. A node hivatkozás vagy csomópontra mutat. A merge függvény hasonlít a fenti példára: két rendezett listát egyesít, és üres listákat is kezel. Ez esetben a node-ot bemeneti paramétereire és kimenetére használja.
function merge_sort(node head) is // visszatérés üres lista esetén if head = nil then return nil var node array[32]; initially all nil var node result var node next var int i result := head // csomópontok egyesítése while result ≠ nil do next := result.next; result.next := nil for (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) do result := merge(array[i], result) array[i] := nil // ne menjen a tömb végén túl if i = 32 then i -= 1 array[i] := result result := next // tömb egyesítése egy listába result := nil for (i = 0; i < 32; i += 1) do result := merge(array[i], result) return result
Elemzés
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e6/Merge_sort_algorithm_diagram.svg/220px-Merge_sort_algorithm_diagram.svg.png)
n objektum rendezésében az összefésüléses rendezés átlagos és legrosszabb eseti teljesítménye . Ha egy n elemű lista rendezésének ideje , akkor az algoritmus definíciójából (az algoritmus két fele akkora listára való alkalmazása, valamint a két lista egyesítéséhez szükséges n lépés összege.[3] Ez az „oszd meg és uralkodj” ismétlések főtételéből következik.
A legrosszabb esetben végzett összehasonlításokat a rendezési számok adják meg. Ezek értéke legfeljebb , ami és közt van.[4] Az összefésüléses rendezés legjobb esetben mintegy feleannyi ismétlést igényel a legrosszabb esetnél.[5]
Nagy n és véletlenszerű bemeneti lista esetén az összefésüléses rendezés várható összehasonlítás-száma -val kevesebb a legrosszabb esetinél, ahol
Legrosszabb esetben az összefésüléses rendezés mintegy 39%-kal kevesebb összehasonlítást végez a gyors rendezés átlagos eseténél, mozgatásszáma , hasonlóan a gyors rendezés legjobb esetéhez.[5]
A gyors rendezésnél hatékonyabb az összefésüléses rendezés, ha a rendezendő adat csak sorozatban érhető el hatékonyan, így népszerű az olyan nyelvekben, mint a Lisp, ahol az ilyen adatszerkezetek gyakoriak. Szemben a gyors rendezés egyes megvalósításaival, az összefésüléses rendezés stabil.
Az összefésüléses rendezés leggyakoribb megvalósítása nem helybe rendez,[6] így a bemenet memóriamérete a rendezett kimenetnek fenntartandó (vö. lejjebb n/2 további helyet igénylő változatokhoz).
Természetes összefésüléses rendezés
A természetes összefésüléses rendezés hasonlít az alulról felfelé építkezőre, de a természetesen előforduló rendezett részsorozatokat felhasználja. A monoton és a biton sorozatok is felhasználhatók, a listák hatékony adatszerkezetek erre (FIFO sorozatként vagy LIFO vermekként).[7] Az alulról felfelé építkező összefésüléses rendezés feltételezi. hogy minden sorozat egyelemű. A gyakorlatban a véletlenszerű bemenet sok rövid, rendezett részsorozattal rendelkezik. Általában nincs annyi áthaladásra szükség, mivel kevesebb egyesítendő sorozat van. Legjobb esetben a bemenet már rendezett (vagyis egy sorozat), így a természetes összefésüléses rendezésnek csak egyszer kell áthaladnia az adaton. Sok gyakorlati esetben hosszú természetes sorozatok is vannak, ezeket használja ki a Tim-rendezésben is a természetes összefésüléses rendezés. Például:
Kezdet : 3 4 2 1 7 5 8 9 0 6 Sorozatok : (3 4)(2)(1 7)(5 8 9)(0 6) Összefésülés: (2 3 4)(1 5 7 8 9)(0 6) Összefésülés: (1 2 3 4 5 7 8 9)(0 6) Összefésülés: (0 1 2 3 4 5 6 7 8 9)
Formálisan a természetes összefésüléses rendezés Runs-optimális, ahol Runs(L) L növekvő vagy csökkenő részsorozatainak számánál eggyel kisebb.
Torna–cserés kiválasztó rendezések használhatók a külső rendezőalgoritmusok kezdeti sorozatainak megadására.
Pingpong-összefésüléses rendezés
A pingpong-összefésüléses rendezés 2 helyett 4 sorozatot egyesít. Ezeket két rendezett sorozatban fésüli össze, melyek egyesítve visszakerülnek a fő memóriába. Így nincs szükség a másolási műveletre, a mozgatások száma feleződik. Egy ilyen megvalósítás közkincsként jelent meg a WikiSortnál 2014-ben, melyet később a pasziánszrendezés optimalizációjának írtak le, és pingpongrendezésnek neveztek.[8][9] A Quadsort 2020-ban vezette be e metódust quad merge néven.[10]
Helyben történő összefésüléses rendezés
Az összefésüléses rendezés egyik hátránya tömböknél az munkamemória-szükséglet. Számos módszert javasoltak ennek csökkentésére vagy a teljes helyben történő megvalósításra:
- (Kronrod 1969) alternatív változatot javasolt konstans többlethelyszükséglettel.
- Katajainen et al. konstans mennyiségű munkamemóriát igénylő változatot javasoltak: elég tárhelyet a bemenet egy elemének, valamint további helyet mutató tárolásához. időhatárt értek el, de az algoritmus nem stabil.[11]
- Számos kísérlet történt helyben történő összefésülő algoritmusra, mely egy összefésülő rendezéssel összekapcsolható, helyben történő összefésülő rendezést adva. Itt a „helyben történő” tágítható „logaritmikus veremhelyet igénylő”-re, mivel a normál összefésüléses rendezés ennyi helyet igényel saját veremhasználatának. Geffert et al. kimutatták, hogy helyben történő stabil összefésülés lehetséges idő alatt konstans mennyiségű ideiglenes tárhellyel, de az algoritmus összetett, és magasak a konstans tényezők: n és m elemű tömbök egyesítéséhez mozgatás is szükséges lehet.[12] A bonyolult algoritmus egyszerűbbé és könnyebben megérthetővé vált. Bing-Chao Huang és Michael A. Langston[13] egyértelmű lineáris idejű algoritmust („helyben történő praktikus összefésülés”) írtak le egy rendezett lista egyesítésére fix mennyiségű további helyigénnyel. Mindketten felhasználták Kronrod és társai munkáját. Az egyesítés lineáris időben történik konstans tárhelyszükséglet mellett. Az algoritmus átlagos futásideje kevesebb mint kétszer hosszabb az egyszerű összefésüléses rendezési algoritmusoknál, és további ideiglenes memóriaegységet tud használni. Bár az algoritmus a gyakorlatban gyorsabb, bizonyos listák esetén instabil. De hasonló koncepciók meg tudták oldani e problémát is. További helyben történő algoritmus például az futásidejű és stabil SymMerge.[14] Egy ilyen algoritmus komplexitása a nem linearitmikus, de mégis kvázilineáris .
- Sok külső rendezés több allistára osztó összefésüléses rendezést használ, ideális esetben annyira, hogy az egyesítésükkor a jelenleg feldolgozott oldalhalmazhoz még elég a fő memória.
- Modern stabil lineáris és helyben történő összefésülés-változat a blokk-összefésüléses rendezés, mely egyedi értékeket használ ideiglenes tárhelyként.
- A tárhelyköltség bináris keresésekkel és forgatásokkal -re csökkenthető.[15] Ezt használja a C++ STL könyvtár és a quadsort.[10]
- Másoláscsökkentő lehetőség az új információmezők kulcshoz (m eleméhez) rendelése. Ez a kulcsok és a kapcsolódó információk (a kulcsok) rendezett listába kapcsolására szolgál. A rendezett listák egyesítése ezután a kapcsolati értékek változtatásával folytatódik rekordmozgatás nélkül. Egy csak kapcsolatot tartalmazó mező általában kisebb a teljes rekordnál, így kevesebb helyet használ. Ez általános rendezési módszer, nem korlátozódik az összefésüléses rendezésre.
- A helyköltség -re csökkentésére egyszerű mód a bal és a jobb oldal teljes szerkezetkénti kezelése, m bal oldalának ideiglenes helybe tétele, majd hogy az egyesítés az egyesített kimenetet m-be helyezze. Ekkor jobb az ideiglenes hely egyesítésen kívüli foglalása, egyszeri foglalást lehetővé téve. A korábban említett sok másolás is megszűnik, mivel a visszatérés előtti utolsó 2 sor fölössé válik.
Használata szalagos tárhelyekkel
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6c/IBM_729_Tape_Drives.nasa.jpg/220px-IBM_729_Tape_Drives.nasa.jpg)
Egy külső összefésüléses rendezés hasznos lemez- vagy szalagmeghajtók esetén, ha az adat nagy az elsődleges tárnak. A külső rendezésen bemutatható a lemezekkel való működés. Egy általános szalagmeghajtós rendezés 4 szalagot használ. A be-/kimenet sorozatban történik (kivéve a visszatéréseket az áthaladások végén. Egy minimális megvalósításban csak 2 puffer és néhány programváltozó van.
A szalagokat A-tól D-ig elnevezve, ahol A-n van az eredeti adat, illetve 2 pufferrel az algoritmus hasonlít az alulról felfelé építkező megvalósításra, szalagmeghajtópárokat használva tömbök helyett. Az alapalgoritmust az alábbiak írják le:
- A párjainak egyesítése, kétrekordos allisták írása C-re és D-re felváltva
- C és D kéttagú allistáinak egyesítése felváltva A-ra és B-re.
- A és B 4 tagú allistáinak egyesítése felváltva C-re és D-re
- E lépések ismétlése rendezettségig lépésben.
Rövid sorozatokkal való kezdés helyett gyakran hibrid algoritmust használnak, ahol először sok adat kerül a memóriába, belső rendezést hajt végre hosszú sorozatot adva, majd ezeket a kimenetbe osztja el. Ez sok korai átmenetet elkerül. Például egy 1024 tagú belső sorozat 9-cel csökkenti a lépésszámot. A belső rendezés ezért gyakran nagy tömbökkel történik. Továbbá vannak módszerek az elérhető memóriánál nagyobb kezdeti sorozatok létrehozásához. Ezek egyike, Knuth bináris minimális kupacon alapuló snowplow algoritmusa a memóriánál átlagosan kétszer hosszabb sorozatokat ad.[16]
Kis többletköltséggel ez módosítható háromszalagossá. futásidő érhető el 2 sorral, egy sorral és egy veremmel vagy 3 veremmel. szalaggal és memóriaelemmel a szalagműveletek száma -szor csökkenthető irányú egyesítő algoritmussal.
A meghajtóhasználatot a polifázisos összefésüléses rendezés optimalizálja.
Optimalizáció
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c5/Merge_sort_animation2.gif/220px-Merge_sort_animation2.gif)
Modern számítógépeken a referenciahely fontos lehet a szoftveroptimalizációban a többszintű memóriahierarchiák miatt. Gyorsítótárbiztos változatokat is javasoltak, ahol a műveletek a gyorsítótári mozgatást minimalizálják. Például a csempézett összefésüléses rendezés leállítja a résztömbök bontását, ha S méretű tömböket ért el, ahol S a processzor gyorsítótárában elférő adatelemek száma. E résztömböket helyben történő algoritmussal, például beillesztéses rendezéssel rendezik a memóriacserék számának csökkentéséhez, a normál összefésüléses rendezést a hagyományos rekurzív módon hajtja végre. Ez jobb teljesítményt mutatott gyorsítótár-optimalizációval rendelkező gépeken.(LaMarca & Ladner 1997)
Párhuzamos egyesítésű rendezés
Az összefésüléses rendezés jól párhuzamosítható az „oszd meg és uralkodj!” elv miatt Számos különböző párhuzamos változat jött létre az évek folyamán. Egyes párhuzamos változatok a sorozatos felülről lefelé haladó összefésülő algoritmushoz kapcsolódnak, míg másoknak ettől eltérő általános szerkezetük van, és K irányú összefésülést használnak.
Párhuzamos rekurzióval
A sorozatos összefésüléses rendezés két szakasszal írható le: a felosztásos és az egyesítő fázissal. Az első sok rekurzív hívásból áll, melyek azonos osztási folyamatot hajtanak végre, míg a részsorozatok triviálisan rendezettek (legfeljebb 1 eleműek). Egy intuitív megközelítés ezek párhuzamosítása.[17] Az alábbi pszeudokód a fork és a join kulcsszavakkal működő párhuzamos rekurziós módszert írja le:
// A tömb lo–hi közti (exkluzív) elemeinek rendezése. algorithm mergesort(A, lo, hi): if lo+1 < hi: // 2 vagy több elem. mid := ⌊(lo + hi) / 2⌋ fork mergesort(A, lo, mid) mergesort(A, mid, hi) join merge(A, lo, mid, hi)
Ez az algoritmus a sorozatosnak triviális módosítása, és nem jól párhuzamosít. Így gyorsulása nem jelentős. Munkaideje , ami csak -szer jobb a sorozatosnál. Ez főképp a sorozatos egyesítés miatt van, mely a szűk keresztmetszetet jelenti a párhuzamos végrehajtásokban.
Párhuzamos összefésülésű rendezés
Jobb párhuzamosság érhető el párhuzamos összefésülő algoritmussal. Cormen et al. egy bináris változatot mutatnak be, mely két rendezett részsorozatot egy rendezett kimenetbe egyesítenek.[17]
Az egyik sorozatban (egyenlőtlen hossz esetén a hosszabban) kiválasztja a középső elemet. Helyzetét a másik sorozatban úgy határozza meg, hogy az elem beillesztése után a sorozat rendezett marad. Így ismert, hány elem kisebb a sorozatokból, és a kiválasztott elem helyzete a kimeneti sorozatban kiszámítható. A kisebb és nagyobb elemekből álló részsorozatra az algoritmus végrehajtása ismét párhuzamosan történik az alapeset eléréséig.
Az alábbi pszeudokód módosított párhuzamos összefésülő rendezést mutat párhuzamos összefésülő algoritmussal (forrás: Cormen et al.).
/** * A: Bemenet * B: Kimenet * lo: alsó határ * hi: felső határ * off: eltolás */ algorithm parallelMergesort(A, lo, hi, B, off): len := hi - lo + 1 if len == 1 then B[off] := A[lo] else let T[1..len] be a new array mid := ⌊(lo + hi) / 2⌋ mid' := mid - lo + 1 fork parallelMergesort(A, lo, mid, T, 1) parallelMergesort(A, mid + 1, hi, T, mid' + 1) join parallelMerge(T, 1, mid', mid' + 1, len, B, off)
A legrosszabb eset rekurzív számításához az ismétlődő hívásoknak csak egyszer kell megtörténniük párhuzamosságuk miatt, így:
E függvény megoldása:
E párhuzamos összefésülő algoritmus párhuzamossága , az előző algoritmusénál sokkal nagyobb. Egy ilyen rendezés gyors stabil sorozatos rendezéssel és gyors sorozatos összefésüléssel kis tömbök egyesítésére való alapesettel jól működhet.[18]
Párhuzamos többirányú összefésüléses rendezés
Nem mindig megfelelő az összefésüléses rendezés kétirányú összefésülésre való korlátozása, hiszen sokszor processzor érhető el. Jobb megközelítés lehet k irányú összefésülést használni, mely ennek általánosítása, ahol k rendezett sorozat egyesítése történik. Ez alkalmas egy PRAM rendezési algoritmusát.[19][20]
Alapötlet
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/44/Parallel_multiway_mergesort_process.svg/220px-Parallel_multiway_mergesort_process.svg.png)
Egy n elemű rendezetlen sorozat esetén a cél a sorozat rendezése p processzorral. Ezek egyenlően vannak elosztva a processzorok közt és helyben rendezve sorozatos rendezési algoritmussal. Így a sorozat hosszú sorozatokból áll.
Az egyes sorozatokat többsorozatos/elosztó kiválasztásra használják. -re az algoritmus meghatározza a elválasztóelemeket, melyek rangja . Ezután a helyzeteit bináris kereséssel határozzák meg, így az tovább bomlik p részsorozatra (, ahol
Majd az elemei, vagyis minden és közti elem az i. processzorhoz kerülnek, melyek egészén el vannak osztva. Így minden processzor rendezett sorozatok sorozatát kapja. Hogy az elválasztó elemek rangja, k globálisan lett megválasztva, két fontos tulajdonságot ad: Egyrészt k úgy lett megválasztva, hogy minden processzor elemen működik hozzárendelés után. Az algoritmus tökéletesen kiegyensúlyozott. Másrészt az i. processzorhoz tartozó összes elem kisebb vagy egyenlő az i+1.-hez tartozó összes elemnél. Így minden processzor helyben végrehajt p irányú egyesítést, a részsorozatokból rendezett sorozatot adva. Így nem kell további p irányú egyesítés, az eredményeket a processzorszám sorrendjében kell egymás mellé helyezni.
Többsorozatos választás
A legegyszerűbb változatban p egyenlően p processzor közt elosztott rendezett sorozat, valamint k rang esetén a feladat x megtalálása, melynek globális rangja k az összes sorozatban. Ez felhasználható minden felosztására két részre egy adott felbontó indexnél, ahol az egyik rész csak x-nél kisebb, a másik csak x-nél nagyobb elemeket tartalmaz.
Az alábbi sorozatos algoritmus a szétválasztások indexeit adja ki, vagyis az -ket az sorozatokban, ahol globális rangja k-nál kisebb, és .[21]
algorithm msSelect(S : Array of sorted Sequences [S_1,..,S_p], k : int): for i = 1 to p: (l_i, r_i) = (0, |S_i|-1) while there exists i: l_i < r_i: // elem kijelölése S_j[l_j], .., S_j[r_j] közt, egyenlő eloszlású véletlen j választása v := pickPivot(S, l, r) for i = 1 to p: m_i = binarySearch(v, S_i[l_i, r_i]) // sorozatosan if m_1 + ... + m_p >= k: // m_1+ ... + m_p v globális rangja r := m // vektor-hozzárendelés else l := m return l
A komplexitáselemzéshez a PRAM modell választható. Ha az adat egyenlően oszlik el minden p-nél, a binarySearch p-szeri végrehajtásának futásideje A várható ismétlési mélység ahogy a gyors választásnál is. Így a teljes várható futásidő
Párhuzamos többirányú összefésüléses rendezésre alkalmazva az algoritmusnak párhuzamosan kell futnia, hogy minden rangú felezőelem, ahol egyidejűleg legyen megtalálható. Ezen elemek ezután minden sorozat p részre osztására felhasználható, az összes futásidő .
Pszeudokód
Alább a párhuzamos többirányú összefésüléses rendezés teljes pszeudokódja van, ha határszinkronizáció a többsorozatos választás előtt és után, így minden processzor meg tudja találni az elválasztó elemeket és a sorozatfelbontást.
/** * d: rendezetlen tömb * n: elemszám * p: processzorszám * return Sorted Array */ algorithm parallelMultiwayMergesort(d : Array, n : int, p : int): o := new Array[0, n] // kimeneti tömb for i = 1 to p in parallel: // minden processzor párhuzamosan S_i := d[(i-1) * n/p, i * n/p] // n/p hosszú sorozat sort(S_i) // lokális rendezés synch v_i := msSelect([S_1,...,S_p], i * n/p) // ni/p globális rangú elem synch (S_i,1, ..., S_i,p) := sequence_partitioning(si, v_1, ..., v_p) // s_i felbontása részsorozatokra o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i) // egyesítés és kimenethez rendelés return o
Elemzés
Először minden processzor rendezi a hozzá tartozó elemet komplexitású algoritmussal. Ezután az elválasztóelemeket kiszámítják idő alatt. Végül minden p tagú elemet párhuzamosan egyesítik a processzorok idő alatt sorozatos p irányú egyesítéssel. Így a futásidő
Gyakorlati használata
A többirányú összefésüléses rendezés nagy párhuzamosíthatósága miatt nagyon skálázható, lehetővé téve sok processzor használatát. Ez lehetőséget ad nagy mennyiségű adat rendezésére, például számítógépklaszterek esetén. Mivel az ilyen rendszerekben a memória jellemzően nem korlátozó tényező, az összefésüléses rendezés helykomplexitásbeli hátránya elhanyagolható. Azonban más tényezők fontosak az ilyen rendszerekben, melyeket nem vesznek figyelembe PRAM modellnél. Például ilyen tényezők a memóriahierarchia, a gyorsítótárban el nem férő adat és a processzorok közti adatcsere során fellépő kommunikációs költségek, melyek korlátozó tényezők lehetnek, ha közös memórián már nem érhetők el az adatok.
Sanders et al. tömeges szinkronpárhuzamos algoritmust mutattak be többszintű többirányú összefésüléses rendezésre, mely p processzort méretű csoportra bont. A processzorok először helyben rendeznek. Szemben az egyszintű többirányú összefésüléses rendezéssel, e sorozatok r részre vannak osztva, és a megfelelő processzoorcsoportokhoz kerülnek. E folyamat ismétlődik e csoportokban, csökkentve a kommunikációt és elkerülve a sok kis üzenet okozta problémát. A valós hálózat szerkezete használható a processzorcsoportok meghatározására.[20]
További változatok
Az összefésüléses rendezés volt az egyik első rendezési algoritmus optimális gyorsítással. Richard Cole alminta-algoritmust használt idejű összefésüléshez.[22] Más párhuzamos rendezési algoritmusok hasonló vagy jobb időkorlátokat tudnak elérni alacsonyabb konstansokkal. Például 1991-ben David Powers párhuzamosított gyors rendezést és ehhez kapcsolódó gyökrendezést írt le, mely idő alatt tudott futni CRCW PRAM-on n processzorral implicit felosztással.[23] Powers kimutatta, hogy Batcher biton rendezésének csatornázott változatának futásideje pillangó-rendezőhálózaton, ami azonban a gyakorlatban gyorsabb, mint az rendezés PRAM-on, és részletesen leírja a rejtett költségeket az összehasonlítás, a gyök- és a párhuzamos rendezés esetén.[24]
Összehasonlítás más rendezésekkel
A Perl 5.8-ban az összefésüléses rendezés lett az alapértelmezett rendezőalgoritmus a gyors rendezés után.[25] In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted.[26] The Linux kernel uses merge sort for its linked lists.[27] A Python Tim-rendezést használ, mely az összefésüléses és a beillesztéses rendezés keveréke, ezenkívül a Java SE 7 (nem primitív típusú tömböknél),[28] az Android[29] és a GNU Octave alapértelmezett rendezőalgoritmusa lett.[30]
Jegyzetek
- ↑ (Skiena 2008, p. 122)
- ↑ (1997. március 1.) „A meticulous analysis of mergesort programs”. Italian Conference on Algorithms and Complexity: 217–228. doi:10.1007/3-540-62592-5_74.
- ↑ (Cormen et al. 2009, p. 36)
- ↑ A legrosszabb esetben szereplő szám nem egyezik Donald Knuth Art of Computer Programming című könyvének 3. kötetével. Ennek oka, hogy Knuth egy kissé gyengébb összefésülésesrendezés-változatot elemez.
- ↑ a b Data structure using C++. Firewall Media (2007). ISBN 978-81-318-0020-1. OCLC 849900742
- ↑ (Cormen et al. 2009, p. 151)
- ↑ (1983) „DCS Technical Report 8313”, Kiadó: Department of Computer Science, University of New South Wales.
- ↑ WikiSort. Fast and stable sort algorithm that uses O(1) memory. Public domain.. GitHub , 2014. április 14.
- ↑ (2014) „Patience is a Virtue: Revisiting Merge and Sort on Modern Processors”. SIGMOD/PODS.
- ↑ a b Quadsort is a branchless stable adaptive merge sort.. GitHub , 2022. június 8.
- ↑ (Katajainen, Pasanen & Teuhola 1996)
- ↑ (2000) „Asymptotically efficient in-place merging”. Theoretical Computer Science 237 (1–2), 159–181. o. DOI:10.1016/S0304-3975(98)00162-5.
- ↑ (1988. március 1.) „Practical In-Place Merging”. Communications of the ACM 31 (3), 348–352. o. DOI:10.1145/42392.42403.
- ↑ (2004) „Algorithms – ESA 2004”. European Symp. Algorithms 3221. doi:10.1007/978-3-540-30140-0_63.
- ↑ (2003. szeptember 1.) „A New Method for Efficient in-Place Merging”. Proceedings of the Korean Institute of Intelligent Systems Conference, 392–394. o.
- ↑ Ferragina, Paolo. 5. Sorting Atomic Items, The magic of Algorithms!, 5-4. o. (2019)
- ↑ a b (Cormen et al. 2009, pp. 797–805)
- ↑ Victor J. Duvanenko: „Parallel Merge Sort”, Dr. Dobb's Journal & blog [1] és C++-megvalósítás repozitóriuma [2]
- ↑ Lecture: Parallel algorithms, 2008. [2020. január 9-i dátummal az eredetiből archiválva]. (Hozzáférés: 2020. május 2.)
- ↑ a b Practical Massively Parallel Sorting, Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures, 13–23. o.. DOI: 10.1145/2755573.2755595 (2015). ISBN 9781450335881
- ↑ Peter Sanders: Lecture Parallel algorithms', 2019 (Hozzáférés: 2020. május 2.)
- ↑ (1988. augusztus 1.) „Parallel merge sort”. SIAM J. Comput. 17 (4), 770–785. o. DOI:10.1137/0217049.
- ↑ Powers, David M. W.. Parallelized Quicksort and Radixsort with Optimal Speedup, Proceedings of International Conference on Parallel Computing Technologies, Novosibirsk (1991)
- ↑ Powers, David M. W. (1995. január 1.). „Parallel Unification: Practical Complexity”. Australasian Computer Architecture Workshop Flinders University.
- ↑ Sort – Perl 5 version 8.8 documentation. (Hozzáférés: 2020. augusztus 23.)
- ↑ coleenp: src/java.base/share/classes/java/util/Arrays.java @ 53904:9c3fe09f69bc. OpenJDK, 2019. február 22.
- ↑ linux kernel /lib/list_sort.c
- ↑ jjb: Commit 6804124: Replace "modified mergesort" in java.util.Arrays.sort with timsort. Java Development Kit 7 Hg repo, 2009. július 29. [2018. január 26-i dátummal az eredetiből archiválva]. (Hozzáférés: 2011. február 24.)
- ↑ Class: java.util.TimSort<T>. Android JDK Documentation. [2015. január 20-i dátummal az eredetiből archiválva]. (Hozzáférés: 2015. január 19.)
- ↑ liboctave/util/oct-sort.cc. Mercurial repository of Octave source code. (Hozzáférés: 2013. február 18.) „Code stolen in large part from Python's, listobject.c, which itself had no license header. However, thanks to Tim Peters for the parts of the code I ripped-off.”
Fordítás
Ez a szócikk részben vagy egészben a Merge sort című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Források
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
- Katajainen (1996). „Practical in-place mergesort”. Nordic Journal of Computing 3 (1), 27–40. o. [2011. augusztus 7-i dátummal az eredetiből archiválva]. ISSN 1236-6064. (Hozzáférés: 2009. április 4.) . Also Practical In-Place Mergesort. Also [3]
- Knuth, Donald. Section 5.2.4: Sorting by Merging, Sorting and Searching, 2nd, The Art of Computer Programming, Addison-Wesley, 158–168. o. (1998). ISBN 0-201-89685-0
- Kronrod (1969). „Optimal ordering algorithm without operational field”. Soviet Mathematics - Doklady 10, 744. o.
- LaMarca (1997). „The influence of caches on the performance of sorting”. Proc. 8th Ann. ACM-SIAM Symp. On Discrete Algorithms (SODA97), 370–379. o.
- Skiena, Steven S.. 4.5: Mergesort: Sorting by Divide-and-Conquer, The Algorithm Design Manual, 2nd, Springer, 120–125. o. (2008). ISBN 978-1-84800-069-8
- Sun Microsystems: Arrays API (Java SE 6). (Hozzáférés: 2007. november 19.)
- Oracle Corp.: Arrays (Java SE 10 & JDK 10). (Hozzáférés: 2018. július 23.)
További információk
- Animated Sorting Algorithms: Merge Sort a Wayback Machine-ben (archiválva 2015. március 6-i dátummal) – grafikus bemutató
- Open Data Structures - 11.1.1. szakasz - Merge Sort, Pat Morin