Isi kandungan
- pengenalan
- Apa itu Merge Sort dalam C++
- Pendekatan Bahagi dan Takluk
- Algoritma Isih Gabung
- Pelaksanaan Merge Sort dalam C++
- Kesimpulan
1. Pengenalan
Algoritma pengisihan dalam sains komputer digunakan untuk menyusun data dalam tertib menaik atau menurun. Terdapat berbilang algoritma pengisihan dengan sifat yang berbeza tersedia. Merge sort ialah salah satu kaedah dalam C++ yang boleh mengisih tatasusunan.
2. Apakah itu Merge Sort dalam C++
Isih Gabung menggunakan teknik bahagi dan takluk yang boleh menyusun elemen tatasusunan. Ia juga boleh mengisih senarai elemen dalam C++. Ia membahagikan input kepada dua bahagian, mengisih setiap separuh secara berasingan, dan kemudian menggabungkannya dalam susunan yang betul.
3. Pendekatan Bahagi dan Takluk
Algoritma pengisihan menggunakan strategi bahagi-dan-takluk, yang memerlukan pembahagian tatasusunan input kepada subarray yang lebih kecil, menyelesaikannya secara berasingan, dan kemudian menggabungkan hasil untuk menghasilkan output yang diisih. Dalam kes isihan gabungan, tatasusunan dibahagikan secara rekursif kepada dua bahagian sehingga hanya satu elemen yang tinggal dalam setiap separuh.
4. Algoritma Isih Gabung
Algoritma isihan gabungan terdiri daripada dua langkah utama: bahagi dan cantum. Langkah-langkahnya adalah seperti berikut:
4.1 Bahagi
Algoritma isihan gabungan mengikut strategi bahagi-dan-takluk untuk mengisih elemen dalam tatasusunan.
- Langkah pertama dalam algoritma akan menyemak elemen tatasusunan. Jika ia mengandungi satu elemen, maka ia sudah dianggap diisih, dan algoritma akan mengembalikan tatasusunan yang sama tanpa sebarang perubahan.
- Jika tatasusunan mengandungi lebih daripada satu elemen, algoritma akan terus membahagikannya kepada dua bahagian: separuh kiri dan separuh kanan.
- Algoritma isihan cantuman kemudiannya digunakan secara rekursif pada bahagian kiri dan kanan tatasusunan, dengan berkesan membahagikannya kepada subarray yang lebih kecil dan mengisihnya secara individu.
- Proses rekursif ini berterusan sehingga subarray mengandungi hanya satu elemen setiap satu (seperti pada langkah 1), di mana ia boleh digabungkan untuk menghasilkan tatasusunan keluaran terakhir yang diisih.
4.2 Bercantum
Sekarang kita akan melihat langkah-langkah untuk menggabungkan tatasusunan:
- Langkah pertama untuk algoritma isihan gabungan melibatkan mencipta tatasusunan kosong.
- Algoritma kemudiannya meneruskan untuk membandingkan elemen pertama bahagian kiri dan kanan tatasusunan input.
- Yang lebih kecil daripada dua elemen ditambah pada tatasusunan baharu dan kemudian dialih keluar daripada separuh tatasusunan input masing-masing.
- Langkah 2-3 kemudian diulang sehingga salah satu bahagian dikosongkan.
- Sebarang elemen yang tinggal dalam separuh yang tidak kosong kemudiannya ditambahkan pada tatasusunan baharu.
- Tatasusunan yang terhasil kini diisih sepenuhnya dan mewakili output akhir algoritma isihan gabungan.
5. Pelaksanaan Merge Sort dalam C++
Untuk melaksanakan pengisihan gabungan dalam C++ dua kaedah berbeza diikuti. Kerumitan masa kedua-dua kaedah adalah setara, tetapi penggunaan subarray sementara mereka berbeza.
Kaedah pertama untuk isihan gabungan dalam C++ menggunakan dua subarray sementara, manakala yang kedua hanya menggunakan satu. Perlu diingat bahawa jumlah saiz dua subarray sementara dalam kaedah pertama adalah sama dengan saiz tatasusunan asal dalam kaedah kedua, jadi kerumitan ruang kekal malar.
Kaedah 1 – Menggunakan Dua Subarray Suhu
Berikut ialah program contoh untuk pengisihan gabungan dalam C++ menggunakan Kaedah 1, yang menggunakan dua subarray sementara:
#includemenggunakan ruang nama std ;
batal bercantum ( int arr [ ] , int l , int m , int r )
{
int n1 = m - l + 1 ;
int n2 = r - m ;
int L [ n1 ] , R [ n2 ] ;
untuk ( int i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
untuk ( int j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
int i = 0 , j = 0 , k = l ;
sementara ( i < n1 && j < n2 ) {
jika ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
lain {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
sementara ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
sementara ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
batal mergeSort ( int arr [ ] , int l , int r )
{
jika ( l < r ) {
int m = l + ( r - l ) / 2 ;
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
bercantum ( arr , l , m , r ) ;
}
}
int utama ( )
{
int arr [ ] = { 12 , sebelas , 13 , 5 , 6 , 7 } ;
int arr_size = saiz ( arr ) / saiz ( arr [ 0 ] ) ;
cout << 'Susun atur yang diberikan ialah \n ' ;
untuk ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Tatasusunan disusun ialah \n ' ;
untuk ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
kembali 0 ;
}
Dalam atur cara ini, fungsi gabungan mengambil tiga argumen arr, l dan r, yang mewakili tatasusunan untuk diisih dan menunjukkan indeks subarray yang perlu digabungkan. Fungsi pertama mencari saiz dua subarray untuk digabungkan, kemudian mencipta dua subarray sementara L dan R untuk menyimpan unsur subarray ini. Ia kemudian membandingkan unsur-unsur dalam L dan R dan menggabungkannya ke dalam tatasusunan asal yang dinamakan arr dalam susunan menaik.
Teknik divide-and-conquer digunakan oleh fungsi mergeSort untuk membahagi tatasusunan kepada dua bahagian secara rekursif sehingga hanya ada satu elemen yang tertinggal dalam subarray. Ia kemudian menggabungkan dua subarray menjadi subarray yang disusun. Fungsi ini terus menggabungkan subarrays melainkan ia mengisih tatasusunan lengkap.
Dalam fungsi utama, kami mentakrifkan arr tatasusunan dengan 6 elemen dan memanggil fungsi mergeSort untuk mengisihnya. Pada penghujung kod, tatasusunan yang diisih dicetak.
Kaedah 2 – Menggunakan One Temp Subarray
Berikut ialah program contoh untuk pengisihan gabungan dalam C++ menggunakan Kaedah 2, yang menggunakan subarray sementara tunggal:
#includemenggunakan ruang nama std ;
batal bercantum ( int arr [ ] , int l , int m , int r )
{
int i , j , k ;
int n1 = m - l + 1 ;
int n2 = r - m ;
// Cipta subarray sementara
int L [ n1 ] , R [ n2 ] ;
// Salin data ke subarrays
untuk ( i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
untuk ( j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
// Gabungkan subarray sementara kembali ke dalam tatasusunan asal
i = 0 ;
j = 0 ;
k = l ;
sementara ( i < n1 && j < n2 ) {
jika ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
lain {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
// Salin baki elemen L[]
sementara ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
// Salin baki elemen R[]
sementara ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
batal mergeSort ( int arr [ ] , int l , int r )
{
jika ( l < r ) {
int m = l + ( r - l ) / 2 ;
// Isih bahagian kiri dan kanan secara rekursif
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
// Cantumkan dua bahagian yang disusun
bercantum ( arr , l , m , r ) ;
}
}
int utama ( )
{
int arr [ ] = { 12 , sebelas , 13 , 5 , 6 , 7 } ;
int arr_size = saiz ( arr ) / saiz ( arr [ 0 ] ) ;
cout << 'Susun atur yang diberikan ialah \n ' ;
untuk ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Tatasusunan disusun ialah \n ' ;
untuk ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
kembali 0 ;
}
Program ini seperti yang sebelumnya, tetapi bukannya menggunakan dua subarray sementara L dan R, ia menggunakan satu temp subarray sementara. Fungsi gabungan berfungsi dengan cara yang sama seperti sebelumnya, tetapi bukannya menyalin data ke L dan R, ia menyalinnya ke temp. Ia kemudian menggabungkan elemen temp array kembali ke dalam arr yang merupakan tatasusunan asal.
Fungsi mergeSort adalah sama seperti sebelumnya, kecuali ia menggunakan temp dan bukannya L dan R untuk menyimpan subarray sementara.
Dalam fungsi utama, kami mentakrifkan arr tatasusunan dengan 6 elemen dan memanggil fungsi mergeSort untuk mengisihnya. Pelaksanaan kod berakhir dengan mencetak tatasusunan yang diisih pada skrin.
Kesimpulan
Isih Gabung ialah algoritma yang menyusun elemen tatasusunan, dan ia menggunakan teknik bahagi-dan-takluk serta membuat perbandingan antara elemen. Isih gabungan dalam C++ mempunyai kerumitan masa O(n log n) dan amat berkesan untuk menyusun tatasusunan yang besar. Walaupun ia memerlukan memori tambahan untuk menyimpan subarray yang digabungkan, kestabilannya menjadikannya pilihan popular untuk mengisih.