 |
| Bubble Sort Time Complexity |
Bubble Sort zaman karmaşıklığı nedir sorusunun 3 ayrı cevabı mevcut. Çünkü zaman karmaşıklığının 3 kriteri var. Bunlar Worst Case (en kötü durum), Best Case (en iyi durum) ve Avarage Case (Ortalama Durum).
Öncelikli olarak algoritmayı incelediğimizde karşımıza temel olarak for döngüsü içerisinde for döngüsü çıkmaktadır. Yani iç içe loop döngüsüdür. Üstteki for döngüsü n eleman sayısı için çalışır. Alttaki for döngüsü ise n-1 eleman sayısı için çalışmaktadır. Yani bubble sort büyük O notasyonu n*(n-1)'den n^2 gelir. (aslında karşımıza n^2-n ifadesi gelir. Ancak biz üssü büyük olan ifadeyi hesaba katarız)
Peki en kötü durum yani Bubble Sort Worst Case senaryosunda ne olur? En kötü durumda dizinin en küçük elemanı en sondadır. Böyle bir durum yaşandığında n elemanlı dizide n geçiş yaşanır ve her geçişte n-1 adet adım gerçekleşir. Bu da bize n^2-n ifadesini verir. Bu da N^2 demektir. Yani bubble sort en kötü durum senaryosu N^2 dir.
Bubble Sort Avarage Case için de durum aynıdır. yani N^2 dir. Algoritmanın pek performanslı olmamasının nedeni de budur. Yani ortalama durumu ile en kötü durumu neredeyse aynıdır. Eleman sayısı fazla olan diziler için kesinlikle tercih edilmemelidir.
Bubble Sort en iyi durum senaryosu ise dizinin zaten sıralı olduğu haldir. Bu durumda 1 iterasyon yapılır yani hiç swap yapımaz. Hiç swap işlemi yapılmadıysa 1. geçişin 1. adımından sonra döngüden çıkılır. Bu en iyi durumdur. Bubble Sort best case 1'dir.
Bubble Sort Zaman Karmaşıklığı Hesabı Nasıl Yapılır
Eğer size direkt olarak böyle bir soru sorulursa, her adımda birer eleman eksilteceğinizi belirterek bu şekilde bir hesaplamanın yapılacağını söyleyebilirsiniz. Yani;
(n-1)+(n-2)+(n-3)+....+2+1 = x dersek
x = [n*(n-1)]/2
O(n^2) olarak bulunur.
Bubble Sort Algoritması Yorumu
Eğer size hocanız Bubble Sort algoritmasını yorumlamanızı isterse O(n^2) olduğunu, avarage case'inin, Worst Case ile aynı olduğundan (n^2) büyük elemanlı diziler için uygun olmadığını belirtebilirsiniz.
Zaman Karmaşıklığı Nedir Diye Soruyorsanız İlgili Makalemizi Okuyabilirsiniz...
Etiketler: Algoritma Karmaşıklığı, Algoritmalar, Bubble Sort, Bubble Sort Avarage Case, Bubble Sort best case, Bubble Sort Worst Case, sıralama algoritmaları
