Introduzione all'algoritmo Merge Sort

Merge sort è un algoritmo di ordinamento basato sulla tecnica del "divide et impera". È uno degli algoritmi di ordinamento più efficienti.

In questo articolo imparerai a conoscere il funzionamento dell'algoritmo del merge sort, l'algoritmo del merge sort, la sua complessità temporale e spaziale e la sua implementazione in vari linguaggi di programmazione come C++, Python e JavaScript.

Come funziona l'algoritmo Merge Sort?

Merge sort funziona secondo il principio del divide et impera. Merge sort suddivide ripetutamente un array in due sottoarray uguali finché ogni sottoarray è costituito da un singolo elemento. Infine, tutti questi sottoarray vengono uniti in modo tale che l'array risultante venga ordinato.

Questo concetto può essere spiegato in modo più efficiente con l'aiuto di un esempio. Considera un array non ordinato con i seguenti elementi: {16, 12, 15, 13, 19, 17, 11, 18}.

Qui, l'algoritmo di ordinamento di unione divide l'array in due metà, richiama se stesso per le due metà e quindi unisce le due metà ordinate.

Unisci algoritmo di ordinamento Mer

Di seguito è riportato l'algoritmo del merge sort:

MergeSort (arr[], leftIndex, rightIndex)
if leftIndex >= rightIndex
ritorno
altro
Trova l'indice centrale che divide l'array in due metà: 
middleIndex = leftIndex + (rightIndex-leftIndex)/2
Chiama mergeSort() per la prima metà: 
Chiama mergeSort (arr, leftIndex, middleIndex)
Chiama mergeSort() per la seconda metà:
Chiama mergeSort (arr, middleIndex+1, rightIndex)
Unisci le due metà ordinate nel passaggio 2 e 3:
Call merge (arr, leftIndex, middleIndex, rightIndex)

Relazionato: Che cos'è la ricorsione e come si usa?

Complessità temporale e spaziale dell'algoritmo Merge Sort

L'algoritmo Merge sort può essere espresso nella forma della seguente relazione di ricorrenza:

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

Dopo aver risolto questa relazione di ricorrenza usando il teorema del master o il metodo dell'albero di ricorrenza, otterrai la soluzione come O(n logn). Pertanto, la complessità temporale dell'algoritmo di merge sort è O(n accesso).

La migliore complessità temporale del merge sort: O(n accesso)

La complessità temporale del caso medio del merge sort: O(n accesso)

La complessità temporale del caso peggiore del merge sort: O(n accesso)

Relazionato: Che cos'è la notazione Big-O?

La complessità dello spazio ausiliario dell'algoritmo di merge sort è Sopra) come n spazio ausiliario è richiesto nell'implementazione del merge sort.

Implementazione in C++ dell'algoritmo Merge Sort

Di seguito è riportata l'implementazione C++ dell'algoritmo di ordinamento di unione:

// Implementazione C++ di
// unisci algoritmo di ordinamento
#includere 
usando lo spazio dei nomi std;
// Questa funzione unisce due sottoarray di arr[]
// Sottoarray sinistro: arr[leftIndex..middleIndex]
// Sottoarray destro: arr[middleIndex+1..rightIndex]
void merge (int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Crea array temporanei
int L[DimensioneSubarraysinistra], R[DimensioneSubarraydestra];
// Copia i dati negli array temporanei L[] e R[]
per (int i = 0; i < leftSubarraySize; io++)
L[i] = arr[Indicesinistro + i];
per (int j = 0; j < rightSubarraySize; j++)
R[j] = arr[indice medio + 1 + j];
// Unisci di nuovo gli array temporanei in arr[leftIndex..rightIndex]
// Indice iniziale del sottoarray sinistro
int i = 0;
// Indice iniziale del sottoarray destro
intj = 0;
// Indice iniziale del sottoarray unito
int k = indice sinistro;
while (i < leftSubarraySize && j < rightSubarraySize)
{
se (L[i] <= R[j])
{
arr[k] = L[i];
io++;
}
altro
{
arr[k] = R[j];
j++;
}
k++;
}
// Se ci sono alcuni elementi rimanenti in L[]
// Copia in arr[]
while (i < leftSubarraySize)
{
arr[k] = L[i];
io++;
k++;
}
// Se ci sono alcuni elementi rimanenti in R[]
// Copia in arr[]
while (j < rightSubarraySize)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort (int arr[], int leftIndex, int rightIndex)
{
if (leftIndex >= rightIndex)
{
ritorno;
}
int middleIndex = leftIndex + (rightIndex - leftIndex)/2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex+1, rightIndex);
unire (arr, leftIndex, middleIndex, rightIndex);
}
// Funzione per stampare gli elementi
// dell'array
void printArray (int arr[], int size)
{
per (int i = 0; io < taglia; io++)
{
cout << arr[i] << " ";
}
cout<}
// Codice conducente
intero principale()
{
int arr[] = { 16, 12, 15, 13, 19, 17, 11, 18 };
int size = sizeof (arr) / sizeof (arr[0]);
cout<printArray (arr, dimensione);
mergeSort (arr, 0, dimensione - 1);
cout<printArray (arr, dimensione);
restituisce 0;
}

Produzione:

Matrice non ordinata:
16 12 15 13 19 17 11 18 
Matrice ordinata:
11 12 13 15 16 17 18 19

Implementazione JavaScript dell'algoritmo Merge Sort

Di seguito è riportata l'implementazione JavaScript dell'algoritmo di ordinamento di unione:

// Implementazione JavaScript del
// unisci algoritmo di ordinamento
// Questa funzione unisce due sottoarray di arr[]
// Sottoarray sinistro: arr[leftIndex..middleIndex]
// Sottoarray destro: arr[middleIndex+1..rightIndex]
funzione unione (arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Crea array temporanei
var L = new Array (leftSubarraySize);
var R = new Array (rightSubarraySize);
// Copia i dati negli array temporanei L[] e R[]
per (lascia i = 0; ioL[i] = arr[Indicesinistro + i];
}
per (sia j = 0; jR[j] = arr[indice medio + 1 + j];
}
// Unisci di nuovo gli array temporanei in arr[leftIndex..rightIndex]
// Indice iniziale del sottoarray sinistro
variabile i = 0;
// Indice iniziale del sottoarray destro
varj = 0;
// Indice iniziale del sottoarray unito
var k = indice sinistro;
while (i < leftSubarraySize && j < rightSubarraySize)
{
se (L[i] <= R[j])
{
arr[k] = L[i];
io++;
}
altro
{
arr[k] = R[j];
j++;
}
k++;
}
// Se ci sono alcuni elementi rimanenti in L[]
// Copia in arr[]
while (i < leftSubarraySize)
{
arr[k] = L[i];
io++;
k++;
}
// Se ci sono alcuni elementi rimanenti in R[]
// Copia in arr[]
while (j < rightSubarraySize)
{
arr[k] = R[j];
j++;
k++;
}
}
function mergeSort (arr, leftIndex, rightIndex) {
if (indice sinistro >= indice destro) {
ritorno
}
var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex+1, rightIndex);
unire (arr, leftIndex, middleIndex, rightIndex);
}
// Funzione per stampare gli elementi
// dell'array
funzione printArray (arr, dimensione) {
per (lascia i = 0; iodocument.write (arr[i] + " ");
}
documento.write("
");
}
// Codice pilota:
var arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ];
var size = arr.lunghezza;
document.write("Array non ordinato:
");
printArray (arr, dimensione);
mergeSort (arr, 0, dimensione - 1);
document.write("Array ordinato:
");
printArray (arr, dimensione);

Produzione:

Matrice non ordinata:
16 12 15 13 19 17 11 18
Matrice ordinata:
11 12 13 15 16 17 18 19

Relazionato: Programmazione dinamica: esempi, problemi comuni e soluzioni

Implementazione in Python dell'algoritmo Merge Sort

Di seguito è riportata l'implementazione Python dell'algoritmo di ordinamento di unione:

# Implementazione Python del
# algoritmo di ordinamento di unione
def mergeSort (arr):
se len (arr) > 1:
# Trovare l'indice centrale dell'array
indice medio = len (arr)//2
# Metà sinistra dell'array
L = arr[:indice medio]
# Metà destra dell'array
R = arr[indice medio:]
# Ordinamento della prima metà dell'array
unisciOrdina (L)
# Ordinamento della seconda metà dell'array
unisciOrdina (R)
# Indice iniziale del sottoarray sinistro
io = 0
# Indice iniziale del sottoarray destro
j = 0
# Indice iniziale del sottoarray unito
k = 0
# Copia i dati negli array temporanei L[] e R[]
mentre i < len (L) e j < len (R):
se L[i] < R[j]:
arr[k] = L[i]
io = io + 1
altro:
arr[k] = R[j]
j = j + 1
k = k + 1
# Controllo se ci sono alcuni elementi rimanenti
mentre io < len (L):
arr[k] = L[i]
io = io + 1
k = k + 1
mentre j < len (R):
arr[k] = R[j]
j = j + 1
k = k + 1
# Funzione per stampare gli elementi
# dell'array
def printArray (arr, dimensione):
per i nell'intervallo (dimensioni):
print (arr[i], end=" ")
Stampa()
# Codice conducente
arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
dimensione = lente (arr)
print("Array non ordinato:")
printArray (arr, dimensione)
mergeSort (arr)
print("array ordinato:")
printArray (arr, dimensione)

Produzione:

Matrice non ordinata:
16 12 15 13 19 17 11 18
Matrice ordinata:
11 12 13 15 16 17 18 19

Comprendere altri algoritmi di ordinamento

L'ordinamento è uno degli algoritmi più utilizzati nella programmazione. Puoi ordinare gli elementi in diversi linguaggi di programmazione utilizzando vari algoritmi di ordinamento come ordinamento rapido, ordinamento a bolle, ordinamento di unione, ordinamento per inserimento, ecc.

L'ordinamento a bolle è la scelta migliore se vuoi conoscere l'algoritmo di ordinamento più semplice.

Introduzione all'algoritmo di Bubble Sort

L'algoritmo Bubble Sort: un'eccellente introduzione all'ordinamento degli array.

Leggi Avanti

Circa l'autore