Contoh Merge Sort, Pengertian, beserta Cara Kerjanya
How to tekno
·waktu baca 4 menit
Tulisan dari How To Tekno tidak mewakili pandangan dari redaksi kumparan
PerbesarSalah satu materi yang perlu diketahui seorang pemrogram adalah pengertian dan contoh merge sort. Materi ini biasanya diaplikasikan pada bahasa pemrograman C, C++, Java, dan Python.
Lewat artikel ini, How To Tekno akan menjabarkan pengertian dan contoh merge sort dalam coding pada penjelasan berikut. Jadi, simak informasinya sampai selesai, ya!
Apa itu Merge Sort?
Dikutip dari laman Programiz, merge sort merupakan algoritma program komputer sorting atau penggabungan yang didasarkan pada prinsip Devide and Conquer Algorithm.
Jenis algoritma ini dibagi menjadi beberapa sub masalah. Jadi, setiap sub masalah tersebut akan diselesaikan secara individual. Nantinya, sub masalah digabungkan untuk mencari solusi akhir.
Sederhananya, proses Merge Sort dalam pemrograman adalah membagi masalah menjadi beberapa bagian kemudian mengurutkan setiap bagian. Selanjutnya, menggabungkan bagian yang telah diurutkan kembali menjadi satu.
Menurut laman Geeks For Geeks, keuntungan utama dari jenis algoritma Merge Sort ialah memiliki kompleksitas waktu dalam menyelesaikan masalah secara relatif cepat.
Program algoritma ini termasuk populer di kalangan programmer karena mengurutkan data set besar dan relatif efisien serta mudah diimplementasikan.
Merge sort sering dipakai bersamaan dengan algoritma lain seperti quicksort dengan tujuan meningkatkan kinerja keseluruhan dari rutinitas pengurutan yang dijalankan. Lantas seperti apa contoh merge sort? Simak rinciannya pada pejabaran berikut ini.
Contoh Merge Sort dalam Sistem Pemrograman
Untuk memahami cara kerja Merge Sort dalam sistem pemrograman, berikut contohnya yang dikutip dari laman educba.com.
Pada contoh ini array atau larik kode yang diberikan adalah 11, 6, 3, 24, 46, 22, dan 7. Cara kerja Merge Sort larik kode tersebut dibagi menjadi beberapa sub-array. Nantinya, setiap sub diselesaikan secara terpisah. Berikut caranya:
Bagi array dari 7 elemen kode di atas seeprti di bawah ini.
Array 1 adalah 11, 6, 3, dan 24. Array 2 adalah 46, 22, dan 7.
Bagi kedua larik tersebut menjadi dua, yakni 11 dan 6, 3 dan 4, 46 dan 22, kemudian 7.
Bagi lagi array di atas menjadi nilai tunggal hingga tidak dapat lagi dibagi seperti gambar di bawah ini.
Bandingkan elemen di setiap daftar dan gabungkan dengan cara mengurutkan ke dalam daftar lain. Misalnya, bandingkan 11 dan 6, dan urutannya dibalik.
Bandingkan 3 dan 24, mereka berada dalam urutan yang benar. Selanjutnya, bandingkan lagi 46 dan 22 dan masukkan 22 lalu 46. Selanjutnya, pertahankan 7 apa adanya.
Setelah itu, bagikan daftar dua nilai data yang berurutan dalam daftar yang terurut seperti gambar di bawah ini.
Kemudian daftar akan terlihat seperti ini setelah penggabungan terakhir.
Jika digabung dari beberapa sub array, hasil akhirnya akan seperti pada gambar berikut.
Setelah menemukan pengurutan yang benar, tulis kode algoritmanya seperti di bawah ini.
procedure merge_Sort( var array )
if ( length of a == 1 ) return array
var a1 as array = array[0] ... array[n/2]
var a2 as array = array[n/2+1] ... array[n]
a1 = mergesort( a1 )
a2 = mergesort( a2 )
return merge( a1, a2 )
end procedure
procedure merge( var a1 as array, var a2 as array )
var a3 as array
while ( a1 and a2 are not empty )
if ( a1[0] > a2[0] )
add a2[0] to the end of a3
remove a2[0] from a2
else
add a1[0] to the end of a3
remove a1[0] from a1
end if
end while
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
end while
while ( a2 is not empty )
add a2[0] to the end of a3
remove a2[0] from a2
end while
return a3
end procedure.
Perlu diperhatikan, setiap bahasa pemrograman memiliki cara penulisan yang berbeda. Namun, sistem yang dipakai untuk menyelesaikan Merge Sort menggunakan sistem yang sama.
Demikian contoh merge sort dalam sistem pemrograman. Semoga informasi di atas bermanfaat.
(IPT)
Frequently Asked Question Section
Apa itu merge sort?
Apa itu merge sort?
Merge sort merupakan algoritma sorting atau penggabungan yang didasarkan pada prinsip Devide and Conquer Algorithm.
Merge sort biasanya dipakai dalam bahasa pemrograman apa?
Merge sort biasanya dipakai dalam bahasa pemrograman apa?
Umumnya, merge sort diaplikasikan pada bahasa pemrograman C, C++, Java, dan Python.
Apa algoritma yang umumnya dipakai bersama merge sort?
Apa algoritma yang umumnya dipakai bersama merge sort?
Merge sort sering dipakai bersamaan dengan algoritma lain seperti quicksort.