Herkese merhaba, bu yazımda sizlere sıralama algoritmaları arasında yer alan Bubble Sort algoritmasından bahsedeceğim. Bubble sort karşılaştırma temelli basit bir sıralama algoritmasıdır. Sıralanmamış bir veri dizisine sahip olduğumuzu düşünelim. İlk elemanından başlayarak sürekli olarak bir sonraki elemana geçiyor ve her seferinde bir sağdaki eleman ile karşılaştırma yapıyoruz. Eğer sağdaki elemanımız soldakinden küçük ise elemanlar arasında swap işlemi gerçekleştiriyoruz. Bu işlemi sürekli tekrar ediyor ve en sonunda dizimizi sıralamış oluyoruz.
Bu algoritma da sürekli büyük olan sayı ile küçük olan sayı arasında swap işlemi gerçekleştiğinden ötürü ve algoritmanın yapısı sayesinde büyük olan elemanı hep en sağa doğru iteliyoruz. Sayı dizimizi sıralamak için gerçekleştireceğimiz ilk taramada o an dizide bulunan en büyük eleman dizinin en sonuna geliyor olacak. Bir sonraki taramada sıralanmamışların en büyük elemanı dizinin en sondan bir önceki kısımda yer alacak. Tabii ki böyle yazarak ilerlediğimiz zaman bazen kafada bir şeyler oluşmayabiliyor yada yarım kalıyor. Bunun için bir örnek gerçekleştirelim. Bir adet sayı dizimiz olsun.
[1,14,3,22,7,15]
Bu sayı dizimizi Bubble sort algoritması ile sıralayacağız. İlk tarama işlemini adım adım anlatırken sonraki tarama adımlarını hızlıca geçeceğim. Dizinin en büyük elamanının karşılaştırma adımlarını gerçekleştirirken değişen konumuna ve gerçekleştirdikten sonraki konumuna dikkat edelim.
1.Karşılaştırma
Birinci elemanımız 1 ve ikinci elemanımız 14 arasında karşılaştırma işlemi yapıyoruz. 1 sayısı 14 sayısından küçük olduğunu fark ediyor ve devam ediyoruz.
2.Karşılaştırma
İkinci elemanımız ile aynı şekilde üçüncü elemanımız 3 arasında karşılaştırma yapıyoruz ve 14 sayısı 3 sayısından büyük olduğundan swap işlemi gerçekleştiriyoruz.
[1,3,14,22,7,15]
(Swap sonrası)
3.Karşılaştırma
Üçüncü (14) elemanımız ve dördüncü (22) elamanlarımız arasında swap işlemi gerçekleşmeyecek.
4.Karşılaştırma
Dördüncü elamanımız 22 ile beşinci elamanımız 7 arasında bir swap işlemi gerçekleştiriyoruz.
[1,3,14,7,22,15]
(Swap sonrası)
5.Karşılaştırma
Beşinci elamanımız 22 ile altıncı elamanımız 15 arasında bir swap işlemi gerçekleştiriyoruz.
[1,3,14,7,15,22]
(Swap sonrası)
Evet şu anda ilk tarama işlemimizi gerçekleştirdik. Dizimizin en büyük elamanını en sağa atmış olduk.
2.Tarama
[1,3,7,14,15,22]
(2. Tarama Sonrası)
İkinci tarama işleminde gerekli tüm karşılaştırmaları baştan başlayarak gerçekleştirdik. Sadece üçüncü (14) ve dördüncü (7) elamanlar arasında bir karşılaştırma yapıldı. Böylece dizimiz sıralanmış oldu.
Notlar
Yaptığım bazı araştırmalarda Bubble Sort ile n sayıdaki bir dizi için her taramada dizinin tüm elamanlarında karşılaştırmalar yapıldığını fark ettim. Buna karşılık diğer araştırmalarımda ise Her yapılan taramada dizinin sıralanmamış en buyuk elamanının dizinin sağ tarafında kendi yerine yerleştirileceğinden ötürü sıralanmış elemanlar ile tekrardan karşılaştırma yapılmasının gereksiz olduğu yönünde bilgiler edindim.
Bubble sort algoritmasının basit bir yapıda olduğunu gözlemlemişsinizdir. Lakin bu algoritma yapısı gereği büyük boyutlu dizilerde yavaş çalışır.
Okuduğunuz için teşekkür ederim, bir sonraki yazıda görüşmek üzere. Kendinize iyi bakın 🙂
Örnek Java Kodu için tıklayınız.