Sıralama Algoritmaları

Kabarcık sıralaması



Kabarcık sıralaması'nın rastgele üretilmiş sayıları sıraladığını gösteren bir örnek

Kabarcık Sıralaması, 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 ) o ( 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 ) o ( 1 4 5 2 8 )

( 1 4 5 2 8 ) o ( 1 4 2 5 8 )

( 1 4 2 5 8 ) o ( 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 ) o ( 1 4 2 5 8 )

( 1 4 2 5 8 ) o ( 1 2 4 5 8 )

( 1 2 4 5 8 ) o ( 1 2 4 5 8 )

( 1 2 4 5 8 ) o ( 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 ) o ( 1 2 4 5 8 )

( 1 2 4 5 8 ) o ( 1 2 4 5 8 )

( 1 2 4 5 8 ) o ( 1 2 4 5 8 )

( 1 2 4 5 8 ) o ( 1 2 4 5 8 )

Sonuç olarak dizi sıralanmıştır ve algoritma sonlanır

Sözde Kodu

Algoritmanın yalın bir sözde kod olarak gösterimi aşağıdaki gibidir:

procedure bubbleSort( A : sıralanabilir öğe dizisi ) defined as:

do

swapped := false

for each i in 0 to length( A ) - 2 do:

if A[ i ] > A[ i + 1 ] then

swap( A[ i ], A[ i + 1 ] )

swapped := true

end if

end for

while swapped



end procedure </gösterilebilir:

procedure bubbleSort( A : sıralanabilir öğe dizisi ) defined as:

for each i in 1 to length(A) do:

for each j in length(A) downto i + 1 do:

if A[ j -1 ] > A[ j ] then

swap( A[ j - 1], A[ j ] )

end if

end for

end for

end procedure