- Birleştirilen kısım
- Karşılaştırılan
- Geri yazılan
- Şimdiye kadar birleştirilen
Birleştirmeli sıralama
Birleştirmeli sıralama bir böl ve yönet algoritmasıdır. Listeyi ikiye böler, her yarıyı aynı şekilde sıralar ve her seferinde öndeki değerlerden küçük olanı alarak iki sıralı yarıyı birleştirir. Yarıların bir tampon satırına alınıp sırayla geri yazılmasını istediğiniz hızda ya da adım adım izleyin; karşılaştırmaları, yazmaları ve birleştirmeleri sayın. Sıralamayı izlemek için Oynat'a, adım adım ilerlemek için Adım ve Geri'ye basın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Kutucuklar karşılaştırmaları, listeye geri yazmaları ve birleştirmeleri sayar. Çubuk sayısını ve başlangıç düzenini seçin ya da kendi sayılarınızı yazın. Tahta seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.
Nasıl çalışır
- Çubuk sayısını ve başlangıç düzenini seçin: rastgele, neredeyse sıralı, ters veya az sayıda farklı değerle. Ya da kendi sayılarınızı yazın.
- Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Sıralamanın herhangi bir yerine atlamak için adım kaydırıcısını sürükleyin.
- Her birleştirmeyi izleyin: iki sıralı yarı tampona iner ve öndeki değerlerden küçük olanı birer birer yukarı geri çıkar.
Birleştirmeli sıralama nasıl çalışır
Tek bir değer zaten sıralıdır. Daha uzun bir listeyi iki yarıya bölün ve her yarıyı birleştirmeli sıralamayla sıralayın. Sonra yarıları birleştirin: her yarının öndeki değerine bakın, küçük olanı sonuca taşıyın ve iki yarı da boşalana kadar tekrarlayın. İki yarı da sıralı olduğu için sonuç da sıralı olur.
Her zaman n log n
Tekrar tekrar ikiye bölmek yaklaşık log₂ n düzey verir ve her birleştirme düzeyi her değeri bir kez yazar; bu yüzden sıralama yaklaşık n log₂ n yazma ve en fazla o kadar karşılaştırma yapar. Kabarcık, seçmeli ve eklemeli sıralamadan farklı olarak bu sayı n² ile büyümez ve listenin sırası çok daha az önemlidir. Bedeli, liste kadar uzun bir tampondur. Birleştirmeli sıralama ayrıca kararlıdır; Python ve Java'daki sıralamaların temeli olmasının nedeni budur.
Sık sorulan sorular
Birleştirmeli sıralama nasıl çalışır?
Listeyi ikiye böler, her yarıyı birleştirmeli sıralamayla sıralar ve her seferinde öndeki değerlerden küçük olanı alarak iki sıralı yarıyı birleştirir. Tek değerli bir liste zaten sıralıdır, bu yüzden bölme orada durur.
Birleştirmeli sıralama kaç karşılaştırma yapar?
n değer için en fazla yaklaşık n log₂ n − n + 1, en az yaklaşık n log₂ n'nin yarısı kadar. 40 değer için bu en fazla 177'dir. Listeye geri yazmaların sayısı belirli bir n için hep aynıdır: her birleştirme düzeyinde değer başına bir.
Birleştirmeli sıralama neden ek bellek gerektirir?
İki yarıyı yerinde hızlıca birleştirmek zordur; bu yüzden olağan birleştirmeli sıralama yarıları bir tampona kopyalar ve sırayla geri yazar. Tampon liste kadar uzundur; hızlı sıralama ve yığın sıralamasına göre başlıca dezavantajı budur.
Birleştirmeli sıralama kararlı mıdır?
Evet. Öndeki iki değer eşit olduğunda sol yarıdaki önce gider; böylece eşit değerler ilk sıralarını korur.
Sayılarım bir yere gönderiliyor mu?
Hayır. Sıralama tarayıcınızda çalışır ve son ayarlarınız bu tarayıcının yerel depolamasında kalır.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Editöre Git