Anak Males – Artikel ini akan memberikan panduan untuk membuat sebuah program dengan bahasa C++ yang mengaplikasikan metode pengurutan merge sort.
Merge Sort adalah salah satu algoritma pengurutan yang bersifat divide and conquer. Algoritma ini membagi data yang akan diurutkan menjadi bagian-bagian yang lebih kecil, lalu mengurutkan masing-masing bagian tersebut dan menggabungkannya kembali menjadi satu data yang terurut.
Merge sort merupakan algoritma yang stabil dan efisien, dengan kompleksitas waktu O(n log n).
Algoritma ini juga stabil, artinya jika ada dua elemen yang memiliki nilai yang sama, posisi elemen tersebut tidak akan berubah setelah diurutkan.
Merge sort juga dapat digunakan untuk mengurutkan data yang tidak dapat diakses secara langsung, seperti data yang disimpan dalam file atau data yang sangat besar sehingga tidak dapat dimasukkan ke dalam memori komputer secara langsung.
Baca : Latihan C++ #39 : Quick Sort
Program C++ Membuat Merge Sort
Berikut adalah contoh program C++ yang menerima input dari user untuk menyortir sebuah array menggunakan algoritma Merge Sort:
#include <iostream>
using namespace std;
// Fungsi untuk menggabungkan dua bagian array
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++) {
L[i] = arr[l + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[m + 1 + j];
}
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Fungsi untuk menyortir array dengan merge sort
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// Fungsi utama
int main() {
int n;
cout << "Masukkan jumlah elemen dalam array: ";
cin >> n;
int arr[n];
cout << "Masukkan elemen dalam array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Array sebelum diurutkan: \n";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
mergeSort(arr, 0, n - 1);
cout << "\nArray setelah diurutkan: \n";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Berikut adalah penjelasan lebih detail tentang masing-masing bagian dari kode program di atas:
#include <iostream>
using namespace std;
Pertama-tama, kita meng-include library iostream yang digunakan untuk input/output stream dan mendeklarasikan using namespace std; agar kita tidak perlu mengetik std:: setiap kali menggunakan fungsi dari library tersebut.
Baca : Latihan C++ #38 : Bubble Sort
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++) {
L[i] = arr[l + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[m + 1 + j];
}
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
Kemudian, kita membuat fungsi merge() yang digunakan untuk menggabungkan dua bagian array yang sudah terurut.
Fungsi ini menerima input berupa array, indeks awal (l), indeks tengah (m), dan indeks akhir (r) dari array yang akan digabungkan.
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
Selanjutnya, kita membuat fungsi mergeSort() yang digunakan untuk menyortir array dengan algoritma merge sort.
Fungsi ini menerima input berupa array, indeks awal (l), dan indeks akhir (r) dari array yang akan disortir.
Dalam fungsi mergeSort(), array akan dibagi menjadi dua bagian secara rekursif. Setiap bagian akan disortir secara terpisah dengan menggunakan fungsi mergeSort() lagi.
Ketika sudah tidak dapat dibagi lagi, maka akan digabungkan menggunakan fungsi merge().
Baca : Latihan C++ #37 : Persegi Panjang Bintang
int main() {
int n;
cout << "Masukkan jumlah elemen dalam array: ";
cin >> n;
int arr[n];
cout << "Masukkan elemen dalam array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Array sebelum diurutkan: \n";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
mergeSort(arr, 0, n - 1);
cout << "\nArray setelah diurutkan: \n";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Kemudian kita membuat fungsi utama main() yang digunakan untuk menerima input jumlah elemen dalam array dari user, kemudian menerima input elemen dari user dan menampilkan array sebelum dan sesudah diurutkan.
Pada fungsi utama, kita menerima input jumlah elemen dalam array dari user menggunakan cin >> n;, kemudian kita membuat array dengan jumlah elemen yang sesuai dengan input user.
Kemudian kita menerima input elemen dari user dan menampilkan array sebelum diurutkan.
Setelah itu kita memanggil fungsi mergeSort(arr, 0, n - 1); yang digunakan untuk menyortir array menggunakan algoritma merge sort, dan menampilkan array setelah diurutkan.
Program akan berakhir dengan return 0;
Baca : Latihan C++ #36 : Belah Ketupat Bintang
Output Program C++ Membuat Merge Sort
Jika Anda menjalankan program yang saya berikan di atas, Anda akan melihat output seperti ini:
Masukkan jumlah elemen dalam array: 6
Masukkan elemen dalam array: 12 11 13 5 6 7
Array sebelum diurutkan:
12 11 13 5 6 7
Array setelah diurutkan:
5 6 7 11 12 13
Output tersebut menunjukkan bahwa array yang dimasukkan oleh user sebelum diurutkan (12, 11, 13, 5, 6, 7) telah diurutkan menjadi (5, 6, 7, 11, 12, 13) setelah program dijalankan.
Penutup
Sekian untuk tutorial C++ kali ini, sampai jumpa di tutorial C++ lainnya.