In questo tutorial imparerai a combinare l'ordinamento. Inoltre, troverai esempi funzionanti di merge sort C, C ++, Java e Python.
Merge Sort è uno degli algoritmi di ordinamento più popolari che si basa sul principio di Divide and Conquer Algorithm.
Qui, un problema è suddiviso in più sottoproblemi. Ogni problema secondario viene risolto individualmente. Infine, i problemi secondari vengono combinati per formare la soluzione finale.
Esempio di ordinamento unione
Divide and Conquer Strategy
Usando la tecnica Divide and Conquer , dividiamo un problema in sottoproblemi. Quando la soluzione per ogni sottoproblema è pronta, "combiniamo" i risultati dei sottoproblemi per risolvere il problema principale.
Supponiamo di dover ordinare un array A. Un sottoproblema sarebbe ordinare una sottosezione di questo array che inizia con l'indice pe termina con l'indice r, indicato come A (p… r).
Dividi
Se q è il punto a metà strada tra p e r, allora possiamo dividere il sottoarray A (p… r) in due array A (p… q) e A (q + 1, r).
Conquista
Nella fase di conquista, proviamo a ordinare entrambi i sottoarray A (p… q) e A (q + 1, r). Se non abbiamo ancora raggiunto il caso di base, dividiamo nuovamente entrambi i sottoarray e proviamo a ordinarli.
Combina
Quando il passo di conquista raggiunge il passo di base e otteniamo due sottoarray ordinati A (p … q) e A (q + 1, r) per l'array A (p … r), combiniamo i risultati creando un array ordinato A ( p… r) da due sottoarray ordinati A (p… q) e A (q + 1, r).
L'algoritmo MergeSort
La funzione MergeSort divide ripetutamente l'array in due metà fino a raggiungere uno stadio in cui proviamo a eseguire MergeSort su un sottoarray di dimensione 1, ad esempio p == r.
Successivamente, la funzione di unione entra in gioco e combina gli array ordinati in array più grandi fino a quando l'intero array viene unito.
MergeSort (A, p, r): se p> r return q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) merge (A, p, q, r )
Per ordinare un intero array, dobbiamo chiamare MergeSort(A, 0, length(A)-1).
Come mostrato nell'immagine sottostante, l'algoritmo di ordinamento di unione divide ricorsivamente l'array in metà fino a raggiungere il caso base dell'array con 1 elemento. Successivamente, la funzione di unione raccoglie i sotto-array ordinati e li unisce per ordinare gradualmente l'intero array.
Unisci l'ordinamento in azione
La fusione Passo di merge sort
Ogni algoritmo ricorsivo dipende da un caso base e dalla capacità di combinare i risultati dei casi base. L'ordinamento di unione non è diverso. La parte più importante dell'algoritmo di ordinamento di unione è, hai indovinato, passaggio di unione.
Il passaggio di unione è la soluzione al semplice problema di unire due elenchi ordinati (array) per creare un unico elenco ordinato (array) di grandi dimensioni.
L'algoritmo mantiene tre puntatori, uno per ciascuno dei due array e uno per mantenere l'indice corrente dell'array ordinato finale.
Abbiamo raggiunto la fine di uno qualsiasi degli array? No: confronta gli elementi correnti di entrambi gli array Copia l'elemento più piccolo nell'array ordinato Sposta il puntatore dell'elemento contenente l'elemento più piccolo Sì: copia tutti gli elementi rimanenti dell'array non vuoto
Unisci passaggio
Scrittura del codice per l'algoritmo di unione
Una differenza notevole tra la fase di unione che abbiamo descritto sopra e quella che usiamo per l'ordinamento di unione è che eseguiamo la funzione di unione solo su sotto-array consecutivi.
Questo è il motivo per cui abbiamo bisogno solo dell'array, della prima posizione, dell'ultimo indice del primo sottoarray (possiamo calcolare il primo indice del secondo sottoarray) e dell'ultimo indice del secondo sottoarray.
Il nostro compito è unire due sottoarray A (p… q) e A (q + 1… r) per creare un array ordinato A (p… r). Quindi gli input per la funzione sono A, p, q e r
La funzione di unione funziona come segue:
- Crea copie dei sottoarray
L ← A(p… q)e M ← A (q + 1… r). - Crea tre puntatori i, j e k
- mantiene l'indice corrente di L, a partire da 1
- j mantiene l'indice corrente di M, a partire da 1
- k mantiene l'indice corrente di A (p… q), a partire da p.
- Finché non raggiungiamo la fine di L o M, scegli il più grande tra gli elementi da L e M e posizionali nella posizione corretta in A (p… q)
- Quando esauriamo gli elementi in L o M, raccogliamo gli elementi rimanenti e inseriamo A (p … q)
Nel codice, questo sarebbe simile a:
// Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Funzione Merge () spiegata passo dopo passo
Stanno accadendo molte cose in questa funzione, quindi facciamo un esempio per vedere come funzionerebbe.
Come al solito, un'immagine parla più di mille parole.
Unione di due sottoarray consecutivi di array
La matrice A (0… 5) contiene due sottoarray ordinati A (0… 3) e A (4… 5). Vediamo come la funzione di unione unirà i due array.
void merge(int arr(), int p, int q, int r) ( // Here, p = 0, q = 4, r = 6 (size of array)
Passaggio 1: creare copie duplicate di sotto-array da ordinare
// Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1 = 3 - 0 + 1 = 4; int n2 = r - q = 5 - 3 = 2; int L(4), M(2); for (int i = 0; i < 4; i++) L(i) = arr(p + i); // L(0,1,2,3) = A(0,1,2,3) = (1,5,10,12) for (int j = 0; j < 2; j++) M(j) = arr(q + 1 + j); // M(0,1,2,3) = A(4,5) = (6,9) 
Crea copie di sottoarray per l'unione
Passaggio 2: mantenere l'indice corrente dei sotto-array e dell'array principale
int i, j, k; i = 0; j = 0; k = p; 
Mantieni gli indici delle copie del sotto-array e dell'array principale
Passaggio 3: fino a quando non raggiungiamo la fine di L o M, scegli il più grande tra gli elementi L e M e posizionali nella posizione corretta in A (p … r)
while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) 
Confrontando i singoli elementi dei sottoarray ordinati fino alla fine di uno
Passaggio 4: quando esauriamo gli elementi in L o M, raccogliamo gli elementi rimanenti e inseriamo A (p … r)
// We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; ) 
Copia gli elementi rimanenti dal primo array al sottoarray principale
// We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) ) 
Copia gli elementi rimanenti del secondo array nel sottoarray principale
Questo passaggio sarebbe stato necessario se la dimensione di M fosse maggiore di L.
Alla fine della funzione di unione, viene ordinato il sottoarray A (p… r).
Esempi di Python, Java e C / C ++
Python Java C C ++ # MergeSort in Python def mergeSort(array): if len(array)> 1: # r is the point where the array is divided into two subarrays r = len(array)//2 L = array(:r) M = array(r:) # Sort the two halves mergeSort(L) mergeSort(M) i = j = k = 0 # Until we reach either end of either L or M, pick larger among # elements L and M and place them in the correct position at A(p… r) while i < len(L) and j < len(M): if L(i) < M(j): array(k) = L(i) i += 1 else: array(k) = M(j) j += 1 k += 1 # When we run out of elements in either L or M, # pick up the remaining elements and put in A(p… r) while i < len(L): array(k) = L(i) i += 1 k += 1 while j < len(M): array(k) = M(j) j += 1 k += 1 # Print the array def printList(array): for i in range(len(array)): print(array(i), end=" ") print() # Driver program if __name__ == '__main__': array = (6, 5, 12, 10, 9, 1) mergeSort(array) print("Sorted array is: ") printList(array)
// Merge sort in Java class MergeSort ( // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L() = new int(n1); int M() = new int(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = (l + r) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver program public static void main(String args()) ( int arr() = ( 6, 5, 12, 10, 9, 1 ); MergeSort ob = new MergeSort(); ob.mergeSort(arr, 0, arr.length - 1); System.out.println("Sorted array:"); printArray(arr); ) )
// Merge sort in C #include // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) printf("%d ", arr(i)); printf(""); ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); printf("Sorted array: "); printArray(arr, size); )
// Merge sort in C++ #include using namespace std; // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) cout << arr(i) << " "; cout << endl; ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); cout << "Sorted array: "; printArray(arr, size); return 0; )
Unisci ordinamento complessità
Complessità temporale
Complessità caso migliore: O (n * log n)
Complessità caso peggiore: O (n * log n)
Complessità case media: O (n * log n)
Complessità spaziale
La complessità spaziale del merge sort è O (n).
Unisci le applicazioni di ordinamento
- Problema di conteggio delle inversioni
- Ordinamento esterno
- Applicazioni di e-commerce
