Merge sort è uno degli algoritmi informatici di base, formulato nel 1945 dal grande matematico John von Neumann. Durante la partecipazione al Progetto Manhattan, Neumann ha dovuto affrontare la necessità di elaborare in modo efficiente enormi quantità di dati. Il metodo da lui sviluppato utilizzava il principio del "divide et impera", che riduceva notevolmente il tempo necessario per il lavoro.
Principio e uso dell'algoritmo
Il metodo merge sort viene utilizzato nei problemi di ordinamento delle strutture che hanno ordinato l'accesso agli elementi, come array, liste, stream.
Durante l'elaborazione, il blocco dati iniziale viene suddiviso in piccole componenti, fino a un elemento, che di fatto è già un elenco ordinato. Quindi viene rimontato nell'ordine corretto.
L'ordinamento di un array di una certa lunghezza richiede un'area di memoria aggiuntiva della stessa dimensione, in cui l'array ordinato viene raccolto in parti.
Il metodo può essere utilizzato per ordinare qualsiasi tipo di dati comparabile, come numeri o stringhe.
Unisci ordinatotrame
Per capire l'algoritmo, iniziamo la sua analisi dalla fine, dal meccanismo di unire i blocchi ordinati.
Immaginiamo di avere due array di numeri ordinati in qualsiasi modo che devono essere combinati tra loro in modo che l'ordinamento non venga interrotto. Per semplicità, ordineremo i numeri in ordine crescente.
Esempio elementare: entrambi gli array sono costituiti da un elemento ciascuno.
int arr1={31}; int arr2={18};
Per unirli, devi prendere l'elemento zero del primo array (non dimenticare che la numerazione parte da zero) e l'elemento zero del secondo array. Questi sono, rispettivamente, 31 e 18. Secondo la condizione di ordinamento, il numero 18 dovrebbe venire per primo, poiché è inferiore. Metti i numeri nell'ordine corretto:
int risultato={18, 31};
Diamo un'occhiata a un esempio più complicato, in cui ogni array è composto da diversi elementi:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
L'algoritmo di unione consisterà nel confrontare in sequenza elementi più piccoli e posizionarli nell'array risultante nell'ordine corretto. Per tenere traccia degli indici correnti, introduciamo due variabili: index1 e index2. Inizialmente, li impostiamo a zero, poiché gli array sono ordinati e gli elementi più piccoli si trovano all'inizio.
int index1=0; int index2=0;
Scriviamo l'intero processo di fusione passo dopo passo:
- Prendi l'elemento con index1 dall'array arr1 e l'elemento con index2 dall'array arr2.
- Confronta, seleziona il più piccolo e inseriscilomatrice risultante.
- Incrementa l'indice corrente dell'elemento più piccolo di 1.
- Continua dal primo passaggio.
Nella prima orbita, la situazione apparirà così:
indice1=0; indice2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; indice1++; risultato[0]=arr1[0]; // risultato=[2]
Al secondo turno:
indice1=1; indice2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; indice2++; risultato[1]=arr2[0]; // risultato=[2, 5]
Terzo:
indice1=1; indice2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; indice2++; risultato[2]=arr2[1]; // risultato=[2, 5, 6]
E così via, finché il risultato non è un array completamente ordinato: {2, 5, 6, 17, 21, 19, 30, 45}.
Alcune difficoltà possono sorgere se si uniscono array con lunghezze diverse. Cosa succede se uno degli indici correnti ha raggiunto l'ultimo elemento e ci sono ancora membri rimasti nel secondo array?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 passo indice1=0, indice2=0; 1 2 risultato={1, 2}; // 3 passi indice1=1, indice2=1; 4 < 5 risultato={1, 2, 4}; //4 step index1=2, index2=1 ??
La variabile index1 ha raggiunto il valore 2, ma l'array arr1 non ha un elemento con quell'indice. Qui tutto è semplice: basta trasferire gli elementi rimanenti del secondo array in quello risultante, preservandone l'ordine.
risultato={1, 2, 4, 5, 6, 7, 9};
Questa situazione ci indica la necessitàabbina l'indice di controllo corrente con la lunghezza dell'array da unire.
Schema di unione per sequenze ordinate (A e B) di diverse lunghezze:
- Se la lunghezza di entrambe le sequenze è maggiore di 0, confronta A[0] e B[0] e sposta quella più piccola nel buffer.
- Se la lunghezza di una delle sequenze è 0, prendi gli elementi rimanenti della seconda sequenza e, senza cambiarne l'ordine, spostati alla fine del buffer.
Attuazione della seconda fase
Di seguito è riportato un esempio di unione di due array ordinati in Java.
int a1=new int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=nuovo int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=nuovo int[a1.lunghezza + a2.lunghezza]; int i=0, j=0; for (int k=0; k a1.lunghezza-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=a; i++; } else if (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } altro { int b=a2[j]; a3[k]=b; j++; } }
Qui:
- a1 e a2 sono gli array ordinati originali da unire;
- a3 – matrice finale;
- i e j sono indici degli elementi correnti per gli array a1 e a2.
La prima e la seconda condizione se assicurano che gli indici non vadano oltre la dimensione dell'array. Il terzo e il quarto blocco di condizione, rispettivamente, vengono spostati nell'array risultante dell'elemento più piccolo.
Dividi e conquista
Quindi, abbiamo imparato a unire gli ordinatiraccolte di valori. Si può dire che la seconda parte dell'algoritmo di merge sort - l'unione stessa - è già stata ordinata.
Tuttavia, devi ancora capire come passare dalla matrice originale non ordinata di numeri a più numeri ordinati che possono essere uniti.
Consideriamo la prima fase dell'algoritmo e impariamo come separare gli array.
Questo non è difficile: l'elenco originale dei valori è diviso a metà, quindi ogni parte è anche biforcata e così via fino a ottenere blocchi molto piccoli.
La lunghezza di tali elementi minimi può essere uguale a uno, ovvero possono essere essi stessi un array ordinato, ma questa non è una condizione necessaria. La dimensione del blocco è determinata in anticipo e per ordinarlo è possibile utilizzare qualsiasi algoritmo di ordinamento adatto che funzioni in modo efficiente con array di piccole dimensioni (ad esempio, quicksort o ordinamento per inserimento).
Sembra così.
// array originale {34, 95, 10, 2, 102, 70}; // prima divisione {34, 95, 10} e {2, 102, 70}; // secondo split {34} e {95, 10} e {2} e {102, 70}
I blocchi risultanti, composti da 1-2 elementi, sono molto facili da organizzare.
Dopodiché, devi unire i piccoli array già ordinati a coppie, preservando l'ordine dei membri, cosa che abbiamo già imparato a fare.
Attuazione della prima fase
Il partizionamento ricorsivo di un array è mostrato di seguito.
void mergeSort(T a, long start, long finish) { long split; Se(inizio < arrivo) { split=(inizio + arrivo)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); merge(a, start, split, finish); } }
Cosa succede in questo codice:
-
La funzione mergeSort ottiene l'array iniziale
a
e i bordi sinistro e destro della regione da ordinare (gli indici iniziano e
- finish).
-
Se la lunghezza di questa sezione è maggiore di uno (
inizio < fine
), allora è divisa in due parti (per indice
- split), e ciascuno viene ordinato ricorsivamente.
-
Nella funzione ricorsiva call per il lato sinistro, vengono passati l'indice iniziale del grafico e l'indice
split
. Per quello di destra, rispettivamente, l'inizio sarà
- (split + 1), e la fine sarà l'ultimo indice della sezione originale.
-
Funzione
merge
ottiene due sequenze ordinate (
a[start]…a[split]
e
- a[split +1]…a[finish]) e li unisce in ordine di ordinamento.
I meccanismi della funzione di unione sono discussi sopra.
Schema generale dell'algoritmo
Il metodo merge sort array consiste in due grandi passaggi:
- Dividi l'array originale non ordinato in piccoli pezzi.
- Raccoglili a coppie, seguendo la regola di ordinamento.
Un compito grande e complesso viene suddiviso in molti compiti semplici, che vengono risolti in sequenza, portando al risultato desiderato.
Valutazione del metodo
La complessità temporale dell'ordinamento unione è determinata dall' altezza dell'albero divisoalgoritmo ed è uguale al numero di elementi nell'array (n) moltiplicato per il suo logaritmo (log n). Tale stima è chiamata logaritmica.
Questo è sia un vantaggio che uno svantaggio del metodo. Il suo tempo di esecuzione non cambia nemmeno nel peggiore dei casi, quando l'array originale viene ordinato in ordine inverso. Tuttavia, quando si elaborano dati completamente ordinati, l'algoritmo non fornisce un guadagno di tempo.
È anche importante notare il costo della memoria del metodo di ordinamento unione. Sono uguali alle dimensioni della collezione originale. In quest'area addizionalmente allocata, un array ordinato viene assemblato dai pezzi.
Implementazione dell'algoritmo
L'ordinamento unione Pascal è mostrato di seguito.
Procedura MergeSort(name: string; var f: text); Var a1, a2, s, i, j, kol, tmp: intero; f1, f2: testo; b: booleano Inizio col:=0; Assegna(f, nome); ripristinare(f); Sebbene non EOF(f) inizi read(f, a1); inc(col); fine; chiudere(f); Assign(f1, '{nome del 1° file ausiliario}'); Assign(f2, '{nome del 2° file ausiliario}'); s:=1; Mentre (s<kol) inizia Reset(f); riscrivi(f1); riscrivi(f2); Da i:=1 a kol div 2 inizia Read(f, a1); Scrivi(f1, a1, ' '); fine; Se (kol div 2) mod s0 allora inizia tmp:=kol div 2; Mentre tmp mod s0 inizia Read(f, a1); Scrivi(f1, a1, ' '); inc(tmp); fine; fine; Sebbene non EOF(f) inizi Read(f, a2); Scrivi(f2, a2, ' '); fine; chiudere(f); chiudere(f1); chiudere(f2); riscrivi(f); ripristinare(f1); ripristinare(f2); Leggi(f1, a1); Leggi(f2, a2); Mentre (non EOF(f1)) e (non EOF(f2)) iniziano i:=0; j:=0; b:=vero; Mentre (b) e (non EOF(f1)) e (non EOF(f2)) iniziano Se (a1<a2) allora inizianoScrivi(f, a1, ' '); Leggi(f1, a1); inc(i); Fine altrimenti inizio Scrivi(f, a2, ' '); Leggi(f2, a2); inc(j); fine; Se (i=s) o (j=s) allora b:=falso; fine; Se non b allora inizia While (i<s) e (non EOF(f1)) iniziano Write(f, a1, ' '); Leggi(f1, a1); inc(i); fine; Mentre (j<s) e (non EOF(f2)) iniziano Write(f, a2, ' '); Leggi(f2, a2); inc(j); fine; fine; fine; Anche se non EOF(f1) inizia tmp:=a1; Leggi(f1, a1); Se non EOF(f1) allora Write(f, tmp, ' ') else Write(f, tmp); fine; Sebbene non EOF(f2) inizi tmp:=a2; Leggi(f2, a2); Se non EOF(f2) allora Write(f, tmp, ' ') else Write(f, tmp); fine; chiudere(f); chiudere(f1); chiudere(f2); s:=s2; fine; Cancella(f1); Cancella(f2); Fine;
Visivamente, il funzionamento dell'algoritmo è simile a questo (in alto - sequenza non ordinata, in basso - ordinato).
Ordinamento dati esterni
Molto spesso è necessario ordinare alcuni dati che si trovano nella memoria esterna del computer. In alcuni casi, sono di dimensioni impressionanti e non possono essere inseriti nella RAM per facilitarne l'accesso. In questi casi vengono utilizzati metodi di ordinamento esterno.
La necessità di accedere a supporti esterni riduce l'efficienza del tempo di elaborazione.
La complessità del lavoro è che l'algoritmo può accedere solo a un elemento del flusso di dati alla volta. E in questo caso, uno dei migliori risultati è mostrato dal metodo merge sort, che può confrontare gli elementi di due file in sequenza uno dopo l' altro.
Lettura dei dati dasorgente esterna, la loro elaborazione e scrittura nel file finale avviene in blocchi ordinati (serie). A seconda del modo di lavorare con le dimensioni delle serie ordinate, esistono due tipi di ordinamento: semplice e naturale.
Unione semplice
Con una semplice unione, la lunghezza della serie viene fissata.
Quindi, nel file originale non ordinato, tutte le serie sono costituite da un elemento. Dopo il primo passaggio, la dimensione aumenta a due. Successivo - 4, 8, 16 e così via.
Funziona così:
- Il file sorgente (f) è diviso in due file ausiliari: f1, f2.
- Sono nuovamente uniti in un file (f), ma allo stesso tempo tutti gli elementi vengono confrontati a coppie e formano coppie. La dimensione della serie in questo passaggio diventa due.
- Il passaggio 1 viene ripetuto.
- Il passaggio 2 viene ripetuto, ma i 2 già ordinati vengono uniti per formare 4 ordinati.
- Il ciclo continua, aumentando la serie ad ogni iterazione, finché l'intero file non viene ordinato.
Come fai a sapere che l'ordinamento esterno con una semplice unione è completo?
- lunghezza della nuova serie (dopo la fusione) non inferiore al numero totale di elementi;
- manca solo un episodio;
- Il file ausiliario f2 è stato lasciato vuoto.
Gli svantaggi di una semplice unione sono: poiché la lunghezza della corsa è fissata su ogni passaggio di unione, i dati parzialmente ordinati impiegheranno tutto il tempo per essere elaborati come dati completamente casuali.
Fusione naturale
Questo metodo non limita la lunghezzaserie, ma sceglie il massimo possibile.
Algoritmo di ordinamento:
- Lettura della sequenza iniziale dal file f. Il primo elemento ricevuto viene scritto nel file f1.
- Se la voce successiva soddisfa la condizione di ordinamento, viene scritta lì, in caso contrario, nel secondo file ausiliario f2.
- In questo modo vengono distribuiti tutti i record del file sorgente e viene formata una sequenza ordinata in f1, che determina la dimensione corrente della serie.
- I file f1 e f2 vengono uniti.
- Il ciclo si ripete.
A causa delle dimensioni non fisse della serie, è necessario contrassegnare la fine della sequenza con un carattere speciale. Pertanto, durante la fusione, il numero di confronti aumenta. Inoltre, la dimensione di uno dei file ausiliari potrebbe essere vicina alla dimensione dell'originale.
In media, l'unione naturale è più efficiente della semplice unione con l'ordinamento esterno.
Caratteristiche dell'algoritmo
Quando si confrontano due valori identici, il metodo conserva il loro ordine originale, ovvero è stabile.
Il processo di ordinamento può essere suddiviso con successo in più thread.
Il video mostra chiaramente il funzionamento dell'algoritmo di merge sort.
