Kabarcık sıralaması
Kabarcık sıralaması, anlatması en kolay sıralama algoritmasıdır: iki komşuyu karşılaştırın, sıraları yanlışsa yerlerini değiştirin ve tekrarlayın. Uzun listelerde yavaştır ama her adımı kolayca takip edilir; bu yüzden izlenecek klasik ilk algoritmadır.
Temel fikir
Listeyi soldan sağa dolaşın ve her komşu çiftine bakın. Soldaki değer sağdakinden büyükse yerlerini değiştirin. Sona ulaştığınızda en büyük değer, bir kabarcığın yüzeye çıkması gibi, ta son sıraya taşınmış olur. Bu dolaşmaya geçiş denir. Liste sıralanana kadar geçişleri tekrarlayın.
Bir örnek
5, 1, 4, 2, 8 listesini alalım. İlk geçiş 5 ile 1'i karşılaştırır ve yerlerini değiştirir, ardından 5 ile 4 (takas), 5 ile 2 (takas) ve 5 ile 8 (takas yok): 1, 4, 2, 5, 8. 8 artık son yerindedir. İkinci geçiş 1 ile 4 (takas yok), 4 ile 2 (takas) ve 4 ile 5'i (takas yok) karşılaştırır: 1, 2, 4, 5, 8. Üçüncü geçişte hiç takas olmaz, yani liste sıralanmıştır: 9 karşılaştırma ve 4 takas.
Her geçiş neden bir değeri daha yerine oturtur
Bir geçiş sırasında o ana kadar görülen en büyük değer hep ileri taşınır: geçiş ona ulaştığında her karşılaştırma onu bir yer daha sağa kaydırır. Böylece ilk geçiş en büyük değeri sona, ikinci geçiş ikinci en büyüğü hemen önüne koyar ve bu böyle sürer. k. geçişten sonra son k yer kesinleşir ve sonraki geçiş bir yer önce durabilir. Geçişlerin kısalmasının nedeni budur.
Takas sayısı tersinme sayısına eşittir
Tersinme, yanlış sırada olan bir değer çiftidir: daha büyük bir değerin daha küçük bir değerden önce bir yerde durması. Sırası yanlış iki komşuyu takas etmek tam olarak bir tersinmeyi kaldırır ve yenisini yaratmaz. Bu yüzden kabarcık sıralaması, karşılaştırmalar hangi sırayla yapılırsa yapılsın, başlangıç listesindeki tersinme sayısı kadar takas yapar. Sıralı listede hiç tersinme yoktur; n değerli ters sıralı listede ise mümkün olan en fazla sayı olan n(n − 1)/2 tersinme vardır.
Erken durma ve maliyet
Bütün bir geçişte hiç takas olmazsa tüm komşular sıralıdır ve liste sıralanmıştır. Bunu kontrol etmek, kabarcık sıralamasının sıralı bir listeyi n − 1 karşılaştırmalık tek geçişte bitirmesini sağlar. En kötü durumda yine n − 1 geçiş ve n(n − 1)/2 karşılaştırma gerekir; ortalama takas sayısı ise n(n − 1)/4'tür. İkisi de n² ile büyür, yani listeyi iki katına çıkarmak sıralamayı yaklaşık dört kat uzatır.
Kabarcık sıralaması kararlıdır: eşit değerler asla yer değiştirmez, bu yüzden sıralarını korurlar. Ek bellek kullanmadan yerinde sıralar. Eklemeli sıralama da bu özelliklere sahiptir ve genellikle daha az adım gerektirir; birleştirmeli sıralama ve hızlı sıralama ise n log n ile orantılı süre alır, bu da uzun listelerde çok daha azdır.
Keşfedin
Uygulamayı açıp Oynat'a basın ya da her seferinde bir karşılaştırma ilerlemek için Adım'a basın. Karşılaştırılan iki değer vurgulanır, takas kendi rengiyle gösterilir ve yerine oturan değerler yeşile döner. En kötü durumu görmek için ters sıralı bir liste, erken durmanın sıralamayı birkaç geçişte bitirdiğini görmek için neredeyse sıralı bir liste deneyin ya da yukarıdaki örneğin sayılarını yazın.
Sık sorulan sorular
Kabarcık sıralamasının zaman karmaşıklığı nedir?
En kötü ve ortalama durumda O(n²): n değer için en fazla n(n − 1)/2 karşılaştırma. Erken durma ile zaten sıralı bir liste O(n), yani tek geçiş sürer. Yalnızca O(1) ek bellek gerekir.
Kabarcık sıralaması kararlı mıdır?
Evet. İki komşuyu yalnızca soldaki kesinlikle daha büyükse takas eder; bu yüzden eşit değerler birbirini asla geçmez ve ilk sıralarını korur.
Kabarcık sıralaması ile eklemeli sıralama arasındaki fark nedir?
İkisi de komşuları takas eder ve ikisi de tersinme sayısı kadar takas yapar. Kabarcık sıralaması sıralanmamış kısım üzerinde tam geçişler yapar; eklemeli sıralama ise her yeni değeri yalnızca gerektiği kadar geriye kaydırır, bu yüzden özellikle neredeyse sıralı listelerde genellikle daha az karşılaştırma yapar.
Kabarcık sıralaması ne zaman iyi bir seçimdir?
Çoğunlukla öğretimde ve sadeliğin hızdan daha önemli olduğu çok kısa listelerde. Daha büyük her şey için programlama dilinizin yerleşik sıralaması çok daha hızlıdı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.
Kabarcık sıralamasını deneyin