Taula de continguts
- Introducció
- Què és Merge Sort en C++
- Enfocament divideix i vencem
- Algoritme d'ordenació combinada
- Implementació de Merge Sort en C++
- Conclusió
1. Introducció
Els algorismes d'ordenació en informàtica s'utilitzen per ordenar les dades en ordre ascendent o descendent. Hi ha diversos algorismes d'ordenació amb propietats diferents disponibles. L'ordenació combinada és un dels mètodes de C++ que pot ordenar les matrius.
2. Què és Merge Sort en C++
L'ordenació per combinació utilitza la tècnica de dividir i conquerir que pot organitzar els elements d'una matriu. També pot ordenar la llista d'elements en C++. Divideix l'entrada en dues meitats, ordena cadascuna de manera independent i després les fusiona en l'ordre correcte.
3. Enfocament Divide and Conquer
L'algorisme d'ordenació aplica una estratègia de dividir i conquerir, que consisteix a dividir la matriu d'entrada en subarrays més petits, resoldre'ls per separat i, a continuació, fusionar els resultats per produir una sortida ordenada. En el cas de l'ordenació per fusió, la matriu es divideix de forma recursiva en dues meitats fins que només queda un element a cada meitat.
4. Combinar algorisme d'ordenació
L'algorisme d'ordenació de combinació consta de dos passos principals: dividir i combinar. Els passos són els següents:
4.1 Dividir
L'algorisme d'ordenació combinada segueix una estratègia de dividir i conquerir per ordenar els elements d'una matriu.
- El primer pas de l'algorisme comprovarà els elements de la matriu. Si conté un element, ja es considera ordenat i l'algorisme retornarà la mateixa matriu sense cap canvi.
- Si la matriu conté més d'un element, l'algorisme procedeix a dividir-lo en dues meitats: la meitat esquerra i la meitat dreta.
- L'algoritme d'ordenació de combinació s'aplica de forma recursiva a les meitats esquerra i dreta de la matriu, dividint-les de manera efectiva en subbarrays més petits i ordenant-los individualment.
- Aquest procés recursiu continua fins que els subbarrays contenen només un element cadascun (segons el pas 1), moment en què es poden fusionar per produir una matriu de sortida ordenada final.
4.2 Fusionar
Ara veurem els passos per combinar les matrius:
- El primer pas per a l'algorisme d'ordenació de combinació consisteix a crear una matriu buida.
- A continuació, l'algorisme procedeix a comparar els primers elements de les meitats esquerra i dreta de la matriu d'entrada.
- El més petit dels dos elements s'afegeix a la nova matriu i després s'elimina de la seva meitat respectiva de la matriu d'entrada.
- A continuació, es repeteixen els passos 2-3 fins que es buidi una de les meitats.
- Els elements restants a la meitat no buida s'afegeixen a la nova matriu.
- La matriu resultant ara està completament ordenada i representa la sortida final de l'algorisme d'ordenació de combinació.
5. Implementació de Merge Sort en C++
Per implementar l'ordenació combinada en C++ es segueixen dos mètodes diferents. La complexitat temporal d'ambdós mètodes és equivalent, però el seu ús de subbarrays temporals és diferent.
El primer mètode per a l'ordenació de combinació en C++ utilitza dos subbarrays temporals, mentre que el segon només n'utilitza un. Val la pena assenyalar que la mida total dels dos subarrays temporals del primer mètode és igual a la mida de la matriu original del segon mètode, de manera que la complexitat de l'espai es manté constant.
Mètode 1: ús de dos subbarrays temporals
Aquí hi ha un exemple de programa per a l'ordenació de combinacions en C++ mitjançant el Mètode 1, que utilitza dos subbarrays temporals:
#inclouutilitzant l'espai de noms std ;
buit fusionar ( int arr [ ] , int l , int m , int r )
{
int n1 = m - l + 1 ;
int n2 = r - m ;
int L [ n1 ] , R [ n2 ] ;
per ( int i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
per ( int j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
int i = 0 , j = 0 , k = l ;
mentre ( i < n1 && j < n2 ) {
si ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
altra cosa {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
mentre ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
mentre ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
buit mergeSort ( int arr [ ] , int l , int r )
{
si ( l < r ) {
int m = l + ( r - l ) / 2 ;
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
fusionar ( arr , l , m , r ) ;
}
}
int principal ( )
{
int arr [ ] = { 12 , 11 , 13 , 5 , 6 , 7 } ;
int arr_size = mida de ( arr ) / mida de ( arr [ 0 ] ) ;
cout << 'La matriu donada és \n ' ;
per ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n La matriu ordenada és \n ' ;
per ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
tornar 0 ;
}
En aquest programa, la funció de combinació pren tres arguments arr, l i r, que representen la matriu que s'ha d'ordenar i mostra els índexs de la subbarra que cal combinar. La funció primer troba les mides dels dos subbarrals que s'han de combinar, després crea dos subbarras temporals L i R per emmagatzemar els elements d'aquests subbarras. A continuació, compara els elements de L i R i els fusiona a la matriu original anomenada arr en ordre ascendent.
La funció mergeSort utilitza la tècnica de dividir i vencer per dividir la matriu en dues meitats de forma recursiva fins que només quedi un element al subarray. A continuació, fusiona els dos subbarrays en un subbarray ordenat. La funció continua fusionant els subarrays tret que ordeni la matriu completa.
A la funció principal, definim una matriu arr amb 6 elements i cridem a la funció mergeSort per ordenar-la. Al final del codi, s'imprimeix la matriu ordenada.
Mètode 2: Ús de One Temp Subbarray
Aquí hi ha un exemple de programa per a l'ordenació de combinacions en C++ mitjançant el Mètode 2, que utilitza un sol subbarray temporal:
#inclouutilitzant l'espai de noms std ;
buit fusionar ( int arr [ ] , int l , int m , int r )
{
int i , j , k ;
int n1 = m - l + 1 ;
int n2 = r - m ;
// Crea subbarras temporals
int L [ n1 ] , R [ n2 ] ;
// Copia dades a subbarrays
per ( i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
per ( j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
// Combineu els subarrays temporals de nou a la matriu original
i = 0 ;
j = 0 ;
k = l ;
mentre ( i < n1 && j < n2 ) {
si ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
altra cosa {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
// Copia els elements restants de L[]
mentre ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
// Copia els elements restants de R[]
mentre ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
buit mergeSort ( int arr [ ] , int l , int r )
{
si ( l < r ) {
int m = l + ( r - l ) / 2 ;
// Ordena les meitats esquerra i dreta de manera recursiva
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
// Combina les dues meitats ordenades
fusionar ( arr , l , m , r ) ;
}
}
int principal ( )
{
int arr [ ] = { 12 , 11 , 13 , 5 , 6 , 7 } ;
int arr_size = mida de ( arr ) / mida de ( arr [ 0 ] ) ;
cout << 'La matriu donada és \n ' ;
per ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n La matriu ordenada és \n ' ;
per ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
tornar 0 ;
}
Aquest programa és com l'anterior, però en comptes d'utilitzar dos subbarrays temporals L i R, utilitza un sol subbarray temporal. La funció de combinació funciona de la mateixa manera que abans, però en lloc de copiar les dades a L i R, les copia a temp. A continuació, fusiona els elements de la matriu temporal al fitxer arr que és la matriu original.
La funció mergeSort és la mateixa que abans, excepte que utilitza temp en lloc de L i R per emmagatzemar el subbarray temporal.
A la funció principal, definim una matriu arr amb 6 elements i cridem a la funció mergeSort per ordenar-la. L'execució del codi acaba imprimint la matriu ordenada a la pantalla.
Conclusió
L'ordenació combinada és un algorisme que ordena els elements de la matriu i utilitza la tècnica de dividir i vencer i fa comparacions entre elements. L'ordenació combinada en C++ té una complexitat temporal de O(n log n) i és especialment eficaç per ordenar matrius grans. Tot i que requereix memòria addicional per emmagatzemar els subbarrays combinats, la seva estabilitat el converteix en una opció popular per ordenar.