Özet - Merge sort

Merge sort uygulayıp sonucu yazdıran mini görev yaparsın.

Özet - Merge sort

Merge sort üç adımda çalışır: böl, recursion ile sırala, birleştir. Temel durum tek elemanlı dizidir.

Her düzeyde n eleman işlenir, log n düzey vardır; toplam O(n log n). Kararlıdır ve ek O(n) bellek kullanır.

Büyük dizilerde ve dış sıralamada güçlü bir seçimdir; küçük dizilerde ek bellek yükü olabilir.

Uygulama Özet: merge sort

merge_sort(arr) yaz. Böl, sırala, birleştir. print(merge_sort([3, 1, 4, 1, 5, 9, 2])) ile [1, 1, 2, 3, 4, 5, 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([3, 1, 4, 1, 5, 9, 2]))

Kendini test et

Özet - Merge sort: kavramları eşleştir

Bölme

O(1)
Birleştirme

O(n)
Toplam

O(n log n)
Bellek

O(n) ek

Kararlı koşul

if left[i] ____right[j]:

Cevabı göster

if left[i] <=right[j]:

Merge sort'un bellek maliyeti nedir?
- O(n) ek
- O(log n)
- O(n^2)
- O(1)
Cevabı göster

O(n) ek — O(n) ek

Sıradaki ders: Pivot seçimi

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler