Merge sort

Struktur Data dan Algoritma di Python

Miriam Antona

Software engineer

Merge sort

Mengikuti prinsip divide and conquer
- Divide
  - membagi masalah jadi submasalah lebih kecil
- Conquer
  - submasalah diselesaikan secara rekursif
- Combine
  - solusi submasalah digabungkan untuk solusi akhir

Merge sort - praktik

Representasi skematis daftar dengan angka acak.

Merge sort - praktik

Representasi skematis daftar dengan angka acak. Daftar dibagi menjadi dua bagian.

Merge sort - praktik

Representasi skematis daftar dengan angka acak. Daftar dibagi dua. Ada dua daftar baru: yang pertama berisi setengah kiri daftar asli dan yang kedua setengah kanannya.

Merge sort - praktik

Representasi skematis daftar dengan angka acak. Daftar baru dibagi menjadi dua bagian.

Merge sort - praktik

Representasi skematis daftar dengan angka acak. Ada daftar baru hasil pembagian dari daftar yang terakhir dibagi.

Merge sort - praktik

Representasi skematis daftar dengan angka acak. Daftar baru dibagi menjadi dua bagian.

Merge sort - praktik

Representasi skematis daftar dengan angka acak. Ada daftar baru hasil pembagian dari daftar yang terakhir dibagi.

Merge sort - praktik

Representasi skematis daftar dengan angka acak. Daftar baru dibagi menjadi dua bagian.

Merge sort - praktik

Representasi skematis daftar dengan angka acak. Daftar baru dibagi menjadi dua bagian.

Merge sort - praktik

Representasi skematis daftar dengan angka acak. Elemen dari daftar terakhir yang dibagi telah diurutkan.

Merge sort - praktik

Representasi skematis daftar dengan angka acak. Elemen dari daftar terakhir yang dibagi telah digabung dan diurutkan.

Merge sort - praktik

Representasi skematis daftar dengan angka acak. Elemen dari daftar terakhir yang dibagi telah digabung dan diurutkan.

Merge sort - praktik

Representasi skematis daftar dengan angka acak. Elemen dari daftar terakhir yang dibagi telah digabung dan diurutkan. Semua elemen kini terurut.

Merge sort - implementasi

def merge_sort(my_list):
  if len(my_list) > 1:

    mid = len(my_list)//2
    left_half = my_list[:mid]
    right_half = my_list[mid:]

    merge_sort(left_half)
    merge_sort(right_half)


    i = j = k = 0

    while i < len(left_half) and j < len(right_half):

      if left_half[i] < right_half[j]:

        my_list[k] = left_half[i]

        i += 1

      else:

        my_list[k] = right_half[j]

        j += 1

      k += 1

    while i < len(left_half):

      my_list[k] = left_half[i]
      i += 1
      k += 1


    while j < len(right_half):
      my_list[k] = right_half[j]
      j += 1
      k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)

[1, 4, 20, 22, 30, 35, 40, 50, 90]

Merge sort - kompleksitas

Kasus terburuk: $O(n\log{}n)$
- peningkatan signifikan dibanding bubble, selection, dan insertion sort
- cocok untuk daftar besar
Rata-rata: $\Theta(n\log{}n)$
Terbaik: $\Omega(n\log{}n)$
- algoritma lain (mis. bubble, insertion) punya best case lebih baik
Kompleksitas ruang: $O(n)$
- lebih buruk dari algoritma dengan $O(1)$
Varian lain dapat mengurangi kebutuhan ruang ini

Ayo berlatih!

Struktur Data dan Algoritma di Python