secara riteral mege sort berarti mengurutkan dengan cara menggabungkan. sesuai dengan namanya, algoritma mege sort melibatkan penggabungan secara berulang-ulang hingga membentuk rangakian nilai yang terurut.
berdasarkan jenisnya ini termasuk kedalam jenis algoritma divid and conquer yang berkerja secara rekursif memecah kemudian menggabungkan rangakaian nilai yang ingin diurutkan sampai seluruh nilai menjadi terurut.
Penjelasan mekaniskme pengurutan
algoritma mege sort sendiri sebenarnya tidak hanya menggabungkan. algoritma ini terlebih dahulu pemecahan berulang-ulang, baru kemudian diikuti penggabungan yang disertai pengurutan.
Tahap pemecahan
Tahap pemecahan merupakan tahap divide, yang menyederhanakan persoalan kedalam bentuk yang lebih kecil. pada tahap ini, algoritma mege sort melakukan pemecahan rangkaian nilai (list) menjadi dua bagian (dipecah ditengah) terus menerus sehingga hanya tersisa atau element pada setiap pecahan. lihat potongan kode di bawah ini
jumlah_bilangan = len(list_bilangan)
posisi_tengah = len(list_bilangan)//2
potongan_kiri = list_bilangan[:posisi_tengah]
potongan_kanan = list_bilangan[posisi_tengah:]
merge_sort(potongan_kiri)
merge_sort(potongan_kanan)
potongan kode di atas menunjukan adalah tahap conquer, kebalikan dari proses pemechan, dimana seluruh potongan yang dihasilkan dari proses pemecahan kemudian digabung secara bertingakat.
pada tahap inilah terjadi pengurutan, karena saat digabungkan, masing element - element dari dua potongan yang akan digabungkan, dibandingkan terlebih dahulu untuk kemudian diletakan pada sebuah potongan baru sesuai urutan nilainya, ini berati pada masing-masing pecahan yang akan digabungkan seluruh elemennya terurut dari proses penggabungan sebelumnya.
perhatikan potongan kode program dibawah ini
jumlah_bilangan_kiri = len(potongan_kiri)
jumlah_bilangan_kanan = len(potongan_kanan)
c_all,c_kiri,c_kanan = 0,0,0 # pencacah/counter
# selama masih ada elemen pada potongan
while c_kiri < jumlah_bilangan_kiri or c_kanan < jumlah_bilangan_kanan:
# elemen di potongan kiri habis
if c_kiri == jumlah_bilangan_kiri:
list_bilangan[c_all] = potongan_kanan[c_kanan]
# elemen di potongan kanan habis
elif c_kanan == jumlah_bilangan_kanan:
list_bilangan[c_all] = potongan_kiri[c_kiri]
# nilai antrian elemen di potongan kiri lebih kecil
elif potongan_kiri[c_kiri] <= potongan_kanan[c_kanan]:
list_bilangan[c_all] = potongan_kiri[c_kiri]
# nilai antrian elemen di potongan kanan lebih kecil
list_bilangan[c_all] = potongan_kanan[c_kanan]
jumlah_bilangan_kiri = len(potongan_kiri)
jumlah_bilangan_kanan = len(potongan_kanan)
c_all,c_kiri,c_kanan = 0,0,0 # pencacah/counter
# selama masih ada elemen pada potongan
while c_kiri < jumlah_bilangan_kiri or c_kanan < jumlah_bilangan_kanan:
# elemen di potongan kiri habis
if c_kiri == jumlah_bilangan_kiri:
list_bilangan[c_all] = potongan_kanan[c_kanan]
c_kanan = c_kanan + 1
# elemen di potongan kanan habis
elif c_kanan == jumlah_bilangan_kanan:
list_bilangan[c_all] = potongan_kiri[c_kiri]
c_kiri = c_kiri + 1
# nilai antrian elemen di potongan kiri lebih kecil
elif potongan_kiri[c_kiri] <= potongan_kanan[c_kanan]:
list_bilangan[c_all] = potongan_kiri[c_kiri]
c_kiri = c_kiri + 1
# nilai antrian elemen di potongan kanan lebih kecil
else:
list_bilangan[c_all] = potongan_kanan[c_kanan]
c_kanan = c_kanan + 1
c_all = c_all + 1kode lengkap
berikut ini adalah kode lengkapnya
Post a Comment