Kabarcık Sıralaması ve Ekleme Sıralaması
Kabarcık sıralama, bitişik öğe çiftlerini karşılaştırırken art arda sıralanacak listeden geçerek çalışan bir sıralama algoritmasıdır. Bir çift eleman yanlış sıradaysa, doğru sıraya yerleştirmek için değiştirilirler. Bu geçiş, başka takas gerekmeyene kadar tekrarlanır. Ekleme sıralama ayrıca, giriş listesindeki bir öğeyi zaten sıralanmış olan bir listede doğru konuma ekleyerek çalışan bir sıralama algoritmasıdır. Bu işlem, liste sıralanana kadar tekrar tekrar uygulanır.
Bubble Sort nedir?
Kabarcık sıralama, bitişik öğe çiftlerini karşılaştırırken art arda sıralanacak listeden geçerek çalışan bir sıralama algoritmasıdır. Bir çift eleman yanlış sıradaysa, doğru sıraya yerleştirmek için değiştirilirler. Bu geçiş, başka takas gerekmeyene kadar tekrarlanır (bu, listenin sıralandığı anlamına gelir). Listedeki daha küçük elementler bir balonun yüzeye çıkmasıyla en üste geldiğinden, buna balon sıralama adı verilir. Kabarcık sıralama çok basit bir sıralama algoritmasıdır, ancak n elemanlı bir listeyi sıralarken ortalama durum zamanı karmaşıklığı O(n2)'dir. Bu nedenle, kabarcıklı sıralama, çok sayıda öğe içeren listeleri sıralamak için uygun değildir. Ancak basitliği nedeniyle, algoritmalara giriş sırasında kabarcık sıralama öğretilir.
Ekleme Sıralaması nedir?
Ekle sıralama, giriş listesindeki bir öğeyi listede doğru konuma (zaten sıralanmış) ekleyerek çalışan başka bir sıralama algoritmasıdır. Bu işlem, liste sıralanıncaya kadar tekrar tekrar uygulanır. Yerleştirmeli sıralamada sıralama yerinde gerçekleştirilir. Bu nedenle algoritmanın iterasyonundan sonra listedeki ilk i+1 girişleri sıralanacak ve listenin geri kalanı sıralanmamış olacaktır. Her yinelemede, listenin sıralanmamış kısmındaki ilk eleman alınacak ve listenin sıralanmış bölümünde doğru yere eklenecektir. Ekleme sıralama, O(n2) ortalama durum zaman karmaşıklığına sahiptir. Bu nedenle, eklemeli sıralama büyük listeleri sıralamak için de uygun değildir.
Kabarcık Sıralaması ile Ekleme Sıralaması arasındaki fark nedir?
Hem kabarcık sıralama hem de araya ekleme sıralama algoritmaları O(n2) ortalama durum zaman karmaşıklığına sahip olsa da, kabarcık sıralama neredeyse her zaman araya ekleme sıralamasından daha iyi performans gösterir. Bunun nedeni, iki algoritmanın ihtiyaç duyduğu takas sayısından kaynaklanmaktadır (kabarcık türleri daha fazla takas gerektirir). Ancak kabarcık sıralamanın basitliği nedeniyle kod boyutu çok küçüktür. Ayrıca, pratik olarak kullanılmasına izin verecek olan O(n3/2) zaman karmaşıklığına sahip olan kabuk sıralama adı verilen bir eklemeli sıralama çeşidi vardır. Ayrıca araya eklemeli sıralama, "neredeyse sıralanmış" listeleri sıralamak için kabarcıklı sıralama ile karşılaştırıldığında çok etkilidir.
