Buble Search Algoritması Nedir ?

Bubble Search algoritması, bilgisayar bilimlerinde kullanılan yalın bir sıralama algoritmasıdır. Sıralanacak dizinin üzerinde sürekli ilerlerken her defasında iki öğernin 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ılamayıncaya kadar dizinin başına dönerek kendisini yeniler.

Bir dizi içerisindeki elemanların en sol tarafından başlayarak 2li şekilde dizi elamanları karşılaştırılmaya başlanarak döngünün ilerlemesi sağlanır.

Her bir döngüye Past ( geçiş ) adı verilir. Her bir past içerisindeki döngü sayısı dizi elemanı – 1 ( n-1) kadardır. -1 değeri, en son dizi elemanının, kendinden sonra bir rakam olmadığı için başka bir rakam ile karşılaştırılma gereğinin duyulmadığı durumdan kaynaklanır. Past işlemi, herhanbi bir döngüde değişiklik yapılmayıncaya kadar devam eder.

Örnek:

(3,5,1,7,2) dizisi elimizde olsun. Bunu en küçükten en büyüğe doğru sıralamak istersek bilgisayar tarafından yapılacak işlem şu şekilde olacaktır:

Birinci Geçiş ( First Past )

( 3,5,1,7,2 ) –> ( 3,5,1,7,2) ( bu aşamada 3 ile 5 sayısı karşılaştırılıyor. 3, 5’ten küçük olduğu için yer değişim işlemi yapılmıyor. )

( 3,5,1,7,2) –> ( 3,1,5,7,2) ( bu aşamada 5 ile 1 sayısı karşılaştırılıyor. 5, 1’den büyük olduğu için dizi içerisinde bir sağa kaydırılıyor.)

( 3,1,5,7,2 ) –> ( 3,1,5,7,2 ) ( bu aşamada 5 ile 7 sayısı karşılaştırılıyor. 5, 7’den küçük olduğu için yer değiştirilme işlemi yapılmıyor. )

( 3,1,5,7,2 ) –> ( 3,1,5,2,7 ) ( bu aşamada 7 ile 2 sayısı karşılaştırılıyor. 7, 2’den büyük olduğu için yer değiştirilme işlemi yapılıyor. )

İkinci Geçiş ( Second Past )

( 3,1,5,2,7 ) –> ( 1,3,5,2,7 )

( 1,3,5,2,7 ) –> ( 1,3,5,2,7 )

( 1,3,5,2,7 ) –> ( 1,3,2,5,7 )

( 1,3,2,5,7 ) –> ( 1,3,2,5,7 )

Üçüncü Geçiş ( Third Past )

( 1,3,2,5,7 ) –> ( 1,3,2,5,7 )

( 1,3,2,5,7 ) –> ( 1,2,3,5,7 )

( 1,2,3,5,7 ) –> ( 1,2,3,5,7 )

( 1,2,3,5,7 ) –> ( 1,2,3,5,7 )

Dördüncü Geçiş ( Fourth Past )

( 1,2,3,5,7 ) –> ( 1,2,3,5,7 )

( 1,2,3,5,7 ) –> ( 1,2,3,5,7 )

( 1,2,3,5,7 ) –> ( 1,2,3,5,7 )

( 1,2,3,5,7 ) –> ( 1,2,3,5,7 )

Bu algoritma en kötü ihtimal olarak 4 past halini aldı. Çünkü en küçük sayılardan 2.si dizinin en sonundaydı. Bu yüzden 4 past sayısına kadar çıktık.

Bu dizinin en iyi ihtimali: ( 1,2,3,5,7 ) . Eğer bu şekilde dizi verilseydi sadece 1 past dönecekti.

Bu dizinin en kötü ihtimali : ( 7,5,3,2,1 ) Bu şekilde 5 past dönecekti ve işlem çok daha uzun bir süre alacaktı.

C# Örneği:

static void BubbleSort<T>(IList<T> list) where T : IComparable<T>
{
for (int i = list.Count – 1; i > 0; i–)
{
for (int j = 0; j < i; j++)
{
IComparable current = list[j];
IComparable next = list[j + 1];
if (current.CompareTo(next) > 0)
{
list[j] = next;
list[j + 1] = current;
}
}
}
}