Apa itu Merge Sort dan Cara Penyelesaianya – pesonainformatika.com halo ketemu lagi kali ini kita akan belajar tentang algoritma merge sort dan cara memecahkan nya menggunakan bahasa pemrograman python
Apa itu Merge Sort
sebelum membuat program tentang bagaimana membuat program tentang merge sort ini kita harus mengetahui apa itu merge sort
Merge Sort adalah algoritma pengurutan menggunakan divide conquer yaitu dengan cara memecah kemudian menyelesaikan setiap bagian- bagian pecahanya tadi kemudian digabungkan kembali
Trik Pemecahan Pada Merge Sort
sekarang setelah sekilas membahas tentang Merge Sort sekarang kita akan membahas bagaimana konsep dan trik merge sort secara mendalam
Algoritma ini durumuskan dalam 3 langkah (divide-and-conquer) seperti ini
- Divide: Memilih/memilah elemen dari data menjadi dua bagian.
- Conquer: setiap bagian dengan memanggil prosedur merge sort secara rekursif
- Kombinasi: Mengkombinasi/Menggabungkan setiap bagian dari rangkaian data tersebut
dari 3 langkah tersebut kita mendapatkan data secara berurutan, dan proses rekursif akan berhenti jika sudah mencapai elemen dasar
Membuat Program
buka text editor kamu buat file misalnya merge_sort.py kemudian isi seperti ini
def merge_two_list(a: list, b: list) -> list:
sorted_list = []
length_a = len(a)
length_b = len(b)
# counter
i = j = 0
while i < length_a and j < length_b:
if a[i] <= b[j]:
sorted_list.append(a[i])
i += 1
else:
sorted_list.append(b[j])
j += 1
while i < length_a:
sorted_list.append(a[i])
i += 1
while j < length_b:
sorted_list.append(b[j])
j += 1
return sorted_list
if __name__ == '__main__':
data_list_1 = [5, 8, 12, 56, 89, 100]
data_list_2 = [7, 9, 45, 51]
sort = merge_two_list(data_list_1, data_list_2)
print(sort)
jika kita jalankan hasilnya seperti ini
[5, 7, 8, 9, 12, 45, 51, 56, 89, 100]
Penjelasan Program
dari konsep diatas kita bisa memahami bahwa kita dapat mengurutkan list menggunakan metode (Algoritma) merge sort.
kemudian kita membuat fungsi dengan parameter berupa list lalu fungsi tersebut mengembalikan inputan berupa list, kita menggunakan function annotation
disini kita bisa lihat kita mendefinisikan list kosong yang bernama sorted_list untuk menampung elemen elemen yang telah diurutkan dari kedua list, kemudian kita cek panjang dari kedua list tersebut kemudian disimpan dalam variable
def merge_two_list(a: list, b: list) -> list:
sorted_list = []
length_a = len(a)
length_b = len(b)
kemudian kita mendefinisikan dua variable yang akan kita gunakan sebagai counter dengan nama, yang nantinya kita akan menggunakan counter ini untuk menampung nilai dari index setiap list yang akan diurutkan
# counter
i = j = 0
kemudian kita cek apakah i dan j lebih kecil dari panjang list A dan panjang list B, lalu jika list A dengan index ke i lebih kecil dari list B dengan index ke j maka item dari list A index ke i ditambahkan ke sorted_list (yang tadinya kosong) kemudian i setiap melakukan perulangan ditambah dengan 1 jika tidak maka sebaiknya
while i < length_a and j < length_b:
if a[i] <= b[j]:
sorted_list.append(a[i])
i += 1
else:
sorted_list.append(b[j])
j += 1
while j < length_b:
sorted_list.append(b[j])
j += 1
kemudian dikembalikan (di return) sebagai list yang telah diurutkan
Mengurutkan List dengan Algoritma
ini merupakan lanjutan dari program tersebut, dalam program ini kita akan memotong list menjadi 2 bagian kemudian kita urutkan dengan tektik merge sort yang telah kita pelajari diatas, kita buat fungsi seperti ini
def merge_sort(arr: list) -> list:
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
# merging list
left = merge_sort(left)
right = merge_sort(right)
# return sorting
return merge_two_list(left, right)
jika kita lihat secara keseluruhan maka akan menjadi seperti ini
def merge_two_list(a: list, b: list) -> list:
sorted_list = []
length_a = len(a)
length_b = len(b)
# counter
i = j = 0
while i < length_a and j < length_b:
if a[i] <= b[j]:
sorted_list.append(a[i])
i += 1
else:
sorted_list.append(b[j])
j += 1
while i < length_a:
sorted_list.append(a[i])
i += 1
while j < length_b:
sorted_list.append(b[j])
j += 1
return sorted_list
def merge_sort(arr: list) -> list:
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
# merging list
left = merge_sort(left)
right = merge_sort(right)
# return sorting
return merge_two_list(left, right)
if __name__ == '__main__':
arrays = [10, 3, 5, 15, 7, 8, 23, 98, 29]
print(merge_sort(arrays))
jika kita jalankan maka akan menjadi seperti ini
[3, 5, 7, 8, 10, 15, 23, 29, 98]
gimana cukup mudah bukan, sampai sini dulu studi kasus kali ini semoga bermanfaat dan selamat mencoba, soure code dapat diakses melalui github ikuti terus pesonainformatika, dan dapatkan studi kasus bahasa pemrograman lainya seperti Java, Python C++
people who use linux and people who are friendly