Merge işlemi
- Algoritmalar kursu
- Orta seviye
- Ders 2/80
- 4 dk
İki sıralı diziyi tek sıralı diziye birleştirmeyi öğrenirsin.
Merge işlemi
Merge, iki sıralı diziyi tek sıralı diziye birleştirir. Her dizinin başına bir gösterici koyarız, küçük olanı sonuca kopyalar ve o göstericiyi ilerletiriz.
İki dizi de tükenene kadar devam eder. Her adımda bir eleman kopyalanır; toplam n eleman için O(n) iş yapılır.
Bu adım merge sort'un kalbidir: bölme ucuz, birleştirme değerli.
Sonuç dizisi
Birleştirme sırasında boş bir result listesi tutarız. Her adımda bir eleman eklenir; sonunda result sıralı tüm diziyi içerir.
Kalan elemanlar için iki ayrı while döngüsü daha yazılır: sol veya sağ dizide eleman kaldıysa hepsini sona kopyalarız. Çünkü kalanlar zaten sıralıdır.
Bu kalan kopyalama O(n) toplam işi bozmaz.
Uygulama İki sıralı diziyi birleştir
merge(left, right) yaz. İki sıralı diziyi birleştirip sıralı sonuç döndür. print(merge([1, 4], [2, 5])) ile [1, 2, 4, 5] yazdır.
Başlangıç kodu
def merge(left, right):
# İki sıralı diziyi birleştirÖrnek çözüm
def merge(left, right):
# İki sıralı diziyi birleştir
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([1, 4], [2, 5]))Beklenen çıktı
[1, 2, 4, 5]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Karşılaştırma
if left[i] ____right[j]:if left[i] <=right[j]:Açıklama: <= doğru.
2 Merge işlemi: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Gösterici |
Başlangıç |
Sol dizi |
İlk yarı |
Kalan |
Sona kopyala |
Maliyet |
O(n) |
3 Merge sırasında ne zaman eleman kopyalanır?
- Hiç
- Sadece sonda
- Küçük olan bulunduğunda Doğru cevap
- Rastgele
Açıklama: Küçük olan bulunduğunda