O introducere în algoritmul de sortare Merge

Sortarea Merge este un algoritm de sortare bazat pe tehnica „împarte și cucerește”. Este unul dintre cei mai eficienți algoritmi de sortare.

În acest articol, veți afla despre funcționarea algoritmului de sortare a îmbinării, algoritmul sortării de îmbinare, a acestuia complexitatea timpului și spațiului și implementarea acestuia în diferite limbaje de programare precum C ++, Python și JavaScript.

Cum funcționează algoritmul de sortare Merge?

Sortarea Merge funcționează pe principiul divizării și cuceririi. Merge sort descompune în mod repetat o matrice în două subarrayuri egale până când fiecare subarray constă dintr-un singur element. În cele din urmă, toate aceste subarrays sunt îmbinate astfel încât matricea rezultată este sortată.

Acest concept poate fi explicat mai eficient cu ajutorul unui exemplu. Luați în considerare o matrice nesortată cu următoarele elemente: {16, 12, 15, 13, 19, 17, 11, 18}.

Aici, algoritmul de sortare de îmbinare împarte matricea în două jumătăți, se numește singur pentru cele două jumătăți și apoi îmbină cele două jumătăți sortate.

Merge Sort Algorithm

Mai jos este algoritmul sortării de îmbinare:

MergeSort (arr [], leftIndex, rightIndex)
if leftIndex> = rightIndex
întoarcere
altfel
Găsiți indicele de mijloc care împarte matricea în două jumătăți: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Apelați mergeSort () pentru prima jumătate: 
Apelați mergeSort (arr, leftIndex, middleIndex)
Apelați mergeSort () pentru a doua jumătate:
Apel mergeSort (arr, middleIndex + 1, rightIndex)
Îmbinați cele două jumătăți sortate la pasul 2 și 3:
Combinarea apelurilor (arr, leftIndex, middleIndex, rightIndex)

Legate de: Ce este recursivitatea și cum o utilizați?

Complexitatea de timp și spațiu a algoritmului de sortare Merge

Algoritmul de sortare Merge poate fi exprimat sub forma următoarei relații de recurență:

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

După rezolvarea acestei relații de recurență folosind teorema masterului sau metoda arborelui de recurență, veți obține soluția ca O (n logn). Astfel, complexitatea în timp a algoritmului de sortare a îmbinării este O (n logn).

Complexitatea în cel mai bun caz a sortării fuziunii: O (n logn)

Complexitatea de timp a cazului mediu al sortării de îmbinare: O (n logn)

Cea mai dificilă complexitate temporală a sortării fuziunii: O (n logn)

Legate de: Ce este notația Big-O?

Complexitatea spațiului auxiliar al algoritmului de sortare de îmbinare este Pe) la fel de n spațiul auxiliar este necesar în implementarea sortare fuzionare.

C ++ Implementarea algoritmului Merge Sort

Mai jos este implementarea C ++ a algoritmului de sortare a îmbinării:

// Implementarea C ++ a
// combina algoritmul de sortare
#include 
folosind spațiul de nume std;
// Această funcție îmbină două subarraiuri de arr []
// Subarray stânga: arr [leftIndex..middleIndex]
// Subarray dreapta: arr [middleIndex + 1..rightIndex]
void merge (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Creați tablouri temporare
int L [leftSubarraySize], R [rightSubarraySize];
// Copierea datelor în matricele temporare L [] și R []
pentru (int i = 0; i L [i] = arr [leftIndex + i];
pentru (int j = 0; j R [j] = arr [middleIndex + 1 + j];
// Îmbinați matricele temporare înapoi în arr [leftIndex..rightIndex]
// Indexul inițial al subarray-ului din stânga
int i = 0;
// Indexul inițial al subarrayului drept
int j = 0;
// Indexul inițial al subarray-ului combinat
int k = leftIndex;
while (i {
dacă (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
altfel
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Dacă mai sunt câteva elemente rămase în L []
// Copiază în arr []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Dacă mai sunt câteva elemente rămase în R []
// Copiază în arr []
while (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
if (leftIndex> = rightIndex)
{
întoarcere;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
merge (arr, leftIndex, middleIndex, rightIndex);
}
// Funcția de imprimare a elementelor
// a matricei
void printArray (int arr [], dimensiune int)
{
pentru (int i = 0; i {
cout << arr [i] << "";
}
cout << endl;
}
// Cod șofer
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int size = sizeof (arr) / sizeof (arr [0]);
cout << "Matrice nesortate:" << endl;
printArray (arr, dimensiune);
mergeSort (arr, 0, mărime - 1);
cout << "Matrice sortate:" << endl;
printArray (arr, dimensiune);
retur 0;
}

Ieșire:

Matrice nesortate:
16 12 15 13 19 17 11 18 
Matrice sortate:
11 12 13 15 16 17 18 19

Implementarea JavaScript a algoritmului Merge Sort

Mai jos este implementarea JavaScript a algoritmului de sortare a îmbinării:

// Implementarea JavaScript a
// combina algoritmul de sortare
// Această funcție îmbină două subarraiuri de arr []
// Subarray stânga: arr [leftIndex..middleIndex]
// Subarray dreapta: arr [middleIndex + 1..rightIndex]
funcție merge (arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Creați tablouri temporare
var L = Array nou (leftSubarraySize);
var R = new Array (rightSubarraySize);
// Copierea datelor în matricele temporare L [] și R []
pentru (să i = 0; euL [i] = arr [leftIndex + i];
}
pentru (să fie j = 0; jR [j] = arr [middleIndex + 1 + j];
}
// Îmbinați matricele temporare înapoi în arr [leftIndex..rightIndex]
// Indexul inițial al subarray-ului din stânga
var i = 0;
// Indexul inițial al subarrayului drept
var j = 0;
// Indexul inițial al subarray-ului combinat
var k = leftIndex;
while (i {
dacă (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
altfel
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Dacă mai sunt câteva elemente rămase în L []
// Copiază în arr []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Dacă mai sunt câteva elemente rămase în R []
// Copiază în arr []
while (j {
arr [k] = R [j];
j ++;
k ++;
}
}
funcția mergeSort (arr, leftIndex, rightIndex) {
if (leftIndex> = rightIndex) {
întoarcere
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
merge (arr, leftIndex, middleIndex, rightIndex);
}
// Funcția de imprimare a elementelor
// a matricei
funcție printArray (arr, dimensiune) {
pentru (să i = 0; eudocument.write (arr [i] + "");
}
document.write („
");
}
// Cod șofer:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var size = arr.length;
document.write ("Matrice nesortate:
");
printArray (arr, dimensiune);
mergeSort (arr, 0, mărime - 1);
document.write ("Matrice sortată:
");
printArray (arr, dimensiune);

Ieșire:

Matrice nesortate:
16 12 15 13 19 17 11 18
Matrice sortate:
11 12 13 15 16 17 18 19

Legate de: Programare dinamică: exemple, probleme comune și soluții

Implementarea Python a algoritmului Merge Sort

Mai jos este implementarea Python a algoritmului de sortare a îmbinării:

# Implementarea Python a
# algoritm de sortare merge
def mergeSort (arr):
dacă len (arr)> 1:
# Găsirea indexului de mijloc al matricei
middleIndex = len (arr) // 2
# Jumătatea stângă a matricei
L = arr [: middleIndex]
# Jumătate dreaptă a matricei
R = arr [middleIndex:]
# Sortarea primei jumătăți a matricei
mergeSort (L)
# Sortarea celei de-a doua jumătăți a matricei
mergeSort (R)
# Indexul inițial al subarray-ului din stânga
i = 0
# Indexul inițial al subarrayului drept
j = 0
# Indexul inițial al subarray-ului combinat
k = 0
# Copiați datele în matricele de temperatură L [] și R []
în timp ce i dacă L [i] arr [k] = L [i]
i = i + 1
altceva:
arr [k] = R [j]
j = j + 1
k = k + 1
# Verificarea dacă mai sunt câteva elemente rămase
în timp ce i arr [k] = L [i]
i = i + 1
k = k + 1
în timp ce j arr [k] = R [j]
j = j + 1
k = k + 1
# Funcția de imprimare a elementelor
# din matrice
def printArray (arr, dimensiune):
pentru i în interval (dimensiune):
print (arr [i], end = "")
imprimare()
# Cod șofer
arr = [16, 12, 15, 13, 19, 17, 11, 18]
size = len (arr)
print ("Matrice nesortate:")
printArray (arr, dimensiune)
mergeSort (arr)
print ("Matricea sortată:")
printArray (arr, dimensiune)

Ieșire:

Matrice nesortate:
16 12 15 13 19 17 11 18
Matrice sortate:
11 12 13 15 16 17 18 19

Înțelegeți alte algoritmi de sortare

Sortarea este unul dintre cei mai utilizați algoritmi în programare. Puteți sorta elemente în diferite limbaje de programare folosind diverși algoritmi de sortare, cum ar fi sortare rapidă, sortare cu bule, sortare prin îmbinare, sortare prin inserție etc.

Sortarea cu bule este cea mai bună alegere dacă doriți să aflați despre cel mai simplu algoritm de sortare.

Introducere în algoritmul de sortare cu bule

Algoritmul Bubble Sort: o introducere excelentă la sortarea matricelor.

Citiți în continuare

Despre autor