Sommario
- introduzione
- Cos'è Merge Sort in C++
- Approccio divide et impera
- Unisci algoritmo di ordinamento
- Implementazione di Merge Sort in C++
- Conclusione
1. Introduzione
Gli algoritmi di ordinamento in informatica vengono utilizzati per disporre i dati in ordine crescente o decrescente. Sono disponibili più algoritmi di ordinamento con proprietà distinte. Merge sort è uno dei metodi in C++ che può ordinare gli array.
2. Cos'è Merge Sort in C++
Merge sort utilizza la tecnica divide et impera che può disporre gli elementi di un array. Può anche ordinare l'elenco di elementi in C++. Divide l'input in due metà, ordina ciascuna metà in modo indipendente e quindi le unisce nell'ordine corretto.
3. Approccio divide et impera
L'algoritmo di ordinamento applica una strategia di divisione e conquista, che comporta il partizionamento dell'array di input in sottoarray più piccoli, risolvendoli separatamente e quindi unendo i risultati per produrre un output ordinato. Nel caso di merge sort, l'array viene diviso ricorsivamente in due metà finché non rimane un solo elemento in ciascuna metà.
4. Unisci algoritmo di ordinamento
L'algoritmo di merge sort consiste in due passaggi principali: dividere e unire. I passi sono come segue:
4.1 Dividi
L'algoritmo merge sort segue una strategia divide et impera per ordinare gli elementi in un array.
- Il primo passaggio dell'algoritmo controllerà gli elementi dell'array. Se contiene un elemento, è già considerato ordinato e l'algoritmo restituirà lo stesso array senza alcuna modifica.
- Se l'array contiene più di un elemento, l'algoritmo procede a dividerlo in due metà: la metà sinistra e la metà destra.
- L'algoritmo di merge sort viene quindi applicato in modo ricorsivo alle metà sinistra e destra dell'array, dividendole efficacemente in sottoarray più piccoli e ordinandole singolarmente.
- Questo processo ricorsivo continua fino a quando i sottoarray contengono un solo elemento ciascuno (come al passaggio 1), a quel punto possono essere uniti per produrre un array di output finale ordinato.
4.2 Unisci
Ora vedremo i passaggi per unire gli array:
- Il primo passo per l'algoritmo di merge sort comporta la creazione di un array vuoto.
- L'algoritmo procede quindi a confrontare i primi elementi delle metà sinistra e destra dell'array di input.
- Il più piccolo dei due elementi viene aggiunto al nuovo array e quindi rimosso dalla rispettiva metà dell'array di input.
- I passaggi 2-3 vengono quindi ripetuti finché una delle metà non viene svuotata.
- Eventuali elementi rimanenti nella metà non vuota vengono quindi aggiunti al nuovo array.
- L'array risultante è ora completamente ordinato e rappresenta l'output finale dell'algoritmo di merge sort.
5. Implementazione di Merge Sort in C++
Per implementare il merge sort in C++ vengono seguiti due diversi metodi. La complessità temporale di entrambi i metodi è equivalente, ma il loro utilizzo di sottoarray temporanei è diverso.
Il primo metodo per il merge sort in C++ usa due sottoarray temporanei, mentre il secondo ne usa solo uno. Vale la pena notare che la dimensione totale dei due sottoarray temporanei nel primo metodo è uguale alla dimensione dell'array originale nel secondo metodo, quindi la complessità dello spazio rimane costante.
Metodo 1: utilizzo di due subarray temporanei
Ecco un programma di esempio per unire sort in C++ utilizzando il metodo 1, che utilizza due sottoarray temporanei:
#includeutilizzando lo spazio dei nomi std ;
vuoto unire ( int arr [ ] , int l , int M , int R )
{
int n1 = M - l + 1 ;
int n2 = R - M ;
int l [ n1 ] , R [ n2 ] ;
per ( int io = 0 ; io < n1 ; io ++ )
l [ io ] = arr [ l + io ] ;
per ( int J = 0 ; J < n2 ; J ++ )
R [ J ] = arr [ M + 1 + J ] ;
int io = 0 , J = 0 , K = l ;
Mentre ( io < n1 && J < n2 ) {
Se ( l [ io ] <= R [ J ] ) {
arr [ K ] = l [ io ] ;
io ++;
}
altro {
arr [ K ] = R [ J ] ;
J ++;
}
K ++;
}
Mentre ( io < n1 ) {
arr [ K ] = l [ io ] ;
io ++;
K ++;
}
Mentre ( J < n2 ) {
arr [ K ] = R [ J ] ;
J ++;
K ++;
}
}
vuoto mergeSort ( int arr [ ] , int l , int R )
{
Se ( l < R ) {
int M = l + ( R - l ) / 2 ;
mergeSort ( arr , l , M ) ;
mergeSort ( arr , M + 1 , R ) ;
unire ( arr , l , M , R ) ;
}
}
int principale ( )
{
int arr [ ] = { 12 , undici , 13 , 5 , 6 , 7 } ;
int arr_size = taglia di ( arr ) / taglia di ( arr [ 0 ] ) ;
cout << 'L'array specificato è \N ' ;
per ( int io = 0 ; io < arr_size ; io ++ )
cout << arr [ io ] << ' ' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \N L'array ordinato è \N ' ;
per ( int io = 0 ; io < arr_size ; io ++ )
cout << arr [ io ] << ' ' ;
ritorno 0 ;
}
In questo programma, la funzione merge accetta tre argomenti arr, l e r, che rappresentano l'array da ordinare e mostrano gli indici del sottoarray che deve essere unito. La funzione prima trova le dimensioni dei due sottoarray da unire, quindi crea due sottoarray temporanei L e R per memorizzare gli elementi di questi sottoarray. Quindi confronta gli elementi in L e R e li unisce nell'array originale denominato arr in ordine crescente.
La tecnica divide et impera viene impiegata dalla funzione mergeSort per dividere l'array in due metà in modo ricorsivo fino a quando non rimane un solo elemento escluso nel sottoarray. Quindi unisce i due sottoarray in un sottoarray ordinato. La funzione continua a unire i sottoarray a meno che non ordini l'array completo.
Nella funzione principale, definiamo un array arr con 6 elementi e chiamiamo la funzione mergeSort per ordinarlo. Alla fine del codice viene stampato l'array ordinato.
Metodo 2: utilizzo di un sottoarray temporaneo
Ecco un programma di esempio per unire sort in C++ utilizzando il metodo 2, che utilizza un singolo sottoarray temporaneo:
#includeutilizzando lo spazio dei nomi std ;
vuoto unire ( int arr [ ] , int l , int M , int R )
{
int io , J , K ;
int n1 = M - l + 1 ;
int n2 = R - M ;
// Crea sottoarray temporanei
int l [ n1 ] , R [ n2 ] ;
// Copia i dati nei sottoarray
per ( io = 0 ; io < n1 ; io ++ )
l [ io ] = arr [ l + io ] ;
per ( J = 0 ; J < n2 ; J ++ )
R [ J ] = arr [ M + 1 + J ] ;
// Riunire i sottoarray temporanei nell'array originale
io = 0 ;
J = 0 ;
K = l ;
Mentre ( io < n1 && J < n2 ) {
Se ( l [ io ] <= R [ J ] ) {
arr [ K ] = l [ io ] ;
io ++;
}
altro {
arr [ K ] = R [ J ] ;
J ++;
}
K ++;
}
// Copia gli elementi rimanenti di L[]
Mentre ( io < n1 ) {
arr [ K ] = l [ io ] ;
io ++;
K ++;
}
// Copia gli elementi rimanenti di R[]
Mentre ( J < n2 ) {
arr [ K ] = R [ J ] ;
J ++;
K ++;
}
}
vuoto mergeSort ( int arr [ ] , int l , int R )
{
Se ( l < R ) {
int M = l + ( R - l ) / 2 ;
// Ordina le metà sinistra e destra in modo ricorsivo
mergeSort ( arr , l , M ) ;
mergeSort ( arr , M + 1 , R ) ;
// Unisci le due metà ordinate
unire ( arr , l , M , R ) ;
}
}
int principale ( )
{
int arr [ ] = { 12 , undici , 13 , 5 , 6 , 7 } ;
int arr_size = taglia di ( arr ) / taglia di ( arr [ 0 ] ) ;
cout << 'L'array specificato è \N ' ;
per ( int io = 0 ; io < arr_size ; io ++ )
cout << arr [ io ] << ' ' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \N L'array ordinato è \N ' ;
per ( int io = 0 ; io < arr_size ; io ++ )
cout << arr [ io ] << ' ' ;
ritorno 0 ;
}
Questo programma è come il precedente, ma invece di utilizzare due sottoarray temporanei L e R, utilizza un unico sottoarray temporaneo temp. La funzione di unione funziona allo stesso modo di prima, ma invece di copiare i dati in L e R, li copia in temp. Quindi unisce nuovamente gli elementi dell'array temporaneo nel file arr che è l'array originale.
La funzione mergeSort è la stessa di prima, tranne per il fatto che utilizza temp invece di L e R per memorizzare il sottoarray temporaneo.
Nella funzione principale, definiamo un array arr con 6 elementi e chiamiamo la funzione mergeSort per ordinarlo. L'esecuzione del codice termina stampando l'array ordinato sullo schermo.
Conclusione
Merge sort è un algoritmo che ordina gli elementi dell'array e utilizza la tecnica del divide et impera e fa confronti tra gli elementi. Merge sort in C++ ha una complessità temporale di O(n log n) ed è particolarmente efficace per l'ordinamento di array di grandi dimensioni. Sebbene richieda memoria aggiuntiva per memorizzare i sottoarray uniti, la sua stabilità lo rende una scelta popolare per l'ordinamento.