KATA PENGANTAR
Bismillahirrohmanirohim
Puji syukur kami panjatkan kepada Alloh SWT, karena kuasa-Nya kami dapat menyelesaikan tepat pada waktunya.
Sholawat dan salam semoga tetap tercurah limpahkan kepada junjungan alam Nabi Muhammad SAW, kepada keluarganya, sahabatnya, tabi’in dan tabi’atnya dan semoga sampai kepada kita selaku umatnya, semoga di akhir zaman kita dapat mendapat syafaat darinya. Amin.
Dalam makalah ini kami akan mencoba menbahas tentang pengurutan, yaitu metode pengurutan MERGE SORT, serta contoh-contoh programnya.
Kami sadar dalam penyusunan makalah ini sudah pasti jauh dari kesempurnaan, maka dari itu kritik dan saran yang membangun sangat kami tunggu.
Akhir kata semoga makalah ini bisa bermanfaat bagi semua, khususnya bagi kami selaku penulis dan penyusun, dan umunnya bagi semua pembaca. Terima kasih.
Bandung, 06 Desember 2011
Penulis
DAFTAR ISI
Kata pengantar i
Daftar isi ii
BAB I. PENDAHULUAN 1
BAB II. PEMBAHASAN 2
Contoh program sederhana merge sort 4
BAB III. PENUTUP 6
Kesimpulan 6
Daftar pustaka 7
BAB I
PENDAHULUAN
Divide and Conquer (D&C) adalah algoritma pemrograman yang melakukan pemecahan masalah menjadi dua sub-masalah secara rekursif sampai setiap sub-masalah cukup sederhana untuk diselesaikan secara langsung. Tiap solusi dari masing-masing sub-masalah akan digabungkan untuk mendapatkan solusi dari masalah utama tersebut. Algoritma D&C menjadi basis dari algoritma-algoritma efisien untuk masalah-masalah seperti sorting (quick sort, merge sort) dan transformasi diskrit Fourier.
Dasar dari algoritma ini dikemukakan pertama kali oleh Anatolii Karatsuba Alexeevich pada tahun 1960 sebagai algoritma perkalian dua buah angka n-digit dengan kompleksitas algoritma O(n.2log3). Algoritma ini sekarang dikenal dengan nama Algoritma Karatsuba, membuktikan bahwa ada algoritma perkalian yang lebih cepat dari O(n2) [Kolmogorov, 1956]. Buah pikiran Kolmogorov dan penemuan Karatsuba kemudian membantu merintis penelitian performa algoritma.
Algoritma Divide and Conquer secara natural diimplementasikan secara rekursif sebagai pemanggilan prosedur dalam dirinya sendiri. Sub-masalah-sub-masalah akan dikerjakan dalam procedure-call stack. Setiap sub-masalah yang merupakan hasil pembagian dari masalah utama biasanya dibagi tanpa menimbulkan overlapping sehingga tidak ada pengerjaan redundan. Semuanya akan dimasukkan ke dalam stack dan dikerjakan mulai dari submasalah terkecil. Tetapi, selain pengimplementasian rekursif, dengan metode lain sub-masalah yang dibentuk dapat juga disimpan dalam struktur data yang dibuat sendiri seperti stack, queue, dan priority queue. Pengimplementasian non-rekursif ini menambah kebebasan dalam pemilihan sub-masalah mana yang akan dipecahkan berikutnya. Konsep ini dikembangkan dalam algoritma-algoritma seperti Breadth First Search dan optimalisasi Branch and Bound.
Terdapat dua metode sorting paling umum yang dipakai dalam implementasi algoritma Divide and Conquer, yaitu quick sort dan merge sort (di luar kedua ini masih ada metode lain seperti (insertion sort). Keduanya berfungsiuntuk mengurutkan sebuah array berisi nilai-nilai yang acak dengan cara mengurutkan sebagian dari array terlebih dahulu sebelum mengurutkan semua array secara keseluruhan.Pembahasan mendalam akan menjelaskan lebih, tetapipada saat ini yang akan dibahas adalah metode sorting merge sort.
BAB II
PEMBAHASAN
Merge sort merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945. (id.wikipedia.org)
Algoritma pengurutan data merge sort dilakukan dengan menggunakan cara divide and conquer yaitu dengan memecah kemudian menyelesaikan setiap bagian kemudian menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok.
Setelah itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh seperti awalnya. Sehingga metode merge sort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.
Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.
1. Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2. Conquer
Conquer setiap bagian dengan memanggil prosedur merge sort secararekursif
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkanrangkaian data berurutan
Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.
Contoh penerapan atas sebuah larik/array sebagai data sumber yang akan diurutkan {3, 9, 4, 1, 5, 2} adalah sebagai berikut:
pertama kali larik tersebut dibagi menjadi dua bagian, {3, 9, 4} dan {1, 5, 2}
Kedua larik kemudian diurutkan secara terpisah sehingga menjadi {3, 4, 9} dan {1, 2, 5}
Sebuah larik baru dibentuk yang sebagai penggabungan dari kedua larik tersebut {1}, sementara nilai-nilai dalam masing larik {3, 4, 9} dan {2, 5} (nilai 1 dalam elemen larik ke dua telah dipindahkan ke larik baru)
langkah berikutnya adalah penggabungan dari masing-masing larik ke dalam larik baru yang dibuat sebelumnya.
{1, 2} <-> {3, 4, 9} dan {5}
{1, 2, 3} <-> {4, 9} dan {5}
{1, 2, 3, 4} <-> {9} dan {5}
{1, 2, 3, 4, 5} <-> {9} dan {null}
{1, 2, 3, 4, 5, 9} <-> {null} dan {null}
Contoh program sedehana merge sort
public class mergeSort{
public static void main(String a[]){
int i;
int array[] = {7,5,1,3,6,4,9,8};
System.out.println("\n\n Kelompok 3\n\n");
System.out.println(" Pengurutan dengan Merge Sort\n\n");
System.out.println("Data Sebelum Diurutkan:\n");
for(i = 0; i < array.length; i++)
System.out.print( array[i]+" ");
System.out.println();
mergeSort_srt(array,0, array.length-1);
System.out.print("Data Setelah Diurutkan:\n");
for(i = 0; i <array.length; i++)
System.out.print(array[i]+" ");
System.out.println();
}
public static void mergeSort_srt(int array[],int lo, int n){
int low = lo;
int high = n;
if (low >= high)
{return; }
int middle = (low + high) / 2;
mergeSort_srt(array, low, middle);
mergeSort_srt(array, middle + 1, high);
int end_low = middle;
int start_high = middle + 1;
while ((lo <= end_low) && (start_high <= high))
{
if (array[low] < array[start_high]) {
low++; }
else {
int Temp = array[start_high];
for (int k = start_high- 1; k >= low; k--)
{array[k+1] = array[k]; }
array[low] = Temp;
low++;
end_low++;
start_high++; }
}
}
BAB III
PENUTUP
Kesimpulan
Merge Sort adalah metode pengurutan data dengan cara data dibagi menjadi subkumpulan - subkumpulan yang kemudian subkumpulan tersebut diurutkan secara terpisah, dan kemudian digabungkan kembali dengan metode merging.
DAFTAR PUSTAKA
http://problemkomputer.wordpress.com/tag/rekursif/. Di akses pada : selasa 6 desember 2011 10.13. WIB.
http://www.youtube.com/watch?v=IR7DFDej6l4&feature=related. Di akses pada : selasa 6 desember 2011 04.45. WIB.
http://www.google.co.id/url?sa=t&rct=j&q=makalah+merge+sort.doc&source=web&cd=1&ved=0CBkQFjAA&url=http%3A%2F%2Fwww.informatika.org%2F~rinaldi%2FStmik%2F2007-2008%2FMakalah2008%2FMakalahIF2251-2008-061.pdf&ei=NX3dToXVMsatrAeG6byyBA&usg=AFQjCNHnEOcCjItPK51CBGHGw-L374KhnA&cad=rja. Di akses pada : minggu 4 desember 2011 16.13. WIB.
http://id.wikipedia.org/wiki/Algoritma_merge. Di akses pada : minggu 4 desember 2011 16.30. WIB.
http://www.youtube.com/results?search_query=merge+sort&oq=merge+sort&aq=f&aqi=&aql=&gs_sm=e&gs_upl=42215l46030l0l46265l10l9l0l0l0l0l0l0ll0l0. Di akses pada : selasa 6 desember 2011 05.10. WIB
Bismillahirrohmanirohim
Puji syukur kami panjatkan kepada Alloh SWT, karena kuasa-Nya kami dapat menyelesaikan tepat pada waktunya.
Sholawat dan salam semoga tetap tercurah limpahkan kepada junjungan alam Nabi Muhammad SAW, kepada keluarganya, sahabatnya, tabi’in dan tabi’atnya dan semoga sampai kepada kita selaku umatnya, semoga di akhir zaman kita dapat mendapat syafaat darinya. Amin.
Dalam makalah ini kami akan mencoba menbahas tentang pengurutan, yaitu metode pengurutan MERGE SORT, serta contoh-contoh programnya.
Kami sadar dalam penyusunan makalah ini sudah pasti jauh dari kesempurnaan, maka dari itu kritik dan saran yang membangun sangat kami tunggu.
Akhir kata semoga makalah ini bisa bermanfaat bagi semua, khususnya bagi kami selaku penulis dan penyusun, dan umunnya bagi semua pembaca. Terima kasih.
Bandung, 06 Desember 2011
Penulis
DAFTAR ISI
Kata pengantar i
Daftar isi ii
BAB I. PENDAHULUAN 1
BAB II. PEMBAHASAN 2
Contoh program sederhana merge sort 4
BAB III. PENUTUP 6
Kesimpulan 6
Daftar pustaka 7
BAB I
PENDAHULUAN
Divide and Conquer (D&C) adalah algoritma pemrograman yang melakukan pemecahan masalah menjadi dua sub-masalah secara rekursif sampai setiap sub-masalah cukup sederhana untuk diselesaikan secara langsung. Tiap solusi dari masing-masing sub-masalah akan digabungkan untuk mendapatkan solusi dari masalah utama tersebut. Algoritma D&C menjadi basis dari algoritma-algoritma efisien untuk masalah-masalah seperti sorting (quick sort, merge sort) dan transformasi diskrit Fourier.
Dasar dari algoritma ini dikemukakan pertama kali oleh Anatolii Karatsuba Alexeevich pada tahun 1960 sebagai algoritma perkalian dua buah angka n-digit dengan kompleksitas algoritma O(n.2log3). Algoritma ini sekarang dikenal dengan nama Algoritma Karatsuba, membuktikan bahwa ada algoritma perkalian yang lebih cepat dari O(n2) [Kolmogorov, 1956]. Buah pikiran Kolmogorov dan penemuan Karatsuba kemudian membantu merintis penelitian performa algoritma.
Algoritma Divide and Conquer secara natural diimplementasikan secara rekursif sebagai pemanggilan prosedur dalam dirinya sendiri. Sub-masalah-sub-masalah akan dikerjakan dalam procedure-call stack. Setiap sub-masalah yang merupakan hasil pembagian dari masalah utama biasanya dibagi tanpa menimbulkan overlapping sehingga tidak ada pengerjaan redundan. Semuanya akan dimasukkan ke dalam stack dan dikerjakan mulai dari submasalah terkecil. Tetapi, selain pengimplementasian rekursif, dengan metode lain sub-masalah yang dibentuk dapat juga disimpan dalam struktur data yang dibuat sendiri seperti stack, queue, dan priority queue. Pengimplementasian non-rekursif ini menambah kebebasan dalam pemilihan sub-masalah mana yang akan dipecahkan berikutnya. Konsep ini dikembangkan dalam algoritma-algoritma seperti Breadth First Search dan optimalisasi Branch and Bound.
Terdapat dua metode sorting paling umum yang dipakai dalam implementasi algoritma Divide and Conquer, yaitu quick sort dan merge sort (di luar kedua ini masih ada metode lain seperti (insertion sort). Keduanya berfungsiuntuk mengurutkan sebuah array berisi nilai-nilai yang acak dengan cara mengurutkan sebagian dari array terlebih dahulu sebelum mengurutkan semua array secara keseluruhan.Pembahasan mendalam akan menjelaskan lebih, tetapipada saat ini yang akan dibahas adalah metode sorting merge sort.
BAB II
PEMBAHASAN
Merge sort merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945. (id.wikipedia.org)
Algoritma pengurutan data merge sort dilakukan dengan menggunakan cara divide and conquer yaitu dengan memecah kemudian menyelesaikan setiap bagian kemudian menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok.
Setelah itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh seperti awalnya. Sehingga metode merge sort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.
Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.
1. Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2. Conquer
Conquer setiap bagian dengan memanggil prosedur merge sort secararekursif
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkanrangkaian data berurutan
Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.
Contoh penerapan atas sebuah larik/array sebagai data sumber yang akan diurutkan {3, 9, 4, 1, 5, 2} adalah sebagai berikut:
pertama kali larik tersebut dibagi menjadi dua bagian, {3, 9, 4} dan {1, 5, 2}
Kedua larik kemudian diurutkan secara terpisah sehingga menjadi {3, 4, 9} dan {1, 2, 5}
Sebuah larik baru dibentuk yang sebagai penggabungan dari kedua larik tersebut {1}, sementara nilai-nilai dalam masing larik {3, 4, 9} dan {2, 5} (nilai 1 dalam elemen larik ke dua telah dipindahkan ke larik baru)
langkah berikutnya adalah penggabungan dari masing-masing larik ke dalam larik baru yang dibuat sebelumnya.
{1, 2} <-> {3, 4, 9} dan {5}
{1, 2, 3} <-> {4, 9} dan {5}
{1, 2, 3, 4} <-> {9} dan {5}
{1, 2, 3, 4, 5} <-> {9} dan {null}
{1, 2, 3, 4, 5, 9} <-> {null} dan {null}
Contoh program sedehana merge sort
public class mergeSort{
public static void main(String a[]){
int i;
int array[] = {7,5,1,3,6,4,9,8};
System.out.println("\n\n Kelompok 3\n\n");
System.out.println(" Pengurutan dengan Merge Sort\n\n");
System.out.println("Data Sebelum Diurutkan:\n");
for(i = 0; i < array.length; i++)
System.out.print( array[i]+" ");
System.out.println();
mergeSort_srt(array,0, array.length-1);
System.out.print("Data Setelah Diurutkan:\n");
for(i = 0; i <array.length; i++)
System.out.print(array[i]+" ");
System.out.println();
}
public static void mergeSort_srt(int array[],int lo, int n){
int low = lo;
int high = n;
if (low >= high)
{return; }
int middle = (low + high) / 2;
mergeSort_srt(array, low, middle);
mergeSort_srt(array, middle + 1, high);
int end_low = middle;
int start_high = middle + 1;
while ((lo <= end_low) && (start_high <= high))
{
if (array[low] < array[start_high]) {
low++; }
else {
int Temp = array[start_high];
for (int k = start_high- 1; k >= low; k--)
{array[k+1] = array[k]; }
array[low] = Temp;
low++;
end_low++;
start_high++; }
}
}
BAB III
PENUTUP
Kesimpulan
Merge Sort adalah metode pengurutan data dengan cara data dibagi menjadi subkumpulan - subkumpulan yang kemudian subkumpulan tersebut diurutkan secara terpisah, dan kemudian digabungkan kembali dengan metode merging.
DAFTAR PUSTAKA
http://problemkomputer.wordpress.com/tag/rekursif/. Di akses pada : selasa 6 desember 2011 10.13. WIB.
http://www.youtube.com/watch?v=IR7DFDej6l4&feature=related. Di akses pada : selasa 6 desember 2011 04.45. WIB.
http://www.google.co.id/url?sa=t&rct=j&q=makalah+merge+sort.doc&source=web&cd=1&ved=0CBkQFjAA&url=http%3A%2F%2Fwww.informatika.org%2F~rinaldi%2FStmik%2F2007-2008%2FMakalah2008%2FMakalahIF2251-2008-061.pdf&ei=NX3dToXVMsatrAeG6byyBA&usg=AFQjCNHnEOcCjItPK51CBGHGw-L374KhnA&cad=rja. Di akses pada : minggu 4 desember 2011 16.13. WIB.
http://id.wikipedia.org/wiki/Algoritma_merge. Di akses pada : minggu 4 desember 2011 16.30. WIB.
http://www.youtube.com/results?search_query=merge+sort&oq=merge+sort&aq=f&aqi=&aql=&gs_sm=e&gs_upl=42215l46030l0l46265l10l9l0l0l0l0l0l0ll0l0. Di akses pada : selasa 6 desember 2011 05.10. WIB
makasih infonya gan...
ReplyDeleteok sama-sama semoga bermanfa'at ya..
ReplyDelete