Ühenda sorteerimine on üks arvutiteaduse põhialgoritme, mille sõnastas 1945. aastal suur matemaatik John von Neumann. Manhattani projektis osaledes seisis Neumann silmitsi vajadusega töödelda tõhus alt tohutuid andmehulki. Tema väljatöötatud meetodis kasutati "jaga ja valluta" põhimõtet, mis vähendas oluliselt tööks kuluvat aega.
Algoritmi põhimõte ja kasutamine
Ühendamissortimismeetodit kasutatakse selliste struktuuride sortimisel, mis on tellinud juurdepääsu elementidele, nagu massiivid, loendid, vood.
Töötlemise käigus jagatakse algandmeplokk väikesteks komponentideks, kuni üheks elemendiks, mis tegelikult on juba sorteeritud loend. Seejärel pannakse see õiges järjekorras uuesti kokku.
Teatud pikkusega massiivi sortimiseks on vaja sama suurusega täiendavat mäluala, kuhu sorteeritud massiiv kogutakse osade kaupa.
Meetodit saab kasutada mis tahes võrreldava andmetüübi (nt numbrid või stringid) järjestamiseks.
Liida sorteeritudkrundid
Algoritmi mõistmiseks alustame selle analüüsi lõpust – sorteeritud plokkide liitmise mehhanismist.
Kujutame ette, et meil on kaks mis tahes viisil sorteeritud arvude massiivi, mida tuleb omavahel kombineerida, et sorteerimine ei katkeks. Lihtsuse huvides sorteerime numbrid kasvavas järjekorras.
Elementaarne näide: mõlemad massiivid koosnevad ühest elemendist.
int arr1={31}; int arr2={18};
Nende ühendamiseks tuleb võtta esimese massiivi nullelement (ärge unustage, et nummerdamine algab nullist) ja teise massiivi nullelement. Need on vastav alt 31 ja 18. Vastav alt sorteerimistingimustele peaks number 18 olema esikohal, kuna see on väiksem. Lihts alt pange numbrid õigesse järjekorda:
int tulemus={18, 31};
Vaatame keerulisemat näidet, kus iga massiiv koosneb mitmest elemendist:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Ühendamisalgoritm koosneb väiksemate elementide järjestikusest võrdlemisest ja nende paigutamisest saadud massiivi õiges järjekorras. Praeguste indeksite jälgimiseks toome sisse kaks muutujat – indeks1 ja indeks2. Algselt määrame need nulliks, kuna massiivid on sorteeritud ja väikseimad elemendid on alguses.
int indeks1=0; int indeks2=0;
Paneme kogu liitmisprotsessi samm-sammult kirja:
- Võtke element indeksiga 1 massiivist arr1 ja element indeksiga 2 massiivist arr2.
- Võrdle, valige neist väikseim ja sisestagetulemuseks massiiv.
- Suurendage väiksema elemendi praegust indeksit 1 võrra.
- Jätkake esimesest sammust.
Esimesel orbiidil näeb olukord välja järgmine:
indeks1=0; indeks2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; indeks1++; tulemus[0]=arr1[0]; // tulemus=[2]
Teisel pöördel:
indeks1=1; indeks2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; indeks2++; tulemus[1]=arr2[0]; // tulemus=[2, 5]
Kolmas:
indeks1=1; indeks2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; indeks2++; tulemus[2]=arr2[1]; // tulemus=[2, 5, 6]
Ja nii edasi, kuni tulemuseks on täielikult sorteeritud massiiv: {2, 5, 6, 17, 21, 19, 30, 45}.
Erineva pikkusega massiivide liitmisel võivad tekkida teatud raskused. Mis siis, kui üks praegustest indeksidest on jõudnud viimase elemendini ja teises massiivis on veel liikmeid?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 samm indeks1=0, indeks2=0; 1 2 tulemus={1, 2}; // 3 sammu indeks1=1, indeks2=1; 4 < 5 tulemus={1, 2, 4}; //4 sammu indeks1=2, indeks2=1 ??
Muutuja index1 on jõudnud väärtuseni 2, kuid massiivi arr1 ei ole selle indeksiga elementi. Siin on kõik lihtne: lihts alt teisaldage teise massiivi ülejäänud elemendid saadud elemendile, säilitades nende järjestuse.
tulemus={1, 2, 4, 5, 6, 7, 9};
See olukord näitab meile vajadustsobitage praegune kontrollindeks liidetava massiivi pikkusega.
Ühenda skeem erineva pikkusega järjestatud järjestuste (A ja B) jaoks:
- Kui mõlema jada pikkus on suurem kui 0, võrrelge A[0] ja B[0] ning viige väiksem puhvrisse.
- Kui ühe jada pikkus on 0, võtke teise jada ülejäänud elemendid ja liikuge nende järjekorda muutmata puhvri lõppu.
Teise etapi rakendamine
Näide kahe sorteeritud massiivi ühendamisest Javas on toodud allpool.
int a1=uus int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=uus int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=uus int[a1.pikkus + a2.pikkus]; int i=0, j=0; for (int k=0; k a1.pikkus-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.pikkus-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++; } }
Siin:
- a1 ja a2 on liidetavad algsed sorteeritud massiivid;
- a3 – lõplik massiiv;
- i ja j on massiivi a1 ja a2 praeguste elementide indeksid.
Esimene ja teine if-tingimused tagavad, et indeksid ei ületa massiivi suurust. Vastav alt kolmas ja neljas tingimusplokk teisaldatakse saadud väiksema elemendi massiivi.
Jaga ja valluta
Niisiis, oleme õppinud sorteerituid liitmaväärtuste kogud. Võib öelda, et liitmissortimisalgoritmi teine osa – liitmine ise – on juba sorteeritud.
Siiski peate siiski mõistma, kuidas jõuda algsest sortimata numbrimassiivist mitme sorteeritud arvuni, mida saab liita.
Mõtleme algoritmi esimest etappi ja õpime, kuidas massiive eraldada.
See pole keeruline – esialgne väärtuste loend jagatakse pooleks, seejärel jagatakse ka iga osa kaheks ja nii edasi, kuni saadakse väga väikesed plokid.
Selliste minimaalsete elementide pikkus võib olla võrdne ühega, see tähendab, et nad võivad ise olla sorteeritud massiivi, kuid see pole vajalik tingimus. Ploki suurus määratakse eelnev alt kindlaks ja selle tellimiseks saab kasutada mis tahes sobivat sortimisalgoritmi, mis töötab tõhus alt väikese suurusega massiividega (nt kiirsortimine või sisestamise sortimine).
See näeb välja selline.
// algne massiiv {34, 95, 10, 2, 102, 70}; // esimene poolitamine {34, 95, 10} ja {2, 102, 70}; // sekundijaotus {34} ja {95, 10} ja {2} ja {102, 70}
Saadud 1-2 elemendist koosnevaid plokke on väga lihtne järjestada.
Pärast seda peate juba sorteeritud väikesed massiivid paarikaupa liitma, säilitades liikmete järjestuse, mida oleme juba õppinud tegema.
Esimese etapi rakendamine
Massiivi rekursiivne jaotus on näidatud allpool.
void mergeSort(T a, pikk algus, pikk lõpp) { long split; kui(start < finiš) { split=(start + finiš)/2; mergeSort(a, algus, split); mergeSort(a, split+1, finish); merge(a, start, split, finish); } }
Mis selles koodis juhtub:
-
Funktsioon mergeSort hangib esialgse massiivi
a
ning sortitava piirkonna vasaku ja parema piiri (indeksite algus ja
- finish).
-
Kui selle lõigu pikkus on suurem kui üks (
start < finish
), jagatakse see kaheks osaks (indeksiga
- split) ja igaüks neist sorteeritakse rekursiivselt.
-
Vasakpoolses rekursiivses funktsioonikutses edastatakse graafiku algusindeks ja indeks
split
. Parema jaotise algus on vastav alt
- (split + 1) ja lõpp on algse jaotise viimane indeks.
-
Funktsioon
merge
saab kaks järjestatud jada (
a[start]…a[split]
ja
- a[jagama +1]…a[finish]) ja liidab need sortimise järjekorras.
Ühendamisfunktsiooni mehaanikat käsitletakse eespool.
Algoritmi üldskeem
Ühendatud sortimismassiivi meetod koosneb kahest suurest etapist:
- Jagage sortimata algne massiiv väikesteks tükkideks.
- Koguge need paarikaupa, järgides sortimisreeglit.
Suur ja keeruline ülesanne jaotatakse paljudeks lihtsateks ülesanneteks, mis lahendatakse järjestikku, mis viib soovitud tulemuseni.
Meetodi hindamine
Liite sortimise ajalise keerukuse määrab poolitatud puu kõrgusalgoritmi ja võrdub massiivi elementide arvuga (n) korrutatuna selle logaritmiga (log n). Sellist hinnangut nimetatakse logaritmiliseks.
See on nii meetodi eelis kui ka puudus. Selle tööaeg ei muutu ka halvimal juhul, kui algne massiiv on järjestatud vastupidises järjekorras. Täielikult sorteeritud andmete töötlemisel ei anna algoritm aga ajavõitu.
Samuti on oluline tähele panna liitmissortimismeetodi mälukulu. Need on võrdsed originaalkogu suurusega. Sellel täiendav alt eraldatud alal koostatakse tükkidest sorteeritud massiiv.
Algoritmi rakendamine
Pascali liitmise sortimine on näidatud allpool.
Procedure MergeSort(nimi: string; var f: tekst); Var a1, a2, s, i, j, kol, tmp: täisarv; f1, f2: tekst; b: tõeväärtus Begincol:=0; Määra(f, nimi); lähtestamine(f); Kuigi EOF(f) mitte, alustab lugemist(f, a1); inc(col); lõpp; sulge(f); Assign(f1, '{1. abifaili nimi}'); Assign(f2, '{2. abifaili nimi}'); s:=1; Kuigi (s<kol) alustage Reset(f); ümber kirjutama(f1); ümber kirjutama(f2); For i:=1 kuni kol div 2 alustage Read(f, a1); Write(f1, a1, ' '); lõpp; Kui (kol div 2) mod s0, siis algab tmp:=kol div 2; Kuigi tmp mod s0 algab Read(f, a1); Write(f1, a1, ' '); inc(tmp); lõpp; lõpp; Kuigi mitte EOF(f), alustab Read(f, a2); Write(f2, a2, ' '); lõpp; sulge(f); sulge(f1); sulge(f2); ümber kirjutama(f); lähtestamine(f1); reset(f2); Loe(f1, a1); Loe(f2, a2); Kuigi (mitte EOF(f1)) ja (mitte EOF(f2)) algavad i:=0; j:=0; b:=tõene; Kuigi (b) ja (mitte EOF(f1)) ja (mitte EOF(f2)) algavad Kui (a1<a2), siis alustavadWrite(f, a1, ' '); Loe(f1, a1); inc(i); End else begin Write(f, a2, ' '); Loe(f2, a2); inc(j); lõpp; Kui (i=s) või (j=s), siis b:=vale; lõpp; Kui mitte b, siis alusta While (i<s) ja (mitte EOF(f1)) alusta Write(f, a1, ' '); Loe(f1, a1); inc(i); lõpp; Kuigi (j<s) ja (mitte EOF(f2)) algavad Write(f, a2, ' '); Loe(f2, a2); inc(j); lõpp; lõpp; lõpp; Kuigi mitte EOF(f1), algab tmp:=a1; Loe(f1, a1); Kui mitte EOF(f1), siis Write(f, tmp, ' ') else Write(f, tmp); lõpp; Kuigi mitte EOF(f2), algab tmp:=a2; Loe(f2, a2); Kui mitte EOF(f2), siis Write(f, tmp, ' ') else Write(f, tmp); lõpp; sulge(f); sulge(f1); sulge(f2); s:=s2; lõpp; Kustuta(f1); Kustuta(f2); Lõpp;
Visuaalselt näeb algoritmi töö välja selline (ülemine - järjestamata järjestus, alumine - järjestatud).
Väline andmete sortimine
Väga sageli on vaja sortida mõningaid arvuti välismälus asuvaid andmeid. Mõnel juhul on need muljetavaldava suurusega ja neid ei saa neile juurdepääsu hõlbustamiseks RAM-i paigutada. Sellistel juhtudel kasutatakse väliseid sortimismeetodeid.
Vajadus juurdepääsuks välisele andmekandjale vähendab töötlemisaja tõhusust.
Töö keerukus seisneb selles, et algoritm pääseb korraga juurde ainult ühele andmevoo elemendile. Ja sel juhul näitab üht parimat tulemust liitmise sortimise meetod, mis võimaldab võrrelda kahe faili elemente järjestikku üksteise järel.
Andmete lugemine alatesvälisallikas, nende töötlemine ja lõppfaili kirjutamine toimub järjestatud plokkidena (seeriatena). Vastav alt tellitud seeriate suurusele töötamise viisile on sortimist kahte tüüpi: lihtne ja loomulik liitmine.
Lihtne liitmine
Lihtsa liitmise korral on seeria pikkus fikseeritud.
Seega koosnevad algses sortimata failis kõik seeriad ühest elemendist. Pärast esimest sammu suureneb suurus kaheni. Järgmine – 4, 8, 16 ja nii edasi.
See töötab järgmiselt:
- Lähtefail (f) on jagatud kaheks abifailiks - f1, f2.
- Need liidetakse jälle üheks failiks (f), kuid samal ajal võrreldakse kõiki elemente paarikaupa ja moodustatakse paare. Selles etapis saab seeria suuruseks kaks.
- 1. sammu korratakse.
- Sammu 2 korratakse, kuid juba tellitud 2-d liidetakse järjestatud 4-teks.
- Tsükkel jätkub, suurendades iga iteratsiooni seeriat, kuni kogu fail on sorteeritud.
Kuidas teate, et väline sortimine lihtsa liitmisega on lõppenud?
- uue seeria pikkus (pärast liitmist) mitte vähem kui elementide koguarv;
- ainult üks osa jäänud;
- Abifail f2 jäeti tühjaks.
Lihtsa liitmise miinused on järgmised: kuna töö pikkus on igal liitmiskäigul fikseeritud, võtab osaliselt järjestatud andmete töötlemine sama kaua aega kui täiesti juhuslike andmetega.
Looduslik sulandumine
See meetod ei piira pikkustseeria, kuid valib maksimaalse võimaliku.
Sortimisalgoritm:
- Algse jada lugemine failist f. Esimene vastuvõetud element kirjutatakse faili f1.
- Kui järgmine kirje rahuldab sorteerimistingimust, kirjutatakse see sinna, kui mitte, siis teise abifaili f2.
- Nii jaotatakse kõik lähtefaili kirjed laiali ja f1-s moodustatakse järjestatud jada, mis määrab seeria praeguse suuruse.
- Failid f1 ja f2 on liidetud.
- Tsükkel kordub.
Seda seeria fikseerimata suuruse tõttu on vaja jada lõppu märkida erimärgiga. Seetõttu suureneb liitmisel võrdluste arv. Lisaks võib ühe abifaili suurus olla ligilähedane originaali suurusele.
Keskmiselt on loomulik liitmine tõhusam kui lihtne liitmine välise sorteerimisega.
Algoritmi omadused
Kahte identset väärtust võrreldes säilitab meetod nende algse järjekorra, st on stabiilne.
Sortimisprotsessi saab väga eduk alt jagada mitmeks lõimeks.
Video demonstreerib selgelt liitmissortimisalgoritmi tööd.
