Özet - Merge sort
- Algoritmalar kursu
- Orta seviye
- Ders 4/80
- 4 dk
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.
Başlangıç kodu
def merge_sort(arr):
# Böl, sırala, birleştirÖrnek çözüm
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]))Beklenen çıktı
[1, 1, 2, 3, 4, 5, 9]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Özet - Merge sort: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Bölme |
O(1) |
Birleştirme |
O(n) |
Toplam |
O(n log n) |
Bellek |
O(n) ek |
2 Kararlı koşul
Soru
if left[i] ____right[j]:
Cevap
if left[i] <=right[j]:Açıklama: <= doğru.
3 Merge sort'un bellek maliyeti nedir?
- O(n) ek Doğru cevap
- O(log n)
- O(n^2)
- O(1)
Açıklama: O(n) ek