Yhdistäminen on yksi tietojenkäsittelytieteen perusalgoritmeista, jonka suuri matemaatikko John von Neumann muotoili vuonna 1945. Osallistuessaan Manhattan-projektiin Neumann kohtasi tarpeen käsitellä tehokkaasti v altavia tietomääriä. Hänen kehittämässään menetelmässä käytettiin "hajota ja hallitse" -periaatetta, mikä lyhensi huomattavasti työntekoon kuluvaa aikaa.
Algoritmin periaate ja käyttö
Yhdistetty lajittelumenetelmää käytetään lajitteluongelmissa, jotka liittyvät elementteihin, kuten taulukoihin, luetteloihin, viroihin, saaneiden rakenteiden lajitteluun.
Prosessoinnin aikana alkutietolohko jaetaan pieniin osiin, enintään yhteen elementtiin, joka itse asiassa on jo lajiteltu luettelo. Sitten se kootaan uudelleen oikeassa järjestyksessä.
Tietyn pituisen taulukon lajitteleminen vaatii samankokoisen lisämuistialueen, johon lajiteltu matriisi kerätään osissa.
Menetelmää voidaan käyttää minkä tahansa vertailukelpoisen tietotyypin, kuten numeroiden tai merkkijonojen, tilaamiseen.
Yhdistäminen lajiteltujuonet
Algoritmin ymmärtämiseksi aloitetaan sen analyysi lopusta - lajiteltujen lohkojen yhdistämismekanismista.
Kuvitellaan, että meillä on kaksi jollain tavalla lajiteltua numerotaulukkoa, jotka on yhdistettävä keskenään, jotta lajittelu ei katkea. Yksinkertaisuuden vuoksi lajittelemme numerot nousevaan järjestykseen.
Perusesimerkki: molemmat taulukot koostuvat yhdestä elementistä kumpikin.
int arr1={31}; int arr2={18};
Jos haluat yhdistää ne, sinun on otettava ensimmäisen taulukon nollaelementti (älä unohda, että numerointi alkaa nollasta) ja toisen taulukon nollaelementti. Nämä ovat vastaavasti 31 ja 18. Lajitteluehdon mukaan numero 18 tulee olla ensin, koska se on pienempi. Aseta vain numerot oikeaan järjestykseen:
int tulos={18, 31};
Katsotaan monimutkaisempi esimerkki, jossa jokainen taulukko koostuu useista elementeistä:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Yhdistysalgoritmi koostuu pienten elementtien peräkkäisestä vertailusta ja niiden sijoittamisesta tuloksena olevaan taulukkoon oikeassa järjestyksessä. Nykyisten indeksien seuraamiseksi otetaan käyttöön kaksi muuttujaa - index1 ja index2. Aluksi asetamme ne nollaan, koska taulukot lajitellaan ja pienimmät elementit ovat alussa.
int index1=0; int index2=0;
Kirjoitetaan koko yhdistämisprosessi askel askeleelta:
- Ota elementti indeksillä1 taulukosta arr1 ja elementti, jolla on indeksi2 taulukosta arr2.
- Vertaa, valitse niistä pienin ja laitatuloksena oleva taulukko.
- Kasvata pienemmän elementin nykyistä indeksiä 1:llä.
- Jatka ensimmäisestä vaiheesta.
Ensimmäisellä kiertoradalla tilanne näyttää tältä:
indeksi1=0; indeksi2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; index1++; tulos[0]=arr1[0]; // tulos=[2]
Toisella käännöksellä:
indeksi1=1; indeksi2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; index2++; tulos[1]=arr2[0]; // tulos=[2, 5]
Kolmas:
indeksi1=1; indeksi2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; index2++; tulos[2]=arr2[1]; // tulos=[2, 5, 6]
Ja niin edelleen, kunnes tuloksena on täysin lajiteltu taulukko: {2, 5, 6, 17, 21, 19, 30, 45}.
Joitain vaikeuksia voi ilmetä, jos eripituisia taulukoita yhdistetään. Entä jos jokin nykyisistä indekseistä on saavuttanut viimeisen elementin ja toisessa taulukossa on vielä jäseniä jäljellä?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 askel indeksi1=0, indeksi2=0; 1 2 tulos={1, 2}; // 3 askelta indeksi1=1, indeksi2=1; 4 < 5 tulos={1, 2, 4}; //4 askel indeksi1=2, indeksi2=1 ??
Indeksi1-muuttuja on saavuttanut arvon 2, mutta arr1-taulukossa ei ole elementtiä tällä indeksillä. Täällä kaikki on yksinkertaista: siirrä vain toisen taulukon loput elementit tuloksena olevaan taulukkoon säilyttäen niiden järjestyksen.
tulos={1, 2, 4, 5, 6, 7, 9};
Tämä tilanne osoittaa meille tarpeentäsmää nykyinen tarkistusindeksi yhdistettävän taulukon pituuteen.
Yhdistä kaavio eripituisille järjestetyille sarjoille (A ja B):
- Jos molempien sekvenssien pituus on suurempi kuin 0, vertaa A[0] ja B[0] ja siirrä pienempi puskuriin.
- Jos yhden sekvenssin pituus on 0, ota toisen sekvenssin loput elementit ja siirry puskurin loppuun muuttamatta niiden järjestystä.
Toisen vaiheen toteutus
Alla on esimerkki kahden järjestetyn taulukon yhdistämisestä Javassa.
int a1=uusi int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=uusi int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=uusi int[a1.length + a2.length]; int i=0, j=0; for (int k=0; k a1.length-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++; } }
Tässä:
- a1 ja a2 ovat alkuperäiset yhdistettävät lajitellut taulukot;
- a3 – viimeinen taulukko;
- i ja j ovat taulukoiden a1 ja a2 nykyisten elementtien indeksejä.
Ensimmäinen ja toinen if-ehto varmistavat, että indeksit eivät ylitä taulukon kokoa. Kolmas ja neljäs ehtolohko siirretään pienemmän elementin tuloksena olevaan taulukkoon.
Haja ja hallitse
Olemme siis oppineet yhdistämään lajitellutarvokokoelmia. Voidaan sanoa, että yhdistämislajittelualgoritmin toinen osa - itse yhdistäminen - on jo lajiteltu.
Sinun on kuitenkin vielä ymmärrettävä, kuinka pääset alkuperäisestä lajittelemattomasta numerojoukosta useisiin lajiteltuihin numeroihin, jotka voidaan yhdistää.
Katsotaanpa algoritmin ensimmäistä vaihetta ja opitaan erottamaan taulukoita.
Tämä ei ole vaikeaa - alkuperäinen arvoluettelo jaetaan kahtia, sitten jokainen osa on myös kaksihaarainen ja niin edelleen, kunnes saadaan hyvin pieniä lohkoja.
Tällaisten minimielementtien pituus voi olla yhtä suuri kuin yksi, eli ne voivat itse olla lajiteltu taulukko, mutta tämä ei ole välttämätön ehto. Lohkon koko määritetään etukäteen, ja sen tilaamiseen voidaan käyttää mitä tahansa sopivaa lajittelualgoritmia, joka toimii tehokkaasti pienikokoisten taulukoiden kanssa (esim. pikalajittelu tai lisäyslajittelu).
Se näyttää tältä.
// alkuperäinen taulukko {34, 95, 10, 2, 102, 70}; // ensimmäinen jako {34, 95, 10} ja {2, 102, 70}; // sekunnin jako {34} ja {95, 10} ja {2} ja {102, 70}
Tuodoksena 1-2 elementistä koostuvat lohkot on erittäin helppo järjestää.
Sen jälkeen sinun on yhdistettävä jo lajitellut pienet taulukot pareittain säilyttäen jäsenten järjestyksen, minkä olemme jo oppineet tekemään.
Ensimmäisen vaiheen toteutus
Matriisin rekursiivinen osiointi näkyy alla.
void mergeSort(T a, pitkä aloitus, pitkä loppu) { pitkä jako; jos(aloitus < maali) { split=(aloitus + maali)/2; mergeSort(a, aloita, jakaa); mergeSort(a, split+1, finish); merge(a, aloitus, split, lopeta); } }
Mitä tässä koodissa tapahtuu:
-
MergeSort-funktio saa alkutaulukon
a
ja lajiteltavan alueen vasemman ja oikean reunan (indeksit alkavat ja
- finish).
-
Jos tämän jakson pituus on suurempi kuin yksi (
aloitus < lopetus
), se jaetaan kahteen osaan (indeksillä
- split), ja jokainen lajitellaan rekursiivisesti.
-
Vasemman puolen rekursiivisessa funktiokutsussa käyrän aloitusindeksi ja indeksi
split
välitetään. Oikean osan alku on
- (split + 1) ja loppu on alkuperäisen osan viimeinen indeksi.
-
Function
merge
saa kaksi järjestettyä sekvenssiä (
a[aloitus]…a[split]
ja
- a[split +1]…a[finish]) ja yhdistää ne lajittelujärjestyksessä.
Yhdistystoiminnon mekaniikkaa käsitellään edellä.
Algoritmin yleinen kaavio
Yhdistetty lajittelutaulukko koostuu kahdesta suuresta vaiheesta:
- Jaa lajittelematon alkuperäinen matriisi pieniksi paloiksi.
- Kerää ne pareittain lajittelusäännön mukaisesti.
Suuri ja monimutkainen tehtävä jaetaan useisiin yksinkertaisiin, jotka ratkaistaan peräkkäin, mikä johtaa haluttuun tulokseen.
Menetelmän arviointi
Yhdistämisen aikamonimutkaisuus määräytyy jaetun puun korkeuden mukaanalgoritmi ja on yhtä suuri kuin taulukon elementtien lukumäärä (n) kertaa sen logaritmi (log n). Tällaista arviota kutsutaan logaritmiseksi.
Tämä on sekä menetelmän etu että haitta. Sen ajoaika ei muutu pahimmassakaan tapauksessa, kun alkuperäinen matriisi lajitellaan käänteisessä järjestyksessä. Täysin lajiteltua dataa käsiteltäessä algoritmi ei kuitenkaan anna aikavahvistusta.
On myös tärkeää huomata yhdistämislajittelumenetelmän muistikustannukset. Ne vastaavat alkuperäisen kokoelman kokoa. Tälle lisäksi varatulle alueelle kootaan osista lajiteltu matriisi.
Algoritmin toteutus
Pascal-yhdistelmälajittelu näkyy alla.
Procedure MergeSort(nimi: merkkijono; var f: teksti); Muutt a1, a2, s, i, j, kol, tmp: kokonaisluku; f1, f2: teksti; b: Boolen arvo Begincol:=0; Assign(f, nimi); reset(f); Vaikka ei EOF(f), aloita lukeminen(f, a1); inc(sara); loppu; sulje(f); Assign(f1, '{1. aputiedoston nimi}'); Assign(f2, '{2. aputiedoston nimi}'); s:=1; Vaikka (s<kol) aloita Reset(f); kirjoittaa uudelleen(f1); kirjoittaa uudelleen(f2); Jos i:=1 on kol div 2, aloita Read(f, a1); Write(f1, a1, ' '); loppu; Jos (kol div 2) mod s0 aloita tmp:=kol div 2; Vaikka tmp mod s0 alkaa Read(f, a1); Write(f1, a1, ' '); inc(tmp); loppu; loppu; Vaikka ei EOF(f), aloita Read(f, a2); Write(f2, a2, ' '); loppu; sulje(f); sulje(f1); sulje(f2); kirjoittaa uudelleen(f); reset(f1); reset(f2); Lue(f1, a1); Lue(f2, a2); Vaikka (ei EOF(f1)) ja (ei EOF(f2)) alkavat i:=0; j:=0; b:=true; Vaikka (b) ja (ei EOF(f1)) ja (ei EOF(f2)) alkavat Jos (a1<a2) aloita sittenWrite(f, a1, ' '); Lue(f1, a1); inc(i); End else begin Write(f, a2, ' '); Lue(f2, a2); inc(j); loppu; Jos (i=s) tai (j=s), niin b:=false; loppu; Jos ei b, aloita While (i<s) ja (ei EOF(f1)) aloita Write(f, a1, ' '); Lue(f1, a1); inc(i); loppu; Vaikka (j<s) ja (ei EOF(f2)) alkavat Write(f, a2, ' '); Lue(f2, a2); inc(j); loppu; loppu; loppu; Vaikka ei EOF(f1), aloita tmp:=a1; Lue(f1, a1); Jos ei EOF(f1), sitten Write(f, tmp, ' ') muuten Write(f, tmp); loppu; Vaikka ei EOF(f2), aloita tmp:=a2; Lue(f2, a2); Jos ei EOF(f2), sitten Write(f, tmp, ' ') muuten Write(f, tmp); loppu; sulje(f); sulje(f1); sulje(f2); s:=s2; loppu; Pyyhi(f1); Pyyhi(f2); Loppu;
Visuaalisesti algoritmin toiminta näyttää tältä (ylhäältä - järjestämätön sekvenssi, alhaalla - järjestetty).
Ulkoinen tietojen lajittelu
Hyvin usein on tarpeen lajitella joitakin tietokoneen ulkoisessa muistissa olevia tietoja. Joissakin tapauksissa ne ovat vaikuttavan kokoisia, eikä niitä voida sijoittaa RAM-muistiin niiden käytön helpottamiseksi. Tällaisissa tapauksissa käytetään ulkoisia lajittelumenetelmiä.
Tarve käyttää ulkoista mediaa heikentää käsittelyajan tehokkuutta.
Työn monimutkaisuus on, että algoritmi voi käyttää vain yhtä tietovirran elementtiä kerrallaan. Ja tässä tapauksessa yhden parhaista tuloksista näyttää yhdistämislajittelumenetelmällä, joka voi vertailla kahden tiedoston elementtejä peräkkäin peräkkäin.
Luetaan tietoja kohteestaulkoinen lähde, niiden käsittely ja kirjoittaminen lopulliseen tiedostoon suoritetaan järjestetyissä lohkoissa (sarjoissa). Tilattujen sarjojen koon kanssa työskentelytavan mukaan lajittelua on kahta tyyppiä: yksinkertainen ja luonnollinen yhdistäminen.
Yksinkertainen yhdistäminen
Yksinkertaisella yhdistämisellä sarjan pituus on kiinteä.
Siten alkuperäisessä lajittelemattomassa tiedostossa kaikki sarjat koostuvat yhdestä elementistä. Ensimmäisen vaiheen jälkeen koko kasvaa kahteen. Seuraava - 4, 8, 16 ja niin edelleen.
Se toimii näin:
- Lähdetiedosto (f) on jaettu kahteen aputiedostoon - f1, f2.
- Ne yhdistetään taas yhdeksi tiedostoksi (f), mutta samalla kaikkia elementtejä verrataan pareittain ja muodostavat pareja. Sarjan koosta tässä vaiheessa tulee kaksi.
- Vaihe 1 toistetaan.
- Vaihe 2 toistetaan, mutta jo tilatut 2:t yhdistetään lajiteltuiksi 4:ksi.
- Silmukka jatkuu ja lisää sarjaa jokaisessa iteraatiossa, kunnes koko tiedosto on lajiteltu.
Mistä tiedät, että ulompi lajittelu yksinkertaisella yhdistämisellä on valmis?
- uuden sarjan pituus (yhdistamisen jälkeen) vähintään elementtien kokonaismäärä;
- vain yksi jakso jäljellä;
- Aputiedosto f2 jätettiin tyhjäksi.
Yksinkertaisen yhdistämisen haitat ovat: koska ajon pituus on kiinteä jokaisella yhdistämiskierroksella, osittain järjestetyn tiedon käsittely kestää yhtä kauan kuin täysin satunnaista tietoa.
Luonnollinen fuusio
Tämä menetelmä ei rajoita pituuttasarja, mutta valitsee suurimman mahdollisen.
Lajittelualgoritmi:
- Alkuperäisen sekvenssin lukeminen tiedostosta f. Ensimmäinen vastaanotettu elementti kirjoitetaan tiedostoon f1.
- Jos seuraava merkintä täyttää lajitteluehdon, se kirjoitetaan sinne, jos ei, niin toiseen aputiedostoon f2.
- Tällä tavalla kaikki lähdetiedoston tietueet jaetaan ja f1:een muodostetaan järjestetty järjestys, joka määrittää sarjan nykyisen koon.
- Tiedostot f1 ja f2 on yhdistetty.
- Jakso toistuu.
Sarjan ei-kiinteän koon vuoksi sarjan loppu on tarpeen merkitä erikoismerkillä. Siksi vertailujen määrä lisääntyy yhdistämisen yhteydessä. Lisäksi yhden aputiedoston koko voi olla lähellä alkuperäisen kokoa.
Keskimäärin luonnollinen yhdistäminen on tehokkaampaa kuin yksinkertainen yhdistäminen ulkoiseen lajitteluun.
Algoritmin ominaisuudet
Kahta identtistä arvoa verrattaessa menetelmä säilyttää alkuperäisen järjestyksensä, eli se on vakaa.
Lajitteluprosessi voidaan jakaa erittäin onnistuneesti useisiin säikeisiin.
Video osoittaa selkeästi yhdistämislajittelualgoritmin toiminnan.
