Apa itu Merge Sort dan Cara Penyelesaianya

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]
hasil merge_sort cara pertama

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]
Apa itu Merge Sort dan Cara Penyelesaianya - pesonainformatika.com
hasil pengurutan dengan rekursive

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++