Kabarcık sıralamanın gerçekleşimini gösteren animasyon
Sinking sort olarak da geçen bu sıralama algoritması, komşu olan her iki eleman arasında bir karşılaştırma yapar ve eğer istenenin tersi bir sıralama varsa swapping (yer değiştirme) işlemi uygular. Bu işlem ilk ugulandığında en büyük sayımız en sona yerleşir. Elimizde N elemanlı bir dizi olduğunu kabul edersek, tam bir sıralama elde edebilmemiz için N-1 kere diziyi baştan sona dolaşmamız gerekir.
Performans
Bubble sort, ortalama (avarage) ve en kötü durumda(worst-case) O(n2) zaman karmaşıklığına sahiptir. Best-case durumunda O(n) karmaşıklığı olabilir. Bunun için her bir ikili kontrol döngüsü sonunda bir yer değiştirme (swapping) işlemi yapılmış mı diye kontrol edilir.
Adım-Adım Uygulama
Elimizde 5 1 4 2 8 değerlerine sahip 5 elemanlı bir dizi olsun. Bunu bubble sort kullanarak adım adım sıralayalım:
İlk Döngü:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), İlk iki elemanı karşılaştırıyorum ve swapping yapıyorum.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), 5 > 4 swap yapıyorum
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), 5 > 2 swap yapıyorum
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), 8>5 olduğundan bu adımda swap yapmıyorum
İkinci Döngü:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), 4 > 2 swap yapıyorum
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ), İlk döngüm bittiğine göre sondaki elemanımın en büyük olduğunu biliyorum. gereksiz bir adımdır.
Sıralama işlemi tamamlandı, fakat bunu algoritma bilmiyor bunun için bir adım daha dolaşır.
Üçüncü Döngü:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) –> İki karşılaştırmada swap işlemi yapmadığımdan sıralama gerçekleşmiştir.
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ), sondan bir önceki adıma da ikinci döngü sayesinde bakmama gerek yoktur.
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ), gereksiz adım
Pseudocode
Bu pseudocode, bubble sort algoritması için uygulanan iyileştirmeleri de beraberinde içerir. Buna göre, zaten olması gereken yerde olan son elemanları kontrol etmez (n değerinin sürekli değişmesi sayesinde) ve bir swap işlemi gerçekleştirilmemişse zaten dizi sıralı diyerek algoritmayı bitirir.
