Tam merge sort
- Algoritmalar kursu
- Orta seviye
- Ders 3/80
- 4 dk
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.
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([5, 2, 8, 1, 9]))Beklenen çıktı
[1, 2, 5, 8, 9]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Tam merge sort: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Temel durum |
Tek eleman |
Bölme |
İki yarı |
Birleştirme |
merge |
Maliyet |
O(n log n) |
2 Merge sort ne zaman O(n log n) verir?
- Sadece en iyi durumda
- Sadece sıralı dizide
- Sadece en kötü durumda
- Her zaman Doğru cevap
Açıklama: Her zaman
3 Temel durum
if len(arr) ____1:if len(arr) <=1:Açıklama: <= doğru.