Merge işlemi

İ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.

Örnek çözümü göster

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]))

Kendini test et

Karşılaştırma

if left[i] ____right[j]:

Cevabı göster

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

Merge işlemi: kavramları eşleştir

Gösterici

Başlangıç
Sol dizi

İlk yarı
Kalan

Sona kopyala
Maliyet

O(n)
Merge sırasında ne zaman eleman kopyalanır?
- Hiç
- Sadece sonda
- Küçük olan bulunduğunda
- Rastgele
Cevabı göster

Küçük olan bulunduğunda — Küçük olan bulunduğunda

Sıradaki ders: Tam merge sort

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler