Az összevonás az egyik alapvető számítástechnikai algoritmus, amelyet a nagy matematikus, John von Neumann fogalmazott meg még 1945-ben. A Manhattan Projectben való részvétel során Neumann szembesült azzal, hogy hatalmas mennyiségű adatot kell hatékonyan feldolgozni. Az általa kidolgozott módszer az „oszd meg és uralkodj” elvét alkalmazta, ami jelentősen csökkentette a munkához szükséges időt.
Az algoritmus elve és használata
Az egyesített rendezési módszert olyan struktúrák rendezésének problémáinál használják, amelyek hozzáférést rendeltek el az elemekhez, például tömbökhöz, listákhoz, adatfolyamokhoz.
A feldolgozás során a kezdeti adatblokk kis komponensekre van felosztva, legfeljebb egy elemre, ami valójában már egy rendezett lista. Ezután a megfelelő sorrendben össze kell szerelni.
Egy bizonyos hosszúságú tömb rendezéséhez további, azonos méretű memóriaterületre van szükség, amelybe a rendezett tömb részenként kerül összegyűjtésre.
A módszer használható bármilyen összehasonlítható adattípus, például számok vagy karakterláncok rendezésére.
Egyesítés rendezvetelkek
Az algoritmus megértéséhez kezdjük az elemzést a végéről – a rendezett blokkok egyesítésének mechanizmusától.
Képzeljük el, hogy van két tetszőleges módon rendezett számtömbünk, amelyeket kombinálni kell egymással, hogy a rendezés ne szakadjon meg. Az egyszerűség kedvéért a számokat növekvő sorrendbe rendezzük.
Elemi példa: mindkét tömb egy-egy elemből áll.
int arr1={31}; int arr2={18};
Egyesítésükhöz vegyük az első tömb nulla elemét (ne felejtsük el, hogy a számozás nulláról indul), és a második tömb nulla elemét. Ezek rendre 31, illetve 18. A rendezési feltétel szerint a 18-as szám legyen az első, mivel ez kevesebb. Csak tegye a számokat a megfelelő sorrendbe:
int eredmény={18, 31};
Nézzünk egy bonyolultabb példát, ahol minden tömb több elemből áll:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Az összevonási algoritmus a kisebb elemek egymás utáni összehasonlításából áll, és a megfelelő sorrendben a kapott tömbbe helyezi őket. Az aktuális indexek nyomon követéséhez vezessünk be két változót - az index1-et és az index2-t. Kezdetben nullára állítjuk őket, mivel a tömbök rendezve vannak, és a legkisebb elemek az elején vannak.
int index1=0; int index2=0;
Írjuk meg lépésről lépésre a teljes összevonási folyamatot:
- Vegyük ki az index1 elemet az arr1 tömbből, és az index2 elemet az arr2 tömbből.
- Hasonlítsa össze, válassza ki közülük a legkisebbet, és helyezze beeredményül kapott tömb.
- Növelje a kisebb elem aktuális indexét 1-gyel.
- Folytatás az első lépéstől.
Az első pályán a helyzet így fog kinézni:
index1=0; index2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; index1++; eredmény[0]=arr1[0]; // eredmény=[2]
A második kanyarban:
index1=1; index2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; index2++; eredmény[1]=arr2[0]; // eredmény=[2, 5]
Harmadik:
index1=1; index2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; index2++; eredmény[2]=arr2[1]; // eredmény=[2, 5, 6]
És így tovább, amíg az eredmény egy teljesen rendezett tömb nem lesz: {2, 5, 6, 17, 21, 19, 30, 45}.
Bizonyos nehézségek adódhatnak, ha különböző hosszúságú tömböket egyesítenek. Mi van akkor, ha az egyik aktuális index elérte az utolsó elemet, és még vannak tagok a második tömbben?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 lépés index1=0, index2=0; 1 2 eredmény={1, 2}; // 3 lépés index1=1, index2=1; 4 < 5 eredmény={1, 2, 4}; //4 lépés index1=2, index2=1 ??
Az index1 változó elérte a 2 értéket, de az arr1 tömbnek nincs ilyen indexű eleme. Itt minden egyszerű: csak vigye át a második tömb többi elemét az eredményül kapottba, megőrizve sorrendjüket.
eredmény={1, 2, 4, 5, 6, 7, 9};
Ez a helyzet azt jelzi számunkra, hogy szükség van ráegyeztesse az aktuális ellenőrző indexet az egyesítendő tömb hosszával.
Séma egyesítése a különböző hosszúságú rendezett sorozatokhoz (A és B):
- Ha mindkét sorozat hossza nagyobb, mint 0, hasonlítsa össze A[0]-t és B[0]-t, és helyezze át a kisebbet a pufferbe.
- Ha az egyik sorozat hossza 0, vegye ki a második sorozat többi elemét, és sorrendjének megváltoztatása nélkül lépjen a puffer végére.
A második szakasz megvalósítása
Alább látható egy példa két rendezett tömb összekapcsolására Java nyelven.
int a1=új int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=új int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=new int[a1.length + a2.length]; int i=0, j=0; for (int k=0; k a1.hossz-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=a; i++; } else if (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } else { int b=a2[j]; a3[k]=b; j++; } }
Itt:
- a1 és a2 az összevonandó eredeti rendezett tömbök;
- a3 – végső tömb;
- i és j az a1 és a2 tömbök aktuális elemeinek indexei.
Az első és a második if-feltétel biztosítja, hogy az indexek ne lépjék túl a tömb méretét. A harmadik és negyedik feltételblokk a kisebb elem eredményül kapott tömbjébe kerül.
Oszd meg és uralkodj
Tehát, megtanultuk egyesíteni a rendezetteketértékgyűjtemények. Elmondható, hogy az összevonási rendezési algoritmus második része - maga az összevonás - már rendezve van.
Azonban még mindig meg kell értened, hogyan juthatsz el az eredeti rendezetlen számtömbből több rendezett számhoz, amelyek összevonhatók.
Vegyük fontolóra az algoritmus első szakaszát, és tanuljuk meg a tömbök szétválasztását.
Ez nem nehéz – az eredeti értéklistát ketté kell osztani, majd mindegyik részt kettéosztjuk, és így tovább, amíg nagyon kis blokkokat nem kapunk.
Az ilyen minimális elemek hossza egyenlő lehet eggyel, azaz maguk is lehetnek rendezett tömbök, de ez nem szükséges feltétel. A blokk mérete előre meghatározásra kerül, és bármilyen megfelelő rendezési algoritmus használható, amely hatékonyan működik kis méretű tömbökkel (például gyorsrendezés vagy beillesztési rendezés).
Így néz ki.
// eredeti tömb {34, 95, 10, 2, 102, 70}; // első felosztás: {34, 95, 10} és {2, 102, 70}; // másodperc felosztása {34} és {95, 10} és {2} és {102, 70}
A kapott, 1-2 elemből álló blokkok nagyon könnyen elrendezhetők.
Ezek után páronként össze kell vonni a már rendezett kis tömböket, megőrizve a tagok sorrendjét, amit már megtanultunk.
Az első szakasz megvalósítása
Egy tömb rekurzív particionálása az alábbiakban látható.
void mergeSort(T a, long start, long finish) { long split; ha(kezdet < cél) { split=(rajt + cél)/2; mergeSort(a, start, split); mergeSort(a, felosztás+1, befejezés); merge(a, start, split, finish); } }
Mi történik ebben a kódban:
-
A mergeSort függvény lekéri a kezdeti
a
tömböt, valamint a rendezendő régió bal és jobb oldali határát (az indexek start és
- befejezés).
-
Ha ennek a szakasznak a hossza egynél nagyobb (
start < finish
), akkor két részre van osztva (
- split index szerint), és mindegyik rekurzívan van rendezve.
-
A bal oldali rekurzív függvényhívásban a diagram kezdő indexe és a
split
index átadásra kerül. A jobb oldalinál az eleje
- (split + 1), a vége pedig az eredeti szakasz utolsó indexe.
-
A
merge
függvény két rendezett sorozatot kap (
a[start]…a[split]
és
- a[split +1]…a[finish]), és rendezési sorrendben egyesíti őket.
Az összevonási funkció mechanikáját fentebb tárgy altuk.
Az algoritmus általános sémája
Az egyesítési rendezési tömb módszer két nagy lépésből áll:
- Vasd fel a rendezetlen eredeti tömböt apró darabokra.
- Gyűjtsd össze párban a rendezési szabályt követve.
Egy nagy és összetett feladat sok egyszerű feladatra oszlik, amelyeket egymás után oldanak meg, ami a kívánt eredményhez vezet.
A módszer értékelése
Az összevonási rendezés időbeli összetettségét a felosztott fa magassága határozza megalgoritmus, és egyenlő a tömb elemeinek számával (n) szorozva a logaritmusával (log n). Az ilyen becslést logaritmikusnak nevezik.
Ez a módszer előnye és hátránya is. Futási ideje a legrosszabb esetben sem változik, ha az eredeti tömb fordított sorrendben van rendezve. Teljesen rendezett adatok feldolgozásakor azonban az algoritmus nem biztosít időnövekedést.
Fontos megjegyezni az összevonási rendezési módszer memóriaköltségét is. Ezek megegyeznek az eredeti gyűjtemény méretével. Ezen a kiegészítőleg kiosztott területen egy rendezett tömb kerül összeállításra a darabokból.
Az algoritmus megvalósítása
A Pascal összevonási rendezés lent látható.
Procedure MergeSort(név: string; var f: szöveg); Var a1, a2, s, i, j, kol, tmp: egész szám; f1, f2: szöveg; b: logikai érték Begincol:=0; Hozzárendelés(f, név); reset(f); Bár az EOF(f) nem, de kezdődik az read(f, a1); inc(col); vége; bezár(f); Assign(f1, '{1. segédfájl neve}'); Assign(f2, '{2. segédfájl neve}'); s:=1; Míg (s<kol) elkezdődik a Reset(f); átír(f1); átír(f2); Az i:=1-hez a kol div 2-hez kezdje a Read(f, a1); Write(f1, a1, ' '); vége; Ha (kol div 2) mod s0 akkor kezdődik tmp:=kol div 2; Míg a tmp mod s0 elkezdi a Read(f, a1); Write(f1, a1, ' '); inc(tmp); vége; vége; Bár az EOF(f) nem, de elkezdődik a Read(f, a2); Write(f2, a2, ' '); vége; bezár(f); bezár(f1); bezár(f2); átír(f); reset(f1); reset(f2); Read(f1, a1); Read(f2, a2); Míg (nem EOF(f1)) és (nem EOF(f2)) kezdődik i:=0; j:=0; b:=igaz; Míg (b) és (nem EOF(f1)) és (nem EOF(f2)) kezdődik Ha (a1<a2), akkor kezdődikWrite(f, a1, ' '); Read(f1, a1); inc(i); End else begin Write(f, a2, ' '); Read(f2, a2); inc(j); vége; Ha (i=s) vagy (j=s), akkor b:=hamis; vége; Ha nem b, akkor kezdődik While (i<s) és (nem EOF(f1)) kezdje Write(f, a1, ' '); Read(f1, a1); inc(i); vége; Míg (j<s) és (nem EOF(f2)) megkezdődik a Write(f, a2, ' '); Read(f2, a2); inc(j); vége; vége; vége; Bár az EOF(f1) nem, kezdődik a tmp:=a1; Read(f1, a1); Ha nem EOF(f1), akkor Write(f, tmp, ' ') else Write(f, tmp); vége; Noha nem, az EOF(f2) kezdődik tmp:=a2; Read(f2, a2); Ha nem EOF(f2), akkor Write(f, tmp, ' ') else Write(f, tmp); vége; bezár(f); bezár(f1); bezár(f2); s:=s2; vége; Törlés(f1); Törlés(f2); vége;
Vizuálisan így néz ki az algoritmus működése (felső - rendezetlen sorrend, lent - rendezett).
Külső adatrendezés
Nagyon gyakran van szükség a számítógép külső memóriájában található adatok rendezésére. Egyes esetekben lenyűgöző méretűek, és nem helyezhetők el a RAM-ban, hogy megkönnyítsék a hozzáférést. Ilyen esetekben külső rendezési módszereket alkalmaznak.
A külső adathordozóhoz való hozzáférés szükségessége csökkenti a feldolgozási idő hatékonyságát.
A munka bonyolultsága abban rejlik, hogy az algoritmus egyszerre csak az adatfolyam egy eleméhez férhet hozzá. És ebben az esetben az egyik legjobb eredményt az összevonási rendezési módszer mutatja, amely képes egymás után két fájl elemeit egymás után összehasonlítani.
Adatok olvasása innenkülső forrás, ezek feldolgozása és a végleges fájlba írása rendezett blokkokban (sorozatokban) történik. A rendezett sorozatok méretével való munkamódszer szerint kétféle rendezés létezik: egyszerű és természetes összevonás.
Egyszerű összevonás
Egyszerű egyesítéssel a sorozat hossza rögzített.
Így az eredeti rendezetlen fájlban minden sorozat egy elemből áll. Az első lépés után a méret kettőre nő. Következő - 4, 8, 16 és így tovább.
Ez így működik:
- A forrásfájl (f) két segédfájlra van osztva - f1, f2.
- Ezeket ismét egy fájlba egyesítik (f), ugyanakkor az összes elemet páronként és párokat alkotva hasonlítják össze. A sorozat mérete ennél a lépésnél kettő lesz.
- Az 1. lépés megismétlődik.
- A 2. lépés megismétlődik, de a már rendezett 2-esek összevonva rendezett 4-eket alkotnak.
- A ciklus folytatódik, növelve a sorozatot minden iterációnál, amíg a teljes fájl rendezve lesz.
Honnan tudja, hogy az egyszerű egyesítéssel végzett külső rendezés befejeződött?
- új sorozat hossza (egyesítés után) nem kevesebb, mint az elemek teljes száma;
- már csak egy epizód van hátra;
- Az f2 segédfájl üresen maradt.
Az egyszerű összevonás hátrányai a következők: mivel a futási hossz minden egyes összevonásnál rögzített, a részben rendezett adatok feldolgozása annyi ideig tart, mint a teljesen véletlenszerű adatoké.
Természetes fúzió
Ez a módszer nem korlátozza a hossztsorozat, de a lehető legtöbbet választja.
Rendezési algoritmus:
- A kezdeti sorozat beolvasása az f fájlból. Az első fogadott elem az f1. fájlba kerül.
- Ha a következő bejegyzés teljesíti a rendezési feltételt, akkor oda kerül, ha nem, akkor a második segédfájlba f2.
- Ily módon a forrásfájl összes rekordja elosztásra kerül, és az f1-ben egy rendezett sorozat jön létre, amely meghatározza a sorozat aktuális méretét.
- Az f1 és f2 fájlok egyesítve.
- A ciklus megismétlődik.
A sorozat nem rögzített mérete miatt szükséges a sorozat végét speciális karakterrel jelölni. Emiatt az összevonáskor megnő az összehasonlítások száma. Ezenkívül az egyik segédfájl mérete megközelítheti az eredeti méretét.
Átlagosan a természetes összevonás hatékonyabb, mint az egyszerű egyesítés külső rendezéssel.
Az algoritmus jellemzői
Két azonos érték összehasonlításakor a módszer megőrzi azok eredeti sorrendjét, azaz stabil.
A rendezési folyamat nagyon sikeresen felosztható több szálra.
A videó egyértelműen bemutatja az összevonási rendezési algoritmus működését.
