Kabarcık Sıralaması, (bubble sort), bilgisayar bilimlerinde kullanılan yalın bir sıralama algoritmasıdır.
Sıralanacak dizinin üzerinde sürekli ilerlerken her defasında iki
öğenin birbiriyle karşılaştırılıp, karşılaştırılan öğelerin yanlış
sırada olmaları durumunda yerlerinin değiştirilmesi mantığına dayanır.
Algoritma, herhangi bir değişiklik yapılmayıncaya kadar dizinin başına
dönerek kendisini yineler. Adına "Kabarcık" sıralaması denmesinin nedeni büyük olan sayıların aynı suyun altındaki bir kabarcık gibi dizinin üstüne doğru ilerlemesidir.
Başlangıçta yer yer değiştirme sıralaması olarak adlandırılan kabarcık sıralaması, dizi içindeki büyük elemanların algoritmanın her adımında dizinin sonuna doğru doğrusal olarak ilerlemesini sağlar. Bu ilerleme, seçmeli sıralama algoritmasındaki dizideki değeri küçük olan elemanların dizinin başında kümelenmesi yöntemine benzer şekilde gerçekleşir.
İnceleme
Kabarcık sıralaması dizinin başından başlar ve dizi elemanlarını
sırayla seçer. Seçilen dizi elemanı kendinden sonra gelen elemandan
büyükse bu iki elemanın yerleri değiştirilir. Bu işlem sonucunda
dizinin en büyük elemanı dizi sonuna yerleştirildiğinden bir sonraki
adımda arama sınırı bir eleman geri çekilir. Bu işlem, dizinin
sonundaki elemanın karşılaştırılmasına kadar yinelenerek sürdürülür.
Algoritmanın Karmaşıklığı
Kabarcık sıralama algoritmasının ortalama ve en kötü durumdaki karmaşıklığı
 'dir. Algoritma ortalama ve en kötü durumda
 adet karşılaştırma ve yer değiştirme gerçekleştirir.
Algoritmanın Adım Adım İşleyişi
İçeriği "5 1 4 2 8" olan bir dizi kabarcık sıralaması ile en
küçükten en büyüğe doğru aşağıdaki biçimde sıralanır. Her adımda
dizinin kalın olarak işaretlenmiş elemenları karşılaştırılan elemanlardır.
Birinci Geçiş:
( 5 1 4 2 8 )
 ( 1 5 4 2 8 ) Burada algoritma ilk iki elemanı karşılaştırır ve yerlerini değiştirir.
( 1 5 4 2 8 )
( 1 4 5 2 8 )
( 1 4 5 2 8 )
( 1 4 2 5 8 )
( 1 4 2 5 8 )
( 1 4 2 5 8 ) Burada elemanlar zaten sıralı olduğu için algoritma yerlerini değiştirmez.
İkinci Geçiş:
( 1 4 2 5 8 )
( 1 4 2 5 8 )
( 1 4 2 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
Artık dizi sıralıdır ancak algoritma işlemin bittiğini bilmemektedir.
Algoritmanın dizinin sıralandığını anlaması için bütün dizinin
üzerinden hiçbir değişiklik yapmadan tam bir geçiş yapması gerekir.
Üçüncü Geçiş:
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 )
Sonuç olarak dizi sıralanmıştır ve algoritma sonlanır.
|
