Home-theater-designers
Merge sort è un algoritmo di ordinamento basato sulla tecnica del 'divide et impera'. È uno degli algoritmi di ordinamento più efficienti.
come giocare ai vecchi giochi per PC su Windows 10
In questo articolo imparerai a conoscere il funzionamento dell'algoritmo di ordinamento di unione, l'algoritmo di ordinamento di unione, 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
Di seguito è riportato l'algoritmo del merge sort:
MergeSort(arr[], leftIndex, rightIndex)
if leftIndex >= rightIndex
return
else
Find the middle index that divides the array into two halves:
middleIndex = leftIndex + (rightIndex-leftIndex)/2
Call mergeSort() for the first half:
Call mergeSort(arr, leftIndex, middleIndex)
Call mergeSort() for the second half:
Call mergeSort(arr, middleIndex+1, rightIndex)
Merge the two halves sorted in step 2 and 3:
Call merge(arr, leftIndex, middleIndex, rightIndex)Correlati: 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 log) .
La migliore complessità temporale del merge sort: O (n log)
La complessità temporale del caso medio del merge sort: O (n log)
La complessità temporale del caso peggiore del merge sort: O (n log)
Imparentato: Che cos'è la notazione Big-O?
La complessità dello spazio ausiliario dell'algoritmo di merge sort è Sopra) come n spazio ausiliario è necessario nell'implementazione del merge sort.
Implementazione in C++ dell'algoritmo Merge Sort
Di seguito è riportata l'implementazione C++ dell'algoritmo di ordinamento di unione:
// C++ implementation of the
// merge sort algorithm
#include
using namespace std;
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
void merge(int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
int L[leftSubarraySize], R[rightSubarraySize];
// Copying data to temporary arrays L[] and R[]
for (int i = 0; i L[i] = arr[leftIndex + i];
for (int j = 0; j R[j] = arr[middleIndex + 1 + j];
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
int i = 0;
// Initial index of Right subarray
int j = 0;
// Initial index of merged subarray
int k = leftIndex;
while (i {
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i {
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int leftIndex, int rightIndex)
{
if(leftIndex >= rightIndex)
{
return;
}
int middleIndex = leftIndex + (rightIndex - leftIndex)/2;
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}
// Function to print the elements
// of the array
void printArray(int arr[], int size)
{
for (int i = 0; i {
cout << arr[i] << ' ';
}
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 16, 12, 15, 13, 19, 17, 11, 18 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << 'Unsorted array:' << endl;
printArray(arr, size);
mergeSort(arr, 0, size - 1);
cout << 'Sorted array:' << endl;
printArray(arr, size);
return 0;
} Produzione:
Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19Implementazione JavaScript dell'algoritmo Merge Sort
Di seguito è riportata l'implementazione JavaScript dell'algoritmo di ordinamento di unione:
// JavaScript implementation of the
// merge sort algorithm
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
function merge(arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
var L = new Array(leftSubarraySize);
var R = new Array(rightSubarraySize);
// Copying data to temporary arrays L[] and R[]
for(let i = 0; i L[i] = arr[leftIndex + i];
}
for (let j = 0; j R[j] = arr[middleIndex + 1 + j];
}
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
var i = 0;
// Initial index of Right subarray
var j = 0;
// Initial index of merged subarray
var k = leftIndex;
while (i {
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i {
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j {
arr[k] = R[j];
j++;
k++;
}
}
function mergeSort(arr, leftIndex, rightIndex) {
if(leftIndex >= rightIndex) {
return
}
var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}
// Function to print the elements
// of the array
function printArray(arr, size) {
for(let i = 0; i document.write(arr[i] + ' ');
}
document.write('
');
}
// Driver code:
var arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ];
var size = arr.length;
document.write('Unsorted array:
');
printArray(arr, size);
mergeSort(arr, 0, size - 1);
document.write('Sorted array:
');
printArray(arr, size); Produzione:
Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19Correlati: Programmazione dinamica: esempi, problemi comuni e soluzioni
Implementazione Python dell'algoritmo Merge Sort
Di seguito è riportata l'implementazione Python dell'algoritmo di ordinamento di unione:
# Python implementation of the
# merge sort algorithm
def mergeSort(arr):
if len(arr) > 1:
# Finding the middle index of the array
middleIndex = len(arr)//2
# Left half of the array
L = arr[:middleIndex]
# Right half of the array
R = arr[middleIndex:]
# Sorting the first half of the array
mergeSort(L)
# Sorting the second half of the array
mergeSort(R)
# Initial index of Left subarray
i = 0
# Initial index of Right subarray
j = 0
# Initial index of merged subarray
k = 0
# Copy data to temp arrays L[] and R[]
while i if L[i] arr[k] = L[i]
i = i + 1
else:
arr[k] = R[j]
j = j + 1
k = k + 1
# Checking if there're some remaining elements
while i arr[k] = L[i]
i = i + 1
k = k + 1
while j arr[k] = R[j]
j = j + 1
k = k + 1
# Function to print the elements
# of the array
def printArray(arr, size):
for i in range(size):
print(arr[i], end=' ')
print()
# Driver code
arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
size = len(arr)
print('Unsorted array:')
printArray(arr, size)
mergeSort(arr)
print('Sorted array:')
printArray(arr, size)
Produzione:
Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19Comprendere 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.
Condividere Condividere Tweet E-mail Introduzione all'algoritmo di Bubble SortL'algoritmo Bubble Sort: un'eccellente introduzione all'ordinamento degli array.
Leggi Avanti Argomenti correlati- Programmazione
- JavaScript
- Pitone
- Tutorial sulla programmazione
Yuvraj è uno studente universitario di Informatica presso l'Università di Delhi, in India. È appassionato di sviluppo Web Full Stack. Quando non scrive, esplora la profondità di diverse tecnologie.
Altro da Yuvraj ChandraIscriviti alla nostra Newsletter
Iscriviti alla nostra newsletter per suggerimenti tecnici, recensioni, ebook gratuiti e offerte esclusive!
Clicca qui per iscriverti