Ievads sapludināšanas šķirošanas algoritmā

Sapludināšanas kārtojums ir šķirošanas algoritms, kas balstīts uz “dalīt un iekarot” tehniku. Tas ir viens no efektīvākajiem šķirošanas algoritmiem.

Šajā rakstā jūs uzzināsiet par sapludināšanas šķirošanas algoritma darbību, par apvienošanas šķirošanas algoritmu, tā laika un telpas sarežģītība un tā ieviešana dažādās programmēšanas valodās, piemēram, C ++, Python un JavaScript.

Kā darbojas sapludināšanas šķirošanas algoritms?

Apvienot šķirot darbojas pēc sadalīšanas un iekarošanas principa. Sapludināšanas kārtība atkārtoti sadala masīvu divos vienādos apakškārtos, līdz katra apakšgrupa sastāv no viena elementa. Visbeidzot, visi šie apakšrati tiek apvienoti tā, ka iegūtais masīvs tiek sakārtots.

Šo jēdzienu var efektīvāk izskaidrot ar piemēra palīdzību. Apsveriet nešķirotu masīvu ar šādiem elementiem: {16, 12, 15, 13, 19, 17, 11, 18}.

Šeit sapludināšanas šķirošanas algoritms masīvu sadala divās pusēs, sauc sevi par abām pusēm un pēc tam apvieno abas sakārtotās puses.

Apvienot šķirošanas algoritmu

Zemāk ir apvienošanas veida algoritms:

MergeSort (arr [], leftIndex, rightIndex)
ja leftIndex> = rightIndex
atgriešanās
cits
Atrodiet vidējo indeksu, kas masīvu sadala divās pusēs: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Zvana mergeSort () pirmajā pusē: 
Zvanu sapludināšanaSort (arr, leftIndex, middleIndex)
Zvanu sapludināšana () otrajai pusei:
Zvanu sapludināšanaSort (arr, middleIndex + 1, rightIndex)
Apvienojiet abas pusītes, kas sakārtotas 2. un 3. darbībā:
Zvanu sapludināšana (arr, leftIndex, middleIndex, rightIndex)

Saistīts: Kas ir rekursija un kā jūs to izmantojat?

Apvienošanas šķirošanas algoritma sarežģītība laikā un telpā

Apvienošanas šķirošanas algoritmu var izteikt šādas atkārtošanās attiecības veidā:

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

Pēc šīs atkārtošanās attiecības atrisināšanas, izmantojot galvenā teorēma vai atkārtošanās koka metodi, jūs saņemsiet risinājumu kā O (n logn). Tādējādi sapludināšanas šķirošanas algoritma laika sarežģītība ir O (n pieteikties).

Labākais apvienošanas veida sarežģītības laiks: O (n pieteikties)

Apvienošanas veida vidējā laika sarežģītība: O (n pieteikties)

Apvienošanas veida sliktākā laika sarežģītība: O (n pieteikties)

Saistīts: Kas ir Big-O apzīmējums?

Palīgtelpas sarežģītība sapludināšanas šķirošanas algoritms ir O (n) kā n apvienošanas kārtošanas ieviešanā ir nepieciešama papildu telpa.

C ++ sapludināšanas šķirošanas algoritma ieviešana

Zemāk ir apvienošanas kārtošanas algoritma C ++ ieviešana:

// C ++ programmas ieviešana
// apvienot šķirošanas algoritmu
# iekļaut 
izmantojot nosaukumvietu std;
// Šī funkcija apvieno divus apakškārtas arr []
// Kreisais apakšgrupa: arr [leftIndex..middleIndex]
// Labā apakšzīme: arr [middleIndex + 1..rightIndex]
void sapludināšana (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Izveidot pagaidu masīvus
int L [leftSubarraySize], R [rightSubarraySize];
// Datu kopēšana pagaidu masīvos L [] un R []
par (int i = 0; i L [i] = arr [leftIndex + i];
par (int j = 0; j R [j] = arr [middleIndex + 1 + j];
// Apvienot pagaidu masīvus atpakaļ arr [leftIndex..rightIndex]
// Kreisās apakšgrupas sākotnējais indekss
int i = 0;
// Sākotnējais labās apakšgrupas indekss
int j = 0;
// Apvienotā apakšgrupas sākotnējais indekss
int k = leftIndex;
while (i {
ja (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
cits
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Ja L ir daži atlikušie elementi
// Kopēt uz arr []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Ja R ir daži atlikušie elementi
// Kopēt uz arr []
kamēr (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
ja (leftIndex> = rightIndex)
{
atgriešanās;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
apvienot (arr, leftIndex, middleIndex, rightIndex);
}
// Funkcija elementu drukāšanai
masīva //
void printArray (int arr [], int izmērs)
{
par (int i = 0; i {
cout << arr [i] << "";
}
cout << endl;
}
// Vadītāja kods
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int izmērs = sizeof (arr) / sizeof (arr [0]);
cout << "Nesakārtots masīvs:" << endl;
printArray (arr, izmērs);
mergeSort (arr, 0, izmērs - 1);
cout << "Kārtotais masīvs:" << endl;
printArray (arr, izmērs);
atgriešanās 0;
}

Izeja:

Nesakārtots masīvs:
16 12 15 13 19 17 11 18 
Kārtots masīvs:
11 12 13 15 16 17 18 19

Java sapludināšanas šķirošanas algoritma ieviešana

Zemāk ir apvienošanas kārtošanas algoritma JavaScript ieviešana:

// JavaScript ieviešana
// apvienot šķirošanas algoritmu
// Šī funkcija apvieno divus apakškārtas arr []
// Kreisais apakšgrupa: arr [leftIndex..middleIndex]
// Labā apakšzīme: arr [middleIndex + 1..rightIndex]
funkciju apvienošana (arr, leftIndex, middleIndex, rightIndex) {
ļaujiet leftSubarraySize = middleIndex - leftIndex + 1;
ļaujiet rightSubarraySize = rightIndex - middleIndex;
// Izveidot pagaidu masīvus
var L = jauns masīvs (leftSubarraySize);
var R = jauns masīvs (rightSubarraySize);
// Datu kopēšana pagaidu masīvos L [] un R []
par (lai i = 0; iL [i] = arr [leftIndex + i];
}
par (lai j = 0; jR [j] = arr [middleIndex + 1 + j];
}
// Apvienot pagaidu masīvus atpakaļ arr [leftIndex..rightIndex]
// Kreisās apakšgrupas sākotnējais indekss
var i = 0;
// Sākotnējais labās apakšgrupas indekss
var j = 0;
// Apvienotā apakšgrupas sākotnējais indekss
var k = leftIndex;
while (i {
ja (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
cits
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Ja L ir daži atlikušie elementi
// Kopēt uz arr []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Ja R ir daži atlikušie elementi
// Kopēt uz arr []
kamēr (j {
arr [k] = R [j];
j ++;
k ++;
}
}
funkcija mergeSort (arr, leftIndex, rightIndex) {
if (leftIndex> = rightIndex) {
atgriešanās
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
apvienot (arr, leftIndex, middleIndex, rightIndex);
}
// Funkcija elementu drukāšanai
masīva //
funkcija printArray (arr, izmērs) {
par (lai i = 0; idocument.write (arr [i] + "");
}
document.write ("
");
}
// Vadītāja kods:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var size = arr.length;
document.write ("Nesakārtots masīvs:
");
printArray (arr, izmērs);
mergeSort (arr, 0, izmērs - 1);
document.write ("Kārtots masīvs:
");
printArray (arr, izmērs);

Izeja:

Nesakārtots masīvs:
16 12 15 13 19 17 11 18
Kārtots masīvs:
11 12 13 15 16 17 18 19

Saistīts: Dinamiskā programmēšana: piemēri, bieži sastopamās problēmas un risinājumi

Apvienotais šķirošanas algoritma Python ieviešana

Zemāk ir apvienošanas kārtošanas algoritma Python ieviešana:

# Python ieviešana
# apvienot algoritmu
def mergeSort (arr):
ja len (arr)> 1:
# Masīva vidējā indeksa atrašana
middleIndex = len (arr) // 2
# Masīva kreisā puse
L = arr [: middleIndex]
# Masīva labā puse
R = arr [middleIndex:]
# Masīva pirmās puses kārtošana
sapludinātKārtot (L)
# Masīva otrās puses kārtošana
sapludinātKārtot (R)
# Kreisās apakšgrupas sākotnējais indekss
i = 0
# Labās apakšgrupas sākotnējais indekss
j = 0
# Apvienotā apakšgrupas sākotnējais indekss
k = 0
# Kopēt datus temperatūras masīvos L [] un R []
kamēr i ja L [i] arr [k] = L [i]
i = i + 1
cits:
arr [k] = R [j]
j = j + 1
k = k + 1
# Pārbaudiet, vai ir vēl daži elementi
kamēr es arr [k] = L [i]
i = i + 1
k = k + 1
kamēr j arr [k] = R [j]
j = j + 1
k = k + 1
# Funkcija elementu drukāšanai
Masīva #
def printArray (arr, izmērs):
i diapazonā (izmērs):
drukāt (arr [i], end = "")
izdrukāt ()
# Vadītāja kods
arr = [16, 12, 15, 13, 19, 17, 11, 18]
izmērs = len (arr)
drukāt ("Nesakārtots masīvs:")
printArray (arr, izmērs)
mergeSort (arr)
drukāt ("Kārtots masīvs:")
printArray (arr, izmērs)

Izeja:

Nesakārtots masīvs:
16 12 15 13 19 17 11 18
Kārtots masīvs:
11 12 13 15 16 17 18 19

Izprotiet citus šķirošanas algoritmus

Šķirošana ir viens no programmēšanā visbiežāk izmantotajiem algoritmiem. Varat kārtot elementus dažādās programmēšanas valodās, izmantojot dažādus šķirošanas algoritmus, piemēram, ātru kārtošanu, burbuļu kārtošanu, apvienošanas kārtošanu, ievietošanas kārtošanu utt.

Burbuļu kārtošana ir labākā izvēle, ja vēlaties uzzināt par vienkāršāko šķirošanas algoritmu.

Ievads burbuļu šķirošanas algoritmā

Bubble Sort algoritms: lielisks ievads masīvu šķirošanai.

Lasiet Tālāk

Par autoru