Daftar isi
- Perkenalan
- Apa itu Merge Sort di C++
- Pendekatan Divide and Conquer
- Menggabungkan Algoritma Sortir
- Implementasi Merge Sort di C++
- Kesimpulan
1. Perkenalan
Algoritma pengurutan dalam ilmu komputer digunakan untuk mengatur data dalam urutan naik atau turun. Ada beberapa algoritma pengurutan dengan properti berbeda yang tersedia. Merge sort adalah salah satu metode dalam C++ yang dapat mengurutkan array.
2. Apa itu Merge Sort di C++
Pengurutan gabungan menggunakan teknik bagi-dan-taklukkan yang dapat menyusun elemen-elemen array. Itu juga bisa mengurutkan daftar elemen di C++. Itu membagi input menjadi dua bagian, mengurutkan masing-masing bagian secara terpisah, dan kemudian menggabungkannya dalam urutan yang benar.
3. Pendekatan Divide and Conquer
Algoritme pengurutan menerapkan strategi bagi-dan-taklukkan, yang mengharuskan mempartisi larik masukan menjadi subarray yang lebih kecil, menyelesaikannya secara terpisah, dan kemudian menggabungkan hasilnya untuk menghasilkan keluaran yang diurutkan. Dalam kasus pengurutan gabungan, array secara rekursif dibagi menjadi dua bagian hingga hanya tersisa satu elemen di setiap setengahnya.
4. Menggabungkan Algoritma Sortir
Algoritma merge sort terdiri dari dua langkah utama: membagi dan menggabungkan. Langkah-langkahnya adalah sebagai berikut:
4.1 Bagi
Algoritme sortir gabungan mengikuti strategi bagi-dan-taklukkan untuk menyortir elemen dalam array.
- Langkah pertama dalam algoritma akan memeriksa elemen array. Jika mengandung satu elemen, maka sudah dianggap terurut, dan algoritme akan mengembalikan array yang sama tanpa perubahan apa pun.
- Jika array berisi lebih dari satu elemen, algoritme akan membaginya menjadi dua bagian: bagian kiri dan bagian kanan.
- Algoritme sortir gabungan kemudian diterapkan secara rekursif ke bagian kiri dan kanan dari array, secara efektif membaginya menjadi subarray yang lebih kecil dan mengurutkannya secara individual.
- Proses rekursif ini berlanjut hingga subarray masing-masing hanya berisi satu elemen (sesuai langkah 1), di mana subarray dapat digabungkan untuk menghasilkan array keluaran akhir yang diurutkan.
4.2 Penggabungan
Sekarang kita akan melihat langkah-langkah untuk menggabungkan array:
- Langkah pertama untuk algoritma pengurutan gabungan melibatkan pembuatan array kosong.
- Algoritme kemudian melanjutkan untuk membandingkan elemen pertama dari bagian kiri dan kanan dari larik input.
- Yang lebih kecil dari dua elemen ditambahkan ke array baru dan kemudian dihapus dari masing-masing setengah dari array input.
- Langkah 2-3 kemudian diulang sampai salah satu bagian dikosongkan.
- Setiap elemen yang tersisa di bagian yang tidak kosong kemudian ditambahkan ke array baru.
- Array yang dihasilkan sekarang sepenuhnya diurutkan dan mewakili hasil akhir dari algoritma pengurutan gabungan.
5. Implementasi Merge Sort di C++
Untuk menerapkan sortir gabungan dalam C++, dua metode berbeda diikuti. Kompleksitas waktu kedua metode ini sama, tetapi penggunaan subarray sementara berbeda.
Metode pertama untuk urutan gabungan di C++ menggunakan dua subarray sementara, sedangkan yang kedua hanya menggunakan satu. Perlu dicatat bahwa ukuran total dari dua subarray sementara pada metode pertama sama dengan ukuran array asli pada metode kedua, sehingga kompleksitas ruang tetap konstan.
Metode 1 – Menggunakan Dua Temp Subarrays
Berikut adalah contoh program untuk menggabungkan sortir di C++ menggunakan Metode 1, yang menggunakan dua subarray sementara:
#termasukmenggunakan namespace std ;
ruang kosong menggabungkan ( int arr [ ] , int l , int M , int R )
{
int n1 = M - l + 1 ;
int n2 = R - M ;
int L [ n1 ] , R [ n2 ] ;
untuk ( int Saya = 0 ; Saya < n1 ; Saya ++ )
L [ Saya ] = arr [ l + Saya ] ;
untuk ( int J = 0 ; J < n2 ; J ++ )
R [ J ] = arr [ M + 1 + J ] ;
int Saya = 0 , J = 0 , k = l ;
ketika ( Saya < n1 && J < n2 ) {
jika ( L [ Saya ] <= R [ J ] ) {
arr [ k ] = L [ Saya ] ;
Saya ++;
}
kalau tidak {
arr [ k ] = R [ J ] ;
J ++;
}
k ++;
}
ketika ( Saya < n1 ) {
arr [ k ] = L [ Saya ] ;
Saya ++;
k ++;
}
ketika ( J < n2 ) {
arr [ k ] = R [ J ] ;
J ++;
k ++;
}
}
ruang kosong menggabungkanSort ( int arr [ ] , int l , int R )
{
jika ( l < R ) {
int M = l + ( R - l ) / 2 ;
menggabungkanSort ( arr , l , M ) ;
menggabungkanSort ( arr , M + 1 , R ) ;
menggabungkan ( arr , l , M , R ) ;
}
}
int utama ( )
{
int arr [ ] = { 12 , sebelas , 13 , 5 , 6 , 7 } ;
int arr_size = ukuran dari ( arr ) / ukuran dari ( arr [ 0 ] ) ;
cout << 'Array yang diberikan adalah \N ' ;
untuk ( int Saya = 0 ; Saya < arr_size ; Saya ++ )
cout << arr [ Saya ] << ' ' ;
menggabungkanSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \N Array yang diurutkan adalah \N ' ;
untuk ( int Saya = 0 ; Saya < arr_size ; Saya ++ )
cout << arr [ Saya ] << ' ' ;
kembali 0 ;
}
Dalam program ini, fungsi penggabungan mengambil tiga argumen arr, l, dan r, yang mewakili array yang akan diurutkan dan menunjukkan indeks dari subarray yang perlu digabungkan. Fungsi pertama-tama menemukan ukuran dari dua subarray yang akan digabungkan, kemudian membuat dua subarray sementara L dan R untuk menyimpan elemen dari subarray ini. Itu kemudian membandingkan elemen-elemen dalam L dan R dan menggabungkannya ke dalam array asli bernama arr dalam urutan menaik.
Teknik devide-and-conquer digunakan oleh fungsi mergeSort untuk membagi array menjadi dua bagian secara rekursif sampai hanya ada satu elemen yang tersisa di subarray. Itu kemudian menggabungkan dua subarray menjadi subarray yang diurutkan. Fungsi terus menggabungkan subarray kecuali jika fungsi tersebut mengurutkan array lengkap.
Dalam fungsi utama, kita mendefinisikan array arr dengan 6 elemen dan memanggil fungsi mergeSort untuk mengurutkannya. Di akhir kode, array yang diurutkan dicetak.
Metode 2 – Menggunakan One Temp Subarray
Berikut adalah contoh program untuk menggabungkan sortir di C++ menggunakan Metode 2, yang menggunakan satu subarray sementara:
#termasukmenggunakan namespace std ;
ruang kosong menggabungkan ( int arr [ ] , int l , int M , int R )
{
int Saya , J , k ;
int n1 = M - l + 1 ;
int n2 = R - M ;
// Membuat subarray sementara
int L [ n1 ] , R [ n2 ] ;
// Salin data ke subarray
untuk ( Saya = 0 ; Saya < n1 ; Saya ++ )
L [ Saya ] = arr [ l + Saya ] ;
untuk ( J = 0 ; J < n2 ; J ++ )
R [ J ] = arr [ M + 1 + J ] ;
// Menggabungkan kembali subarray sementara ke dalam array asli
Saya = 0 ;
J = 0 ;
k = l ;
ketika ( Saya < n1 && J < n2 ) {
jika ( L [ Saya ] <= R [ J ] ) {
arr [ k ] = L [ Saya ] ;
Saya ++;
}
kalau tidak {
arr [ k ] = R [ J ] ;
J ++;
}
k ++;
}
// Salin sisa elemen L[]
ketika ( Saya < n1 ) {
arr [ k ] = L [ Saya ] ;
Saya ++;
k ++;
}
// Salin sisa elemen R[]
ketika ( J < n2 ) {
arr [ k ] = R [ J ] ;
J ++;
k ++;
}
}
ruang kosong menggabungkanSort ( int arr [ ] , int l , int R )
{
jika ( l < R ) {
int M = l + ( R - l ) / 2 ;
// Mengurutkan bagian kiri dan kanan secara rekursif
menggabungkanSort ( arr , l , M ) ;
menggabungkanSort ( arr , M + 1 , R ) ;
// Gabungkan dua bagian yang sudah diurutkan
menggabungkan ( arr , l , M , R ) ;
}
}
int utama ( )
{
int arr [ ] = { 12 , sebelas , 13 , 5 , 6 , 7 } ;
int arr_size = ukuran dari ( arr ) / ukuran dari ( arr [ 0 ] ) ;
cout << 'Array yang diberikan adalah \N ' ;
untuk ( int Saya = 0 ; Saya < arr_size ; Saya ++ )
cout << arr [ Saya ] << ' ' ;
menggabungkanSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \N Array yang diurutkan adalah \N ' ;
untuk ( int Saya = 0 ; Saya < arr_size ; Saya ++ )
cout << arr [ Saya ] << ' ' ;
kembali 0 ;
}
Program ini seperti yang sebelumnya, tetapi alih-alih menggunakan dua subarray sementara L dan R, program ini menggunakan satu subarray sementara temp. Fungsi penggabungan bekerja dengan cara yang sama seperti sebelumnya, tetapi alih-alih menyalin data ke L dan R, fungsi ini menyalinnya ke temp. Itu kemudian menggabungkan elemen array temp kembali ke arr yang merupakan array asli.
Fungsi mergeSort sama seperti sebelumnya, kecuali menggunakan temp alih-alih L dan R untuk menyimpan subarray sementara.
Dalam fungsi utama, kita mendefinisikan array arr dengan 6 elemen dan memanggil fungsi mergeSort untuk mengurutkannya. Eksekusi kode diakhiri dengan mencetak larik yang diurutkan di layar.
Kesimpulan
Pengurutan gabungan adalah algoritme yang mengurutkan elemen array, dan menggunakan teknik bagi-dan-taklukkan dan membuat perbandingan antar elemen. Merge sort dalam C++ memiliki kompleksitas waktu O(n log n) dan sangat efektif untuk mengurutkan array besar. Meskipun memerlukan memori tambahan untuk menyimpan subarray yang digabungkan, stabilitasnya menjadikannya pilihan populer untuk penyortiran.