Meydan okuma 1
- Algoritmalar kursu
- Orta seviye
- Ders 77/80
- 4 dk
Merge sort ile bir diziyi sıralayıp yazdırırsın.
Meydan okuma 1: Merge sort
Bu meydan okumada merge sort ile bir diziyi sıralayıp yazdıracaksın. Önceki becerilerini birleştir.
Dizi: [5, 2, 8, 1, 9]. Sıralı çıktı: [1, 2, 5, 8, 9].
Merge sort; böl, recursive sırala ve birleştir adımlarıyla O(n log n) verir.
Uygulama Merge sort
merge_sort(arr) yaz. Diziyi merge sort ile sırala ve döndür. print(merge_sort([5, 2, 8, 1, 9])) ile [1, 2, 5, 8, 9] yazdır.
Başlangıç kodu
def merge_sort(arr):
# Merge sort sıralaÖrnek çözüm
def merge_sort(arr):
# Merge sort sırala
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
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
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 Merge sort'un karmaşıklığı nedir?
- O(n^2)
- O(n log n) Doğru cevap
- O(log n)
- O(n)
Açıklama: O(n log n).
2 Orta indeks
Soru
mid = len(arr) ____ 2
Cevap
mid = len(arr) // 2Açıklama: // doğru.
3 Meydan okuma 1: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
merge sort |
Böl birleştir |
O(n log n) |
Hızlı |
stable |
Sıralı kalır |
divide |
Böl |