Tam merge sort

Recursive merge sort uygulayıp O(n log n) karmaşıklığını öğrenirsin.

Tam merge sort

Tam merge sort, bölme + recursion + birleştirmeyi birleştirir. Temel durum: dizi tek elemanlıysa zaten sıralıdır, olduğu gibi döndürülür.

Değilse, diziyi ikiye böl, her yarıyı recursion ile sırala, sonra merge ile birleştir. Her çağrı problemi yarıya indirir.

Sonuç: kararlı, her zaman O(n log n) çalışan bir sıralama algoritması.

Kararlılık

Merge sort kararlıdır (stable): eşit anahtarlı elemanların göreli sırasını korur. Bunun nedeni, birleştirme sırasında left[i] <= right[j] kullandığımızda sol eleman önce alınır.

Kararlılık, nesneleri bir anahtara göre sıralarken önemlidir: ikincil sıralama bozulmaz.

Bu yüzden merge sort veri tabanı sıralamalarında ve dış sıralamada tercih edilir.

Uygulama Tam merge sort

merge_sort(arr) yaz. Diziyi böl, recursion ile sırala, birleştir. print(merge_sort([5, 2, 8, 1, 9])) ile [1, 2, 5, 8, 9] yazdır.

Örnek çözümü göster

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:]); result.extend(right[j:])
    return result
def merge_sort(arr):
    # Böl, sırala, birleştir
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
print(merge_sort([5, 2, 8, 1, 9]))

Kendini test et

Tam merge sort: kavramları eşleştir

Temel durum

Tek eleman
Bölme

İki yarı
Birleştirme

merge
Maliyet

O(n log n)
Merge sort ne zaman O(n log n) verir?
- Sadece en iyi durumda
- Sadece sıralı dizide
- Sadece en kötü durumda
- Her zaman
Cevabı göster

Her zaman — Her zaman
Temel durum
```
if len(arr) ____1:
```
Cevabı göster
```
if len(arr) <=1:
```

Sıradaki ders: Özet - Merge sort

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler