Merhabalar,
Yeni bir yazı dizisi ile karşınızdayım. Daha önce hiç sıralama algoritmalarından bahsetmediğini fark ettim ve bu diziye başlamak istedim. Yalnızca bir quick sort yazımız olmuştu şimdi bu serinin başlangıcı niteliğinde bir yazı bubble sort ile karşınızdayım.
Sıralama ve arama tekniklerinden pek çok programda yararlanılmaktadır. Günlük yaşamımızda elemanların sıralı tutulduğu listeler yaygın olarak kullanılmaktadır. Sıralama, sıralanacak elemanlar bellekte ise içsel kayıtların bazıları ikincil bellek ortamında ise dışsal sıralama olarak adlandırılır.
Kabarcık Sıralama (Bubble Sort) Algoritması
Dizinin elemanları üzerinden ilk elemandan başlayarak ve her geçişte sadece yan yana bulunan iki eleman arasında sıralama yapılır.
Dizinin başından sonuna kadar tüm elemanlar bir kez işleme tabi tutulduğunda dizinin son elemanı (küçükten büyüğe sıralanırsa) en büyük elemanı haline gelecektir.
Bir sonraki tarama ise bu en sağdaki eleman dışarıda bırakılarak gerçekleştirilmektedir. Bu dışarıda bırakma işlemi de dış döngüdeki sayaç değişkeninin değeri her işletimde bir azaltılmasıyla sağlanmaktadır. Sayaç değişkeninin değeri 1 değerine ulaştığında ise dizinin solunda kalan son iki eleman da sıralanmakta ve sıralama işlemi tamamlanmaktadır.
Bubble sort, sıralama teknikleri içinde anlaşılması ve programlanması kolay olmasına rağmen etkinliği en az olan algoritmadır. (n elemanlı x dizisi için..)
Örnek
• 9,5,8,3,1 rakamlarının azalan şekilde sıralanmasını kabarcık algoritması ile gerçekleştirelim.
Birinci tur tamamlandığında en büyük eleman olan 9 en sona yerleştirilmiş olur ve bir daha karşılaştırmaya gerek kalmaz.
Kabarcık sıralama (bubble sort) algoritmasının kodunu incelersek ise:
//En büyük elemanı En sona taşımak için public static void bubbleSort(int[] x) { int n = x.Length; int tut,j,i; bool sirali = false; for (i=0;(i<n-1)&&!sirali;i++) { sirali=true; for(j=0;j<n-i-1;j++) { if(x[j]>x[j+1] { tut=x[j]; x[j]=x[j+1]; x[j+1]=tut; sirali=false; } } } }
Bubble Sort Algoritma Analizi
•Analizi kolaydır.
•(n-1) iterasyon ve her iterasyonda (n-1) karşılaştırma bulunur(Optimize edilmemiş hali için).
•Toplamda karşlılaştırma sayısı : (n-1)*(n-1) = n²+2n+1 = O(n²) olur.
•İterasyon i’de , (n-i) kadar karşılaştırma yapılacaktır. Buna göre ortalama iterasyon sayısı k, O(k.n) olduğundan O(n²).
Performans
Kabarcık algoritması ortalama N²/2 karşılaştırma ve N²/2 yer değiştirme işlemi gerçekleştirir.
En İyi Durum: O(n) [Best Case]
Eğer;
-Dizi artan sıralı ise
-Sıfır yer değiştirme olur: 0 >> O(1)
-Anahtarların karşılaştırılması : (n-1) >> O(n)
En Kötü Durum: O(n²) [Worst Case]
Eğer;
-Dizi tersten sıralı ise
-Dış döngü n-1 kez çalışır.
-Yer değiştirme: 3*(1+2+3+….+n-1)= 3*n*(n-1)/2 = O(n²)
-Karşılaştırma : (1+2+3+…..+n-1)=n*(n-1)/2= O(n²)
Ortalama Durum: O(n²) [Average Case]
Bu yazımızda da Kabarcık Sıralama (Bubble Sort) algoritması ile ilgili detay ve analiz yaptık. Eğer anlamadığınız ya da eksik gördüğünüz yerler var ise bana yorumlar aracılığı ile bildirebilirsiniz.
Teşekkürler!