Birleştirmeli sıralama

Birleştirmeli sıralama zor bir problemi birçok kolay probleme dönüştürür: sıralı iki listeyi tek listede birleştirmek kolaydır. Her parça tek bir değer olana kadar listeyi ikiye bölün, sonra parçaları yeniden birleştirin. Klasik böl ve yönet algoritmasıdır ve girdi ne olursa olsun süresi n log n'dir.

Bir listenin iki sıralı yarısı tampon satırında, öndeki değerlerden küçük olanı listeye geri çıkıyor
Bir listenin iki sıralı yarısı tampon satırında, öndeki değerlerden küçük olanı listeye geri çıkıyor

Fikir

Birleştirme işin kolay kısmıdır. Her biri sıralı iki liste verildiğinde ilk değerlerini karşılaştırın ve küçük olanı alın. Yeni ilk değerleri karşılaştırın ve yine küçük olanı alın. Listelerden biri bitince diğerinin kalanını sona ekleyin. Her adım bir değer aldığı için toplam uzunluğu m olan iki listeyi birleştirmek en fazla m − 1 karşılaştırma gerektirir. Birleştirmeli sıralama bunu sıralamak için kullanır: listeyi ikiye bölün, her yarıyı birleştirmeli sıralamayla sıralayın ve iki yarıyı birleştirin.

Bir örnek

5, 1, 4, 2, 8 listesini alın. Bunu 5, 1 ve 4, 2, 8 olarak bölün. İlk yarı 5 ve 1'e bölünür, bunlar birleşerek 1, 5 olur. İkinci yarı 4 ve 2, 8'e bölünür; 2, 8 önce 2 ile 8'den birleştirilir, sonra 4 ile birleştirilerek 2, 4, 8 olur. Son olarak 1, 5 ve 2, 4, 8 birleşir: önce 1, sonra 2, sonra 4, sonra 5 ve geriye 8 kalır. Toplam 8 karşılaştırma, 12 yazma ve 4 birleştirme.

Neden n log n

Her bölme parçaları yarıya indirir; yaklaşık log₂ n düzeyden sonra her parça tek bir değer olur. Yukarı dönüşte her birleştirme düzeyi her değeri bir kez işler: düzey başına n yazma ve n'den az karşılaştırma. Toplamda bu yaklaşık n log₂ n eder. 40 değer için sıralama 216 yazma ve en fazla 177 karşılaştırma yapar; kabarcık sıralaması aynı liste için 780 karşılaştırmaya ihtiyaç duyabilir. Girdinin sırası bu algoritmalara göre çok daha az önemlidir: 40 değer için sıralı bir liste 100, ters bir liste 116, rastgele bir liste yaklaşık 160 karşılaştırma alır.

Tampon ve kararlılık

Listede yan yana duran iki yarıyı birleştirmek için olağan yöntem onları bir tampona kopyalar ve sırayla geri yazar. Uygulama bu tamponu ikinci çubuk satırı olarak gösterir. Liste kadar ek bellek gerektirir; birleştirmeli sıralamanın başlıca bedeli budur. Karşılığında sıralama kararlıdır: öndeki iki değer eşit olduğunda sol yarıdaki önce gider, böylece eşit değerler sıralarını korur. Kararlılık, kayıtları önce bir alana, sonra başka bir alana göre sıralarken önemlidir.

Tarihçe ve kullanım

John von Neumann birleştirmeli sıralamayı 1945'te tanımladı; bu da onu program saklayan bir bilgisayar için yazılmış ilk algoritmalardan biri yapar. Verileri uzun diziler hâlinde okuyup yazdığı için teypteki verileri sıralamanın standart yöntemiydi ve belleğe sığmayacak kadar büyük dosyalar için hâlâ kullanılır. Python'ın ve nesneler için Java'nın kullandığı Timsort, önce zaten sıralı dizileri bulan ve kısa parçalar için eklemeli sıralama kullanan bir birleştirmeli sıralamadır.

John von Neumann, Los Alamos kimlik fotoğrafında. Saklanan programlı bir bilgisayar için yazılmış ilk algoritmalardan biri olan birleştirmeli sıralamayı 1945’te tarif etti.
John von Neumann, Los Alamos kimlik fotoğrafında. Saklanan programlı bir bilgisayar için yazılmış ilk algoritmalardan biri olan birleştirmeli sıralamayı 1945’te tarif etti.

Keşfedin

Uygulamayı açın ve Adım'a basın. Listenin gölgeli kısmı bölünmekte ya da birleştirilmektedir, kesikli çizgi ise ortayı gösterir. Bir birleştirme başladığında iki yarı da tampon satırına iner; öndeki iki değer karşılaştırılır ve küçük olan yukarı geri çıkar. Sayaçları izleyin: yazmalar aynı uzunluktaki her liste için aynıdır; karşılaştırmalar sıralı veya ters bir listede en az, rastgele bir listede en fazladır, ama hiçbir zaman yaklaşık n log₂ n'yi aşmaz.

Sık sorulan sorular

Birleştirmeli sıralamanın zaman karmaşıklığı nedir?

En iyi, ortalama ve en kötü durumda O(n log n). Olağan sürüm tampon için O(n) ek bellek gerektirir.

Birleştirmeli sıralama ile hızlı sıralama arasındaki fark nedir?

İkisi de listeyi böler ve parçaları sıralar. Birleştirmeli sıralama değerlere bakmadan ortadan böler ve asıl işi birleştirirken yapar; hızlı sıralama asıl işi bölerken, değerleri bir pivotun etrafında taşıyarak yapar ve birleştirmeye ihtiyaç duymaz. Hızlı sıralama yerinde sıralar ve pratikte çoğu zaman daha hızlıdır, ama kötü girdilerde n²'ye kadar yavaşlayabilir ve kararlı değildir. Birleştirmeli sıralama her zaman n log n ve kararlıdır.

Aşağıdan yukarı birleştirmeli sıralama nedir?

Özyinelemesiz bir sürüm: önce komşu tek değerleri ikililer hâlinde, sonra ikilileri dörtlüler hâlinde birleştirir ve her turda uzunluğu ikiye katlayarak böyle devam eder. Burada gösterilen yukarıdan aşağı sürümle aynı işi yapar.

Birleştirmeli sıralama kararlı mıdır?

Evet, bu uygulamada olduğu gibi eşitlikte önce sol yarıdaki değer alındığı sürece.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Birleştirmeli sıralamayı deneyin