Cuprins
- Introducere
- Ce este Merge Sort în C++
- Abordarea Divide and Conquer
- Algoritmul de sortare fuzionare
- Implementarea Merge Sort în C++
- Concluzie
1. Introducere
Algoritmii de sortare în informatică sunt utilizați pentru a aranja datele în ordine crescătoare sau descrescătoare. Există mai mulți algoritmi de sortare cu proprietăți distincte disponibile. Merge sort este una dintre metodele din C++ care poate sorta matricele.
2. Ce este Merge Sort în C++
Sortarea prin îmbinare folosește tehnica divide-and-conquer care poate aranja elementele unei matrice. De asemenea, poate sorta lista de elemente în C++. Împarte intrarea în două jumătăți, sortează fiecare jumătate independent și apoi le îmbină în ordinea corectă.
3. Abordarea împărțiți și cuceriți
Algoritmul de sortare aplică o strategie de împărțire și cucerire, care implică partiționarea matricei de intrare în subgrupuri mai mici, rezolvarea lor separat și apoi îmbinarea rezultatelor pentru a produce o ieșire sortată. În cazul sortării prin îmbinare, matricea este împărțită recursiv în două jumătăți până când rămâne doar un element în fiecare jumătate.
4. Algoritmul de sortare fuzionare
Algoritmul de sortare de îmbinare constă din doi pași principali: împărțire și îmbinare. Pașii sunt următorii:
4.1 Împărțiți
Algoritmul de sortare de îmbinare urmează o strategie de împărțire și cucerire pentru sortarea elementelor dintr-o matrice.
- Primul pas al algoritmului va verifica elementele matricei. Dacă conține un element, atunci este deja considerat sortat, iar algoritmul va returna aceeași matrice fără nicio modificare.
- Dacă matricea conține mai mult de un element, algoritmul procedează să îl împartă în două jumătăți: jumătatea stângă și jumătatea dreaptă.
- Algoritmul de sortare de îmbinare este apoi aplicat recursiv la jumătățile din stânga și din dreapta ale matricei, împărțindu-le efectiv în subgrupuri mai mici și sortându-le individual.
- Acest proces recursiv continuă până când sub-tabele conțin doar un element fiecare (conform pasului 1), moment în care pot fi îmbinate pentru a produce o matrice finală, sortată.
4.2 Fuzionare
Acum vom vedea pașii pentru a îmbina matricele:
- Primul pas pentru algoritmul de sortare de îmbinare implică crearea unei matrice goale.
- Algoritmul continuă apoi să compare primele elemente ale jumătăților din stânga și din dreapta ale tabloului de intrare.
- Cel mai mic dintre cele două elemente este adăugat la noua matrice și apoi eliminat din jumătatea respectivă a matricei de intrare.
- Pașii 2-3 se repetă apoi până când una dintre jumătăți este golită.
- Orice elemente rămase din jumătatea nevidă sunt apoi adăugate la noua matrice.
- Matricea rezultată este acum complet sortată și reprezintă rezultatul final al algoritmului de sortare de îmbinare.
5. Implementarea Merge Sort în C++
Pentru a implementa sortarea prin îmbinare în C++ sunt urmate două metode diferite. Complexitatea timpului a ambelor metode este echivalentă, dar utilizarea lor a sub-taxelor temporare diferă.
Prima metodă pentru sortarea de îmbinare în C++ folosește două subbariere temporare, în timp ce a doua utilizează doar una. Este demn de remarcat faptul că dimensiunea totală a celor două subbaryuri temporare din prima metodă este egală cu dimensiunea matricei originale din a doua metodă, astfel încât complexitatea spațiului rămâne constantă.
Metoda 1 – Folosirea a două subbariere de temperatură
Iată un exemplu de program pentru sortarea îmbinării în C++ utilizând Metoda 1, care utilizează două subbariere temporare:
#includefolosind namespace std ;
gol combina ( int arr [ ] , int l , int m , int r )
{
int n1 = m - l + 1 ;
int n2 = r - m ;
int L [ n1 ] , R [ n2 ] ;
pentru ( int i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
pentru ( int j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
int i = 0 , j = 0 , k = l ;
in timp ce ( i < n1 && j < n2 ) {
dacă ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
altfel {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
in timp ce ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
in timp ce ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
gol mergeSort ( int arr [ ] , int l , int r )
{
dacă ( l < r ) {
int m = l + ( r - l ) / 2 ;
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
combina ( arr , l , m , r ) ;
}
}
int principal ( )
{
int arr [ ] = { 12 , unsprezece , 13 , 5 , 6 , 7 } ;
int arr_size = dimensiunea ( arr ) / dimensiunea ( arr [ 0 ] ) ;
cout << „Matricea dată este \n ' ;
pentru ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Matrice sortată este \n ' ;
pentru ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
întoarcere 0 ;
}
În acest program, funcția de îmbinare ia trei argumente arr, l și r, care reprezintă tabloul care trebuie sortat și arată indicii sub-tabelului care trebuie îmbinat. Funcția găsește mai întâi dimensiunile celor două submagazine care urmează să fie îmbinate, apoi creează două submagazine temporare L și R pentru a stoca elementele acestor submagazine. Apoi compară elementele din L și R și le îmbină în matricea originală numită arr în ordine crescătoare.
Tehnica divide-and-conquer este folosită de funcția mergeSort pentru a împărți matricea în două jumătăți în mod recursiv, până când nu rămâne decât un singur element în subbary. Apoi, îmbină cele două subdivioane într-un subbary sortat. Funcția continuă să îmbine sub-tabele, cu excepția cazului în care sortează matricea completă.
În funcția principală, definim o matrice arr cu 6 elemente și apelăm funcția mergeSort pentru a o sorta. La sfârșitul codului, matricea sortată este tipărită.
Metoda 2 – Folosirea One Temp Subbarray
Iată un exemplu de program pentru sortarea îmbinării în C++ folosind Metoda 2, care utilizează un singur subbary temporar:
#includefolosind namespace std ;
gol combina ( int arr [ ] , int l , int m , int r )
{
int i , j , k ;
int n1 = m - l + 1 ;
int n2 = r - m ;
// Creați subbariere temporare
int L [ n1 ] , R [ n2 ] ;
// Copiați datele în subbariere
pentru ( i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
pentru ( j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
// Îmbină subtabelele temporare înapoi în tabloul original
i = 0 ;
j = 0 ;
k = l ;
in timp ce ( i < n1 && j < n2 ) {
dacă ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
altfel {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
// Copiați elementele rămase din L[]
in timp ce ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
// Copiați elementele rămase din R[]
in timp ce ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
gol mergeSort ( int arr [ ] , int l , int r )
{
dacă ( l < r ) {
int m = l + ( r - l ) / 2 ;
// Sortează recursiv jumătățile stângă și dreaptă
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
// Îmbină cele două jumătăți sortate
combina ( arr , l , m , r ) ;
}
}
int principal ( )
{
int arr [ ] = { 12 , unsprezece , 13 , 5 , 6 , 7 } ;
int arr_size = dimensiunea ( arr ) / dimensiunea ( arr [ 0 ] ) ;
cout << „Matricea dată este \n ' ;
pentru ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Matrice sortată este \n ' ;
pentru ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
întoarcere 0 ;
}
Acest program este ca și precedentul, dar în loc să folosească două subbarray temporare L și R, folosește o singură temperatură subbary temporară. Funcția de îmbinare funcționează în același mod ca înainte, dar în loc să copieze datele în L și R, le copiază în temp. Apoi îmbină elementele matricei temp înapoi în arr care este matricea originală.
Funcția mergeSort este aceeași ca și înainte, cu excepția faptului că folosește temp în loc de L și R pentru a stoca subbarajul temporar.
În funcția principală, definim o matrice arr cu 6 elemente și apelăm funcția mergeSort pentru a o sorta. Execuția codului se încheie prin imprimarea matricei sortate pe ecran.
Concluzie
Sortare prin îmbinare este un algoritm care sortează elementele matricei și folosește tehnica divide-and-conquer și face comparații între elemente. Merge sort în C++ are o complexitate de timp de O(n log n) și este deosebit de eficient pentru sortarea matricelor mari. Deși necesită memorie suplimentară pentru a stoca subbaryurile îmbinate, stabilitatea sa îl face o alegere populară pentru sortare.