Sorting mungkin salah
satu algoritma penting yang dilakukan oleh komputer dan tentunya satu dari
topik yang paling diselidiki dalam desain algoritma. Beberapa algoritma Sorting
telah ditemukan dan secara umum dideskripsikan dan dianalisa dalam Buku teks Algoritma
dan Data Struktur [Weiss, Aho] atau dalam standar referensi kerja [Knuth, van
Leeuwen]. algoritma Sorting dapat dibagi kedalam perbandingan dan
distribusi berdasarkan algoritma.
Perbandingan berdasarkan
metode dengan hanya membandingkan elemen satu sama lain dalam suatu array yang
ingin kita urutkan. Dalam ilmu komputer dan
matematika, algoritma sorting adalah suatu
algoritma yang meletakkan elemen dari sebuah list
dalam suatu urutan tertentu. Urutan yang paling sering
digunakan adalah urutan secara numeric dan
urutan lexicographical. Sorting yang efisien mempunyai
peranan penting untuk mengoptimasi penggunaan
dari algoritma-algoritma lain (seperti search dan merge) yang
membutuhkan list terurut untuk bekerja dengan benar; sorting yang efisien pun
seringkali berguna untuk canonicalizing data dan untuk menghasilkan output yang
dapat dibaca oleh manusia. Lebih jauh lagi, ouputan harus memenuhi dua kondisi
berikut :
• Output tidak dalam bentuk terurut menurun (tiap elemen tidak lebih kecil daripada elemen sebelumnya).
• Output adalah suatu permutasi, atau merupakan pengurutan ulang dari input.
Algoritma sorting merupakan masalah yang umum dalam materi pengenalan ilmu komputer, dimana tedapat banyak algoritma untuk setiap masalah yang menyediakan pengenalan yang baik untuk berbagai macam konsep inti algoritma, seperti notasi big O, algoritma divide-and-conquer, struktur data, algoritma random, analisis best, worst dan average case, time-space-tradeoff dan lower bounds. Beberapa contoh algoritma sorting adalah Quick Sort, Selection Sort, Bubble Sort, Merge Sort, Radix Sort. Algoritma yang akan dibahas lebih lanjut dalam dokumentasi ini adalah algoritma Merge Sort. Algoritma Merge Sort ialah algoritma pengurutan yang berdasarkan pada strategi divide and conquer. Algoritma ini terdiri dari dua bagian utama, pembagian list yang diberikan untuk di-sort ke dalam beberapa sublist yang lebih kecil, dan sort (mengurutkan) dan merge (menggabungkan) sublist-sublist yang lebih kecil ke dalam list hasil yang sudah diurutkan. Pembagian bisa dikatakan cukup mudah karena sublist-sublist tersebut dibagi ke dalam dua sublist yang ukurannya adalah setengah dari ukuran semula. Hal ini terus diulang sampai sublist itu cukup kecil untuk di-sort secara efisien (umumnya telah terdiri dari satu atau dua elemen). Dalam langkah merge dua sublist disatukan kembali dan diurutkan pada saat yang sama.
Dalam kebanyakan kasus MergeSort diimplementasikan secara rekursif dengan pendekatan top-down tapi menggunakan pendekatan bottom-up secara iterative pun dapat dibangun .
Algoritma untuk merge sort ialah sebagai berikut :
1. Untuk kasus n=1, maka table a sudah terurut sendirinya (langkah solve)
2. Untuk kasus n>1, maka :
a. DIVIDE: bagi table a menjadi dua bagian, bagian kiri dan bagian kanan, masingmasing bagian berukuran n/2 elemen.
b. CONQUER: secara rekursif, terapkan algoritma D-and-C pada masing masingmbagian.
c. MERGE: gabung hasil pengurutan kedua bagian sehingga diperoleh table a yangterurut.
• Output tidak dalam bentuk terurut menurun (tiap elemen tidak lebih kecil daripada elemen sebelumnya).
• Output adalah suatu permutasi, atau merupakan pengurutan ulang dari input.
Algoritma sorting merupakan masalah yang umum dalam materi pengenalan ilmu komputer, dimana tedapat banyak algoritma untuk setiap masalah yang menyediakan pengenalan yang baik untuk berbagai macam konsep inti algoritma, seperti notasi big O, algoritma divide-and-conquer, struktur data, algoritma random, analisis best, worst dan average case, time-space-tradeoff dan lower bounds. Beberapa contoh algoritma sorting adalah Quick Sort, Selection Sort, Bubble Sort, Merge Sort, Radix Sort. Algoritma yang akan dibahas lebih lanjut dalam dokumentasi ini adalah algoritma Merge Sort. Algoritma Merge Sort ialah algoritma pengurutan yang berdasarkan pada strategi divide and conquer. Algoritma ini terdiri dari dua bagian utama, pembagian list yang diberikan untuk di-sort ke dalam beberapa sublist yang lebih kecil, dan sort (mengurutkan) dan merge (menggabungkan) sublist-sublist yang lebih kecil ke dalam list hasil yang sudah diurutkan. Pembagian bisa dikatakan cukup mudah karena sublist-sublist tersebut dibagi ke dalam dua sublist yang ukurannya adalah setengah dari ukuran semula. Hal ini terus diulang sampai sublist itu cukup kecil untuk di-sort secara efisien (umumnya telah terdiri dari satu atau dua elemen). Dalam langkah merge dua sublist disatukan kembali dan diurutkan pada saat yang sama.
Dalam kebanyakan kasus MergeSort diimplementasikan secara rekursif dengan pendekatan top-down tapi menggunakan pendekatan bottom-up secara iterative pun dapat dibangun .
Algoritma untuk merge sort ialah sebagai berikut :
1. Untuk kasus n=1, maka table a sudah terurut sendirinya (langkah solve)
2. Untuk kasus n>1, maka :
a. DIVIDE: bagi table a menjadi dua bagian, bagian kiri dan bagian kanan, masingmasing bagian berukuran n/2 elemen.
b. CONQUER: secara rekursif, terapkan algoritma D-and-C pada masing masingmbagian.
c. MERGE: gabung hasil pengurutan kedua bagian sehingga diperoleh table a yangterurut.
Sorting method dikatakan stable jika sorting
method tersebut dapat menjaga keterurutan datadata yang sama (duplikat) sesuai
dengan kondisi aslinya (sebelum dilakukan sorting). Merge sort merupakan salah
satu algoritma sort yang stable.
Ilustrasi :
Ilustrasi :
Pentingnya Stable sort Pada kasus tertentu
dimana keterurutan data menjadi suatu prioritas utama stable sort sangat
berguna. Dengan menggunakan merge sort maka data yang telah terurut dijamin
merupakan data yang stable.
Kesimpulan
MergeSort adalah algoritma yang berdasarkan strategi divide-and-conquer. Algoritma ini tediri dari dua bagian utama, yaitu bagian pembagian list menjadi sublist-sublist yang lebih kecil dan bagian sort (pengurutan) dan merge (penggabungan) pada sublist-sublist tersebut. Algoritma MergeSort merupakan salah satu contoh algoritma yang stable ini.
BestCase untuk algoritma MergeSort ini yaitu pada saat data inputan berupa data yang terurut baik ascending maupun descending. Sedangkan WorstCasenya yaitu pada saat data inputan berupa data yang acak (random). Tetapi untuk kompleksitas waktu asimptotiknya sama yaitu, yaitu sebesar :
O(n 2 log n).
Kesimpulan
MergeSort adalah algoritma yang berdasarkan strategi divide-and-conquer. Algoritma ini tediri dari dua bagian utama, yaitu bagian pembagian list menjadi sublist-sublist yang lebih kecil dan bagian sort (pengurutan) dan merge (penggabungan) pada sublist-sublist tersebut. Algoritma MergeSort merupakan salah satu contoh algoritma yang stable ini.
BestCase untuk algoritma MergeSort ini yaitu pada saat data inputan berupa data yang terurut baik ascending maupun descending. Sedangkan WorstCasenya yaitu pada saat data inputan berupa data yang acak (random). Tetapi untuk kompleksitas waktu asimptotiknya sama yaitu, yaitu sebesar :
O(n 2 log n).
