Bu algoritmanın en iyi, ortalama, ve en kötü çalışma performansı şöyledir:
Best Average Worst
Ω(n) θ(n^2) O(n^2)
75 25 40 80 60 15 30 sırasız listesini ele alalım. Amacımız bu listeyi küçükten büyüğe sıralamak. Bubble sort'da soldan sağa doğru tüm sayıları tararız gerekli swaplar ile en büyük sayıyı en sağa getiririz. Gözünüzün önüne öyle bir baloncuk getirin ki bu balon iki tane sayıyı içine katmış, bu iki sayıdan büyük olanı sağa sürüklüyor ,listenin sonuna kadar bu balon tüm sayıları ikişer ikişer içine katarak en sağa en büyük sayıyı getirmiş oluyor. Sonra en başa dönüp sıralanmamış liste üzerinde baloncuğumuz sıralama tamamlanana kadar sürekli gider gelir.
Yukarıda 7 tane sayı var. Bu sayılardan önce 1. ile 2. karşılaştırılır. Gerekliyse swap yapılır. Sonra 2. ile 3. , 3. ile 4. , 4. ile 5. , 5. ile 6. , 6. ile 7. kıyaslanır. Her kıyaslamadan sonra gerekliyse swap yapılır. En sona en büyük sayı gelmiş olur.
75 25 40 80 60 15 30 75 ile 25 'i karşılaştır.
25 75 40 80 60 15 30 75 > 25 olduğu için swap ettik.
25 75 40 80 60 15 30 75 ile 40'ı karşılaştır.
25 40 75 80 60 15 30 75 > 40 olduğu için swap ettik.
25 40 75 80 60 15 30 75 ile 80'i kıyasla.
25 40 75 80 60 15 30 75 <80 olduğu için swap yapmadık.
25 40 75 80 60 15 30 80 ile 60'i kıyasla.
25 40 75 60 80 15 30 80 > 60 olduğu için swap yapmadık.
25 40 75 60 80 15 30 80 ile 15'i kıyasla.
25 40 75 60 15 80 30 80 > 15 olduğu için swap ettik.
25 40 75 60 15 80 30 80 ile 30'u kıyasla.
25 40 75 60 15 30 80 80 > 30 olduğu için swap ettik. 80'in yerini sabitledik.
En büyük sayıyı bulup en sağa getirdik. Şimdi de kalan sayılar içindeki en büyük sayıyı aynı yöntemle bulup 80'in soluna getirelim.
25 40 75 60 15 30 80
25 40 75 60 15 30 80
25 40 75 60 15 30 80
25 40 75 60 15 30 80
25 40 75 60 15 30 80
25 40 60 75 15 30 80
25 40 60 75 15 30 80
25 40 60 15 75 30 80
25 40 60 15 75 30 80
25 40 60 15 30 75 80
İkinci en büyük sayıyı(75) da bulup uygun yere getirdik. Şu an elimizde 2 elemanlı sıralı bir liste var: 75 80
Şimdi de kalan sayılar içindeki en büyük sayıyı gene aynı metotla bulup 75'in soluna getirelim.
25 40 60 15 30 75 80
25 40 60 15 30 75 80
25 40 60 15 30 75 80
25 40 60 15 30 75 80
25 40 60 15 30 75 80
25 40 15 60 30 75 80
25 40 15 60 30 75 80
25 40 15 30 60 75 80
Üçüncü en büyük sayıyı(60) da bulup uygun yere getirdik. Şu an elimizde 3 elemanlı sıralı bir liste var:
60 75 80
Şimdi de kalan sayılar içindeki en büyük sayıyı gene aynı metotla bulup 60'ın soluna getirelim.
25 40 15 30 60 75 80
25 40 15 30 60 75 80
25 40 15 30 60 75 80
25 15 40 30 60 75 80
25 15 40 30 60 75 80
25 15 30 40 60 75 80
Dördüncü en büyük sayıyı(40) da bulup uygun yere getirdik. Şu an elimizde 4 elemanlı sıralı bir liste var:
40 60 75 80
Şimdi de kalan sayılar içindeki en büyük sayıyı gene aynı metotla bulup 40'ın soluna getirelim.
25 15 30 40 60 75 80
15 25 30 40 60 75 80
15 25 30 40 60 75 80
15 25 30 40 60 75 80
Beşinci en büyük sayıyı(30) da bulup uygun yere getirdik. Şu an elimizde 5 elemanlı sıralı bir liste var:
30 40 60 75 80
Şimdi de kalan sayılar içindeki en büyük sayıyı gene aynı metotla bulup 30'un soluna getirelim.
15 25 30 40 60 75 80
15 25 30 40 60 75 80
Altıncı en büyük sayıyı(25) da bulup uygun yere getirdik. Şu an elimizde 6 elemanlı sıralı bir liste var:
25 30 40 60 75 80
Şimdi de kalan sayılar içindeki en büyük sayıyı gene aynı metotla bulup 25'in soluna getirelim.
15 25 30 40 60 75 80
15 25 30 40 60 75 80
Kalan sayıyı(15) da 25'in soluna ekledik. Böylece tüm sayıları küçükten büyüğe sıraladık:
15 25 30 40 60 75 80
Bu sıralamayı yaparken kullandığımız algoritmanın adı BUBBLE SORT'dur.
Hiç yorum yok:
Yorum Gönder