Birleştirmeli sıralama

Python'da Veri Yapıları ve Algoritmalar

Miriam Antona

Software engineer

Birleştirmeli sıralama

böl ve fethet yaklaşımını izler
- Böl
  - problemi daha küçük alt problemlere böler
- Çöz
  - alt problemler özyineli olarak çözülür
- Birleştir
  - alt problemlerin çözümleri birleştirilerek nihai çözüm elde edilir

Birleştirmeli sıralama - uygulama

Sırasız sayıların bulunduğu bir listenin şematik gösterimi.

Birleştirmeli sıralama - uygulama

Sırasız sayıların bulunduğu bir listenin şematik gösterimi. Liste ikiye bölünmüş.

Birleştirmeli sıralama - uygulama

Sırasız sayıların bulunduğu bir listenin şematik gösterimi. Liste ikiye bölünmüş. İki yeni liste var: ilki orijinal listenin sol yarısı, ikincisi sağ yarısı.

Birleştirmeli sıralama - uygulama

Sırasız sayıların bulunduğu bir listenin şematik gösterimi. Yeni listeler ikiye bölünmüş.

Birleştirmeli sıralama - uygulama

Sırasız sayıların bulunduğu bir listenin şematik gösterimi. Son bölünmüş listelerin bölünmeleriyle yeni listeler var.

Birleştirmeli sıralama - uygulama

Sırasız sayıların bulunduğu bir listenin şematik gösterimi. Yeni listeler ikiye bölünmüş.

Birleştirmeli sıralama - uygulama

Sırasız sayıların bulunduğu bir listenin şematik gösterimi. Son bölünmüş listelerin bölünmeleriyle yeni listeler var.

Birleştirmeli sıralama - uygulama

Sırasız sayıların bulunduğu bir listenin şematik gösterimi. Yeni listeler ikiye bölünmüş.

Birleştirmeli sıralama - uygulama

Sırasız sayıların bulunduğu bir listenin şematik gösterimi. Yeni listeler ikiye bölünmüş.

Birleştirmeli sıralama - uygulama

Sırasız sayıların bulunduğu bir listenin şematik gösterimi. Son bölünmüş listelerdeki öğeler sıralanmış.

Birleştirmeli sıralama - uygulama

Sırasız sayıların bulunduğu bir listenin şematik gösterimi. Son bölünmüş listelerin öğeleri birleştirilip sıralanmış.

Birleştirmeli sıralama - uygulama

Sırasız sayıların bulunduğu bir listenin şematik gösterimi. Son bölünmüş listelerin öğeleri birleştirilip sıralanmış.

Birleştirmeli sıralama - uygulama

Sırasız sayıların bulunduğu bir listenin şematik gösterimi. Son bölünmüş listelerin öğeleri birleştirilip sıralanmış. Tüm öğeler sıralı.

Birleştirmeli sıralama - uygulama

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]

Birleştirmeli sıralama - karmaşıklık

En kötü durum: $O(n\log{}n)$
- kabarcık, seçim ve ekleme sıralamaya göre ciddi iyileşme
- büyük listeler için uygundur
Ortalama durum: $\Theta(n\log{}n)$
En iyi durum: $\Omega(n\log{}n)$
- diğer algoritmalar (örn. kabarcık, ekleme) en iyi durumda daha iyidir
Alan karmaşıklığı: $O(n)$
- $O(1)$ olan algoritmalardan daha kötüdür
Bazı varyantlar bu alanı azaltır

Hadi pratik yapalım!

Python'da Veri Yapıları ve Algoritmalar