Johdatus yhdistämisen lajittelualgoritmiin

Yhdistä lajittelu on lajittelualgoritmi, joka perustuu "jaa ja hallitse" -tekniikkaan. Se on yksi tehokkaimmista lajittelualgoritmeista.

Tässä artikkelissa opit yhdistämisen lajittelualgoritmin toiminnasta, yhdistämislajittelun algoritmista, sen ajan ja avaruuden monimutkaisuus ja sen toteuttaminen useilla ohjelmointikielillä, kuten C ++, Python ja JavaScript.

Kuinka yhdistämislajittelualgoritmi toimii?

Yhdistä lajittelu toimii jakamisen ja valloittamisen periaatteella. Yhdistämislajittelu hajottaa matriisin toistuvasti kahteen yhtä suureen alaryhmään, kunnes kukin alirakenne koostuu yhdestä elementistä. Lopuksi kaikki nämä alirivit yhdistetään siten, että tuloksena oleva taulukko lajitellaan.

Tämä käsite voidaan selittää tehokkaammin esimerkin avulla. Harkitse lajittelematon taulukko, jossa on seuraavat elementit: {16, 12, 15, 13, 19, 17, 11, 18}.

Tässä yhdistämisen lajittelualgoritmi jakaa matriisin kahteen puolikkaaseen, kutsuu itseään kahdeksi puoliskoksi ja yhdistää sitten kaksi lajiteltuja puolikkaita.

Yhdistä lajittelualgoritmi

Alla on yhdistämislajittelun algoritmi:

YhdistäSort (arr [], leftIndex, rightIndex)
jos leftIndex> = rightIndex
palata
muu
Etsi keskimmäinen hakemisto, joka jakaa matriisin kahteen puolikkaaseen: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Soita mergeSort () ensimmäiselle puoliskolle: 
Soita yhdistäminenSort (arr, leftIndex, middleIndex)
Soita mergeSort () toiselle puoliskolle:
Soita yhdistäminenSort (arr, middleIndex + 1, rightIndex)
Yhdistä kaksi vaiheita, jotka on lajiteltu vaiheissa 2 ja 3:
Soittoyhdistelmä (arr, leftIndex, middleIndex, rightIndex)

Liittyvät: Mikä on rekursio ja miten sitä käytetään?

Yhdistämisen lajittelualgoritmin aika ja avaruus

Yhdistä lajittelualgoritmi voidaan ilmaista seuraavan toistosuhteen muodossa:

T (n) = 2T (n / 2) + O (n)

Kun olet ratkaissut tämän toistumissuhteen päällikön lause- tai toistopuu-menetelmällä, saat ratkaisun O: na (n logn). Siten yhdistämisen lajittelualgoritmin aikakompleksi on O (n kirjautua).

Yhdistyslajin paras tapa-ajan monimutkaisuus: O (n kirjautua)

Yhdistämislajittelun keskimääräinen tapausaika-aika: O (n kirjautua)

Yhdistämisen lajittelun pahin tapa-aika: O (n kirjautua)

Liittyvät: Mikä on Big-O-merkintä?

Aputilan monimutkaisuus yhdistämisen lajittelualgoritmista on Päällä) kuten n aputila vaaditaan yhdistämisen lajittelun toteutuksessa.

C ++ Yhdistämisen lajittelualgoritmin toteutus

Alla on yhdistämisen lajittelualgoritmin C ++ -toteutus:

// C ++ -toteutus
// yhdistä lajittelualgoritmi
#sisältää 
käyttämällä nimitilaa vakio;
// Tämä toiminto yhdistää kaksi arr [[]: n aliriviä
// Vasen osa-alue: arr [leftIndex..middleIndex]
// Oikea alaosasto: arr [middleIndex + 1..rightIndex]
void merge (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Luo väliaikaiset taulukot
int L [leftSubarraySize], R [rightSubarraySize];
// Tietojen kopiointi väliaikaisiin matriiseihin L [] ja R []
for (int i = 0; i L [i] = arr [leftIndex + i];
for (int j = 0; j R [j] = arr [keski-Indeksi + 1 + j];
// Yhdistä väliaikaiset taulukot taulukkoon [leftIndex..rightIndex]
// Vasemman alaosaston alkuindeksi
int i = 0;
// Oikean alaosaston alkuindeksi
int j = 0;
// Yhdistetyn osa-alueen alkuindeksi
int k = leftIndex;
while (i {
jos (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
muu
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Jos L: ssä on joitain jäljellä olevia elementtejä
// Kopioi arr: iin []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Jos R: ssä on joitain jäljellä olevia elementtejä
// Kopioi arr: iin []
kun (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
jos (leftIndex> = rightIndex)
{
palata;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
yhdistää (arr, leftIndex, middleIndex, rightIndex);
}
// Toiminto elementtien tulostamiseen
// taulukosta
void printArray (int arr [], int-koko)
{
for (int i = 0; i {
cout << arr [i] << "";
}
cout << endl;
}
// Kuljettajan koodi
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int koko = koko (arr) / kokoof (arr [0]);
cout << "Lajittelematon taulukko:" << endl;
printArray (arr, koko);
mergeSort (arr, 0, koko - 1);
cout << "Lajiteltu taulukko:" << endl;
printArray (arr, koko);
paluu 0;
}

Tuotos:

Lajittelematon taulukko:
16 12 15 13 19 17 11 18 
Lajiteltu taulukko:
11 12 13 15 16 17 18 19

JavaScript Yhdistämisen lajittelualgoritmin toteutus

Alla on yhdistämisen lajittelualgoritmin JavaScript-toteutus:

// JavaScriptin toteutus
// yhdistä lajittelualgoritmi
// Tämä toiminto yhdistää kaksi arr [[]: n aliriviä
// Vasen osa-alue: arr [leftIndex..middleIndex]
// Oikea alaosasto: arr [middleIndex + 1..rightIndex]
funktion yhdistäminen (arr, leftIndex, middleIndex, rightIndex) {
anna leftSubarraySize = middleIndex - leftIndex + 1;
anna rightSubarraySize = rightIndex - middleIndex;
// Luo väliaikaiset taulukot
var L = uusi taulukko (leftSubarraySize);
var R = uusi taulukko (rightSubarraySize);
// Tietojen kopiointi väliaikaisiin matriiseihin L [] ja R []
for (olkoon i = 0; iL [i] = arr [leftIndex + i];
}
for (olkoon j = 0; jR [j] = arr [keski-Indeksi + 1 + j];
}
// Yhdistä väliaikaiset taulukot taulukkoon [leftIndex..rightIndex]
// Vasemman alaosaston alkuindeksi
var i = 0;
// Oikean alaosaston alkuindeksi
var j = 0;
// Yhdistetyn osa-alueen alkuindeksi
var k = leftIndex;
while (i {
jos (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
muu
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Jos L: ssä on joitain jäljellä olevia elementtejä
// Kopioi arr: iin []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Jos R: ssä on joitain jäljellä olevia elementtejä
// Kopioi arr: iin []
kun (j {
arr [k] = R [j];
j ++;
k ++;
}
}
function mergeSort (arr, leftIndex, rightIndex) {
if (leftIndex> = rightIndex) {
palata
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
yhdistää (arr, leftIndex, middleIndex, rightIndex);
}
// Toiminto elementtien tulostamiseen
// taulukosta
funktio printArray (arr, koko) {
for (olkoon i = 0; idocument.write (arr [i] + "");
}
document.write ("
");
}
// Kuljettajan koodi:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var koko = arr.pituus;
document.write ("Lajittelematon taulukko:
");
printArray (arr, koko);
mergeSort (arr, 0, koko - 1);
document.write ("Lajiteltu taulukko:
");
printArray (arr, koko);

Tuotos:

Lajittelematon taulukko:
16 12 15 13 19 17 11 18
Lajiteltu taulukko:
11 12 13 15 16 17 18 19

Liittyvät: Dynaaminen ohjelmointi: Esimerkkejä, yleisiä ongelmia ja ratkaisuja

Yhdistämisen lajittelualgoritmin Python-toteutus

Alla on yhdistämisen lajittelualgoritmin Python-toteutus:

# Python-toteutus
# yhdistä lajittelualgoritmi
def mergeSort (arr):
jos len (arr)> 1:
# Taulukon keskihakemiston etsiminen
middleIndex = len (arr) // 2
# Taulukon vasen puolisko
L = arr [: keski-indeksi]
# Oikea puoli taulukosta
R = arr [keski-indeksi:]
# Lajittelu ryhmän ensimmäiselle puoliskolle
mergeSort (L)
# Lajittelu taulukon toinen puoli
mergeSort (R)
# Vasemman alaosaston alkuindeksi
i = 0
# Oikean alaosaston alkuindeksi
j = 0
# Yhdistetyn osa-alueen alkuindeksi
k = 0
# Kopioi tiedot lämpötilaryhmiin L [] ja R []
kun taas i jos L [i] arr [k] = L [i]
i = i + 1
muu:
arr [k] = R [j]
j = j + 1
k = k + 1
# Tarkistetaan onko jäljellä elementtejä
kun minä arr [k] = L [i]
i = i + 1
k = k + 1
kun j arr [k] = R [j]
j = j + 1
k = k + 1
# Toiminto elementtien tulostamiseen
# matriisista
def print Array (arr, koko):
i: lle alueella (koko):
tulosta (arr [i], loppu = "")
Tulosta()
# Kuljettajan koodi
arr = [16, 12, 15, 13, 19, 17, 11, 18]
koko = len (arr)
tulosta ("Lajittelematon taulukko:")
printArray (arr, koko)
mergeSort (arr)
tulosta ("Lajiteltu taulukko:")
printArray (arr, koko)

Tuotos:

Lajittelematon taulukko:
16 12 15 13 19 17 11 18
Lajiteltu taulukko:
11 12 13 15 16 17 18 19

Ymmärrä muut lajittelualgoritmit

Lajittelu on yksi ohjelmoinnin käytetyimmistä algoritmeista. Voit lajitella elementtejä eri ohjelmointikielillä käyttämällä erilaisia ​​lajittelualgoritmeja, kuten pikalajittelu, kuplalajittelu, yhdistämislajittelu, lisäyslajittelu jne.

Kuplalajittelu on paras valinta, jos haluat oppia yksinkertaisimmasta lajittelualgoritmista.

Johdatus kuplalajittelualgoritmiin

Bubble Sort -algoritmi: erinomainen esittely lajittelulajeihin.

Lue seuraava

Kirjailijasta