Talaan ng mga Nilalaman
- Panimula
- Ano ang Merge Sort sa C++
- Divide and Conquer Approach
- Pagsamahin ang Algorithm ng Pag-uuri
- Pagpapatupad ng Merge Sort sa C++
- Konklusyon
1. Panimula
Ang mga algorithm ng pag-uuri sa computer science ay ginagamit upang ayusin ang data sa pataas o pababang pagkakasunud-sunod. Mayroong maraming mga algorithm ng pag-uuri na may mga natatanging katangian na magagamit. Ang merge sort ay isa sa mga pamamaraan sa C++ na maaaring pag-uri-uriin ang mga arrays.
2. Ano ang Merge Sort sa C++
Gumagamit ang merge sort ng divide-and-conquer technique na maaaring ayusin ang mga elemento ng isang array. Maaari din nitong ayusin ang listahan ng mga elemento sa C++. Hinahati nito ang input sa dalawang halves, iisa-isa ang pag-uuri sa bawat kalahati, at pagkatapos ay pinagsasama ang mga ito sa tamang pagkakasunud-sunod.
3. Divide and Conquer Approach
Ang algorithm ng pag-uuri ay naglalapat ng isang divide-and-conquer na diskarte, na nangangailangan ng paghati sa input array sa mas maliliit na subbarray, paglutas ng mga ito nang hiwalay, at pagkatapos ay pagsasama-samahin ang mga resulta upang makabuo ng isang pinagsunod-sunod na output. Sa kaso ng merge sort, ang array ay recursively nahahati sa dalawang halves hanggang sa isang elemento na lang ang natitira sa bawat kalahati.
4. Pagsamahin ang Sort Algorithm
Ang merge sort algorithm ay binubuo ng dalawang pangunahing hakbang: hatiin at pagsamahin. Ang mga hakbang ay ang mga sumusunod:
4.1 Hatiin
Ang merge sort algorithm ay sumusunod sa isang divide-and-conquer na diskarte para sa pag-uuri ng mga elemento sa isang array.
- Ang unang hakbang sa algorithm ay susuriin ang mga elemento ng array. Kung naglalaman ito ng isang elemento, kung gayon ito ay itinuturing na pinagsunod-sunod, at ibabalik ng algorithm ang parehong array nang walang anumang pagbabago.
- Kung ang array ay naglalaman ng higit sa isang elemento, ang algorithm ay magpapatuloy upang hatiin ito sa dalawang halves: ang kaliwang kalahati at ang kanang kalahati.
- Ang merge sort algorithm ay muling inilalapat sa kaliwa at kanang bahagi ng array, na epektibong hinahati ang mga ito sa mas maliliit na subarray at isa-isang pinagbubukod-bukod ang mga ito.
- Ang recursive na prosesong ito ay nagpapatuloy hanggang sa ang mga subarray ay naglalaman lamang ng isang elemento bawat isa (ayon sa bawat hakbang 1), kung saan maaari silang pagsamahin upang makabuo ng isang pangwakas, pinagsunod-sunod na array ng output.
4.2 Pagsamahin
Ngayon ay makikita natin ang mga hakbang upang pagsamahin ang mga arrays:
- Ang unang hakbang para sa merge sort algorithm ay nagsasangkot ng paglikha ng isang walang laman na array.
- Ang algorithm pagkatapos ay nagpapatuloy upang ihambing ang mga unang elemento ng kaliwa at kanang halves ng input array.
- Ang mas maliit sa dalawang elemento ay idinaragdag sa bagong array at pagkatapos ay aalisin sa kani-kanilang kalahati ng input array.
- Ang mga hakbang 2-3 ay paulit-ulit hanggang sa maubos ang isa sa mga kalahati.
- Anumang natitirang elemento sa hindi-bakanteng kalahati ay idaragdag sa bagong array.
- Ang resultang array ay ganap na ngayong pinagsunod-sunod at kumakatawan sa panghuling output ng merge sort algorithm.
5. Pagpapatupad ng Merge Sort sa C++
Upang ipatupad ang merge sort sa C++ dalawang magkaibang pamamaraan ang sinusunod. Ang pagiging kumplikado ng oras ng parehong mga pamamaraan ay katumbas, ngunit ang kanilang paggamit ng mga pansamantalang subarray ay naiiba.
Ang unang paraan para sa merge sort sa C++ ay gumagamit ng dalawang pansamantalang subarray, habang ang pangalawa ay gumagamit lamang ng isa. Kapansin-pansin na ang kabuuang sukat ng dalawang pansamantalang subarray sa unang pamamaraan ay katumbas ng laki ng orihinal na hanay sa pangalawang pamamaraan, kaya nananatiling pare-pareho ang pagiging kumplikado ng espasyo.
Paraan 1 – Paggamit ng Dalawang Temp Subarray
Narito ang isang halimbawang programa para sa pagsasanib ng pag-uuri sa C++ gamit ang Paraan 1, na gumagamit ng dalawang pansamantalang subarray:
#includegamit ang namespace std ;
walang bisa pagsamahin ( int arr [ ] , int l , int m , int r )
{
int n1 = m - l + 1 ;
int n2 = r - m ;
int L [ n1 ] , R [ n2 ] ;
para sa ( int i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
para sa ( int j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
int i = 0 , j = 0 , k = l ;
habang ( i < n1 && j < n2 ) {
kung ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
iba pa {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
habang ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
habang ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
walang bisa sumanib-uuri ( int arr [ ] , int l , int r )
{
kung ( l < r ) {
int m = l + ( r - l ) / 2 ;
sumanib-uuri ( arr , l , m ) ;
sumanib-uuri ( arr , m + 1 , r ) ;
pagsamahin ( arr , l , m , r ) ;
}
}
int pangunahing ( )
{
int arr [ ] = { 12 , labing-isa , 13 , 5 , 6 , 7 } ;
int arr_size = sukat ng ( arr ) / sukat ng ( arr [ 0 ] ) ;
cout << 'Ang ibinigay na array ay \n ' ;
para sa ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
sumanib-uuri ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Ang pinagsunod-sunod na array ay \n ' ;
para sa ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << '' ;
bumalik 0 ;
}
Sa program na ito, ang merge function ay tumatagal ng tatlong argumento na arr, l, at r, na kumakatawan sa array na pag-uuri-uriin at nagpapakita ng mga indeks ng subarray na kailangang i-merge. Hinahanap muna ng function ang mga laki ng dalawang subarray na isasama, pagkatapos ay gagawa ng dalawang pansamantalang subarray na L at R upang iimbak ang mga elemento ng mga subarray na ito. Pagkatapos ay inihambing nito ang mga elemento sa L at R at pinagsasama ang mga ito sa orihinal na array na pinangalanan arr sa pataas na ayos.
Ang divide-and-conquer technique ay ginagamit ng mergeSort function para hatiin ang array sa dalawang halves nang recursively hanggang sa may isang elemento na lang na naiwan sa subarray. Pagkatapos ay pinagsasama nito ang dalawang subarray sa isang pinagsunod-sunod na subarray. Patuloy na pinagsasama-sama ng function ang mga subarray maliban kung pinag-uuri nito ang kumpletong array.
Sa pangunahing pag-andar, tinutukoy namin ang isang array arr na may 6 na elemento at tinatawag ang mergeSort function upang pag-uri-uriin ito. Sa dulo ng code, naka-print ang pinagsunod-sunod na array.
Paraan 2 – Paggamit ng One Temp Subarray
Narito ang isang halimbawang programa para sa merge sort sa C++ gamit ang Paraan 2, na gumagamit ng isang pansamantalang subarray:
#includegamit ang namespace std ;
walang bisa pagsamahin ( int arr [ ] , int l , int m , int r )
{
int i , j , k ;
int n1 = m - l + 1 ;
int n2 = r - m ;
// Lumikha ng mga pansamantalang subarray
int L [ n1 ] , R [ n2 ] ;
// Kopyahin ang data sa mga subarray
para sa ( i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
para sa ( j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
// Pagsamahin ang mga pansamantalang subarray pabalik sa orihinal na hanay
i = 0 ;
j = 0 ;
k = l ;
habang ( i < n1 && j < n2 ) {
kung ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
iba pa {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
// Kopyahin ang natitirang mga elemento ng L[]
habang ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
// Kopyahin ang natitirang mga elemento ng R[]
habang ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
walang bisa sumanib-uuri ( int arr [ ] , int l , int r )
{
kung ( l < r ) {
int m = l + ( r - l ) / 2 ;
// Pagbukud-bukurin ang kaliwa at kanang bahagi nang paulit-ulit
sumanib-uuri ( arr , l , m ) ;
sumanib-uuri ( arr , m + 1 , r ) ;
// Pagsamahin ang dalawang pinagsunod-sunod na kalahati
pagsamahin ( arr , l , m , r ) ;
}
}
int pangunahing ( )
{
int arr [ ] = { 12 , labing-isa , 13 , 5 , 6 , 7 } ;
int arr_size = sukat ng ( arr ) / sukat ng ( arr [ 0 ] ) ;
cout << 'Ang ibinigay na array ay \n ' ;
para sa ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << '' ;
sumanib-uuri ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Ang pinagsunod-sunod na array ay \n ' ;
para sa ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << '' ;
bumalik 0 ;
}
Ang program na ito ay katulad ng nauna, ngunit sa halip na gumamit ng dalawang pansamantalang subarray na L at R, gumagamit ito ng iisang pansamantalang subarray na temp. Gumagana ang merge function sa parehong paraan tulad ng dati, ngunit sa halip na kopyahin ang data sa L at R, kinokopya ito sa temp. Pagkatapos ay pinagsasama nito ang mga elemento ng temp array pabalik sa arr na ang orihinal na hanay.
Ang mergeSort function ay kapareho ng dati, maliban na ito ay gumagamit ng temp sa halip na L at R upang iimbak ang pansamantalang subarray.
Sa pangunahing pag-andar, tinutukoy namin ang isang array arr na may 6 na elemento at tinatawag ang mergeSort function upang pag-uri-uriin ito. Ang code execution ay nagtatapos sa pamamagitan ng pag-print ng pinagsunod-sunod na array sa screen.
Konklusyon
Ang merge sort ay isang algorithm na nag-uuri ng mga elemento ng array, at ginagamit nito ang divide-and-conquer technique at gumagawa ng mga paghahambing sa pagitan ng mga elemento. Ang merge sort sa C++ ay may time complexity ng O(n log n) at partikular na epektibo para sa pag-uuri ng malalaking array. Bagama't nangangailangan ito ng karagdagang memorya upang maiimbak ang mga pinagsanib na subarray, ang katatagan nito ay ginagawa itong isang popular na pagpipilian para sa pag-uuri.