Penjelasan lengkap merge sort C++
Algoritma ini membagi bilangan atau array sampai tidak dapat dibagi kembali dan mengurutkannya setiap bagian. Dengan cara ini kita dapat memperoleh jumlah perbandingan yang lebih sedikit daripada sorting menggunakan selection sort, bubble sort dan insertion sort.
Bagaimana merge sort bekerja
Algoritma merge sort bekerja seperti deskripsi dibawah ini:
- Bagi array bilangan sampai tidak dapat dibagi kembali,
- Urutkan bilangan yang telah dibagi,
- Gabungkan kembali bilangan yang telah dibagi,
- Array bilangan akan terurut.
Deskripsi diatas agak sulit untuk dibayangkan bagaimana komputer melakukannya untuk itu lihatlah contoh dari sorting dibawah ini dengan algoritma merge sort.
Kita memiliki array bilangan 38, 27, 43, 3, 9, 82, 10. Bilangan tersebut dibagi menjadi dua sehingga array yang terbentuk menjadi 38, 27, 43, 3 dan 9, 82, 10. Array bilangan tersebut masih dapat dibagi kembali, jadi kita harus membagi array tersebut sampai tidak dapat dibagi kembali. Pada bagian ini kita melakuakan pembagian (divide).
Setelah menjadi array yang tidak dapat dibagi, kita gabungkan dengan mengurutkannya. Mekanisme pengurutan sama dengan cara menggabungkan dua array yang telah terurut. Misalnya bagian pertama bandingkan 38 dan 27, maka gabungan array dua bilangan tersebut adalah 27, dan 38. Kemudian pada tingkat selanjutnya (baris ke 5 dan 6), kita memiliki 27, 38 dan 3, dan 43. Bandingkan array bilangan 27 dan 3, karena 3 lebih kecil kita masukkan array baru yakni gabungan dari array sebelumnya. Kemudian bandingkan kembali 27 dengan 43, karenaa 27 lebih kecil kita taruh di sebelah kanan 3. Kemudian kita bandingkan kembali 38 dan 43, karena 38 lebih kecil dari 43, maka kita taruh angka 38 di samping kanan angka 27. Karena salah satu array telah habis kita hanya perlu memasukkannya. Bagian ini biasa disebut dengan penggabungan (conquer).
Dengan cara diatas kita tidak perlu membandingkan setiap angka untuk memperoleh hasil yang terurut. Pada array 2 yang dibandingkan dengan array 2 maksimal kita hanya melakukan perbandingan 3 kali. Dengan cara ini kita akan memperoleh jumlah perbandingan yang lebih sedikit.
Bagaimana membagi array
Untuk membagi array menjadi dua bagian kita menggunakan rekursif. Apa itu fungsi rekursif ? Fungsi rekursif adalah fungsi yang mengacu pada dirinya sendiri. Singkatnya kita melakukan pemanggilan fungsi pada fungsi tersebut. Untuk memahami algoritma merge sort, cobalah untuk memahami bagaimana rekursif bekerja.
Untuk membagi array menjadi dua bagian lihatlah potongan program dibawah ini:
void mergeSort(int arr[], int a, int z)
{if (a < z){int m = a+(z-l)/2;mergeSort(arr, a, m);mergeSort(arr, m+1, z);merge(arr, a, m, z);}}
Fungsi diatas digunakan untuk membagi array menjadi dua bagian. arr[] merupakan bilangan yang akan kita urutkan. Variabel a adalah index paling kiri dari arr[] dan variabel z adalah index paling kanan dalam arr[].
Cara kerja fungsi tersebut adalah jika index kiri lebih kecil dari index kanan, kita membagi menjadi 2 dengan cara m = a +(z-1)/2. Setelah itu kita gunakan rekursif untuk membagi kembali dengan memanggil fungsi dirinya sendiri. Hal ini akan terus dilakukan sampai index kiri (variabel a) lebih besar atau sama dengan index kanan (variabel z). Tapi perlu diingat komputer akan menyelesaikan perintah yang berada pada fungsi paling kecil (fungsi yang memanggil fungsi terlebih dahulu). Untuk lebih jelasnya cobalah untuk melakukan debug pada proses algoritma diatas.
Cara kerja fungsi tersebut adalah jika index kiri lebih kecil dari index kanan, kita membagi menjadi 2 dengan cara m = a +(z-1)/2. Setelah itu kita gunakan rekursif untuk membagi kembali dengan memanggil fungsi dirinya sendiri. Hal ini akan terus dilakukan sampai index kiri (variabel a) lebih besar atau sama dengan index kanan (variabel z). Tapi perlu diingat komputer akan menyelesaikan perintah yang berada pada fungsi paling kecil (fungsi yang memanggil fungsi terlebih dahulu). Untuk lebih jelasnya cobalah untuk melakukan debug pada proses algoritma diatas.
Bagaimana menggabung dua array terurut
Untuk menggabung dua array yang sudah terurut kita hanya perlu membandingkan kedua array, kemudian memasukkannya dalam array baru sampai salah satu array habis. Sisanya dapat dimasukkan tanpa melakukan perbandingan kembali. Lihatlah potongan program dibawah ini:
void merge(int arr[], int a, int m, int z)
{int q, w, e;int n1 = m - a + 1;int n2 = z - 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];q = 0;w = 0;e = a;while (q < n1 && w < n2){if (L[q] <= R[w]){arr[e] = L[q];q++;}else{arr[e] = R[w];w++;}e++;}while (q < n1){arr[e] = L[q];q++;e++;}while (w < n2){arr[e] = R[w];w++;e++;}}
Parameter arr[] adalah array yang akan dibandingkan, parameter a adalah index kiri dari sub array sebelumnya dan paramater m adalah index kanan dari sub array dengan m+1 adalah index kiri dari sub array lainnya, dan parameter z adalah index kanan sub array.
Singkatnya
arr[] adalah array yang akan di sorting
sub array pertama arr[a .. m]
sub array kedua arr[m+1 .. z]
Pada bagian pendeklarasian variabel q, w, e digunakan untuk penunjuk array dari dua array yang nanti akan dibagi. Variabel n1 adalah panjang array pertama dan variabel n2 adalah panjang array kedua. Array pada arr[] dipindahkan dengan index a sampai m, dan index m+1 sampai z. Copy arr[] ke dalam array L dan array R.
Setelah melakukan copy data kita bandingkan dengan mekanisme apabila L[0] lebih kecil dari R[0] value atau nilai L[0] kita masukkan dalam array arr[], index e dan index array L (dalam contoh diatas q) ditambahkan. Sementara itu jika value R lebih kecil dari value L value dari R kita masukkan dalam arr[], index arr[] (dalam contoh diatas e) dan index R[] (dalam contoh diatas w) ditambahkan. Proses ini akan terus berulang sampai salah satu array habis. Setelah itu kita copykan array yang belum habis ke dalam array hasil (dalam contoh arr[]).
Dengan melakukan hal diatas pada setiap bagian, kita akan memperoleh array terurut dengan melakukan sesedikit mungkin perbandingan.
Source code merge sort
#include<stdlib.h>
#include<stdio.h>#include<iostream>using namespace std;void merge(int arr[], int a, int m, int z){int q, w, e;int n1 = m - a + 1;int n2 = z - 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];q = 0;w = 0;e = a;while (q < n1 && w < n2){if (L[q] <= R[w]){arr[e] = L[q];q++;}else{arr[e] = R[w];w++;}e++;}while (q < n1){arr[e] = L[q];q++;e++;}while (w < n2){arr[e] = R[w];w++;e++;}}void mergeSort(int arr[], int a, int z){if (a < z){int m = a+(z-l)/2;mergeSort(arr, a, m);mergeSort(arr, m+1, z);merge(arr, a, m, z);}}void printArray(int A[], int size){int i;for (i=0; i < size; i++)cout << A[i] << " ";cout << endl;}int main(){int arr[] = {12, 11, 13, 5, 6, 7};int arr_size = sizeof(arr)/sizeof(arr[0]);cout << "\nSebelum sorting\n";printArray(arr, arr_size);mergeSort(arr, 0, arr_size - 1);cout << "\nSorted array is \n";printArray(arr, arr_size);return 0;}
Output dari program diatas
Sebelum sorting
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
Setelah anda mempelajari ini, diharapkan anda paham dengan cara kerja dari algoritma diatas. Karena saya percaya orang yang paham dapat membuatnya sendiri meskipun dengan cara yang sedikit berbeda tetapi memiliki hasil dan kompleksitas yang sama.
proses sortingnya pada bagian mana ya gan sebab saya ingin mengurutkan dari besar ke kecil
ReplyDelete