Algorithms

SIRALAMA ALGORİTMALARI – Kabarcık (Bubble Sort) Sıralaması

Bu makalemde sizlere “Kabarcık(Bubble Sort) Sıralaması” algoritmasından bahsedeceğim. Öncelikle algoritmanın tanımını yaptıktan sonra adım adım bir senaryo uygulayacağız. Makalenin sonunda da örnek kod parçacığını göreceksiniz.

Algoritma Hakkında

Temel olan, karışık düzende verilmiş bir dizide   elemanlar içerisinde ilerlerken komşu iki elemanın birbiri ile yer değiştirmesidir. Her adımda komşu iki eleman karşılaştırılır, gerekirse yer değiştirilir.  Bu algoritma iki döngü ile yapılır. İlk döngü elemanlar arasında geçişi, diğer döngü ise yerleştirme işlemi içindir. Bu algoritmanın zaman karmaşıklığı O(n²) dir.  Eğer dizide x kadar eleman sıralı değilse, zaman karmaşıklığı ise  O(xn) dir. Kodlaması oldukça basit olmasına rağmen etkin bir algoritma değildir. Belki geneli sıralı olan dizileri düzeltmek için ve eleman sayısı çok olmayan diziler için kullanılabilir.

Ayrıca bir kaydırma işlemi olması sebebi ile harici bir sıralama yapılırken çok fazla yazma ve okuma işlemi olacağından maliyetli bir algoritmadır. 

Bir dizide algoritmayı adım adım işletelim

Sıralanması nı istediğimiz dizi “9 4 5 3 2 1 8 6 7” olsun.

Dizimizin ilk hali 

Aşağıda adım adım işlemler sıralanmaktadır. her bir düngüde mavi kutucuklar karşılaştırılan sayıları göstermektedir. yeşil kutucuklar ise yer değiştirme sonrası halini göstermektedir. Kırmızı kutular ise yerini bulmuş elemanı gösterir.

1. Döngü

1. ADIM: 2. ADIM:
3. ADIM:
4. ADIM:
5. ADIM:
6. ADIM:
7. ADIM:
8. ADIM:

Sonucu :

2. Döngü

1. ADIM:
2. ADIM:
3. ADIM:
4. ADIM:
5. ADIM:
6. ADIM:
7. ADIM:
 

Sonucu :

3. Döngü

1. ADIM:
2. ADIM:
3. ADIM:
4. ADIM:
5. ADIM:
6. ADIM:

Sonucu :

4. Döngü

1. ADIM:
2. ADIM:
3. ADIM:
4. ADIM:
5. ADIM:
 

Sonucu :

5. Döngü

1. ADIM:
2. ADIM:
3. ADIM:
4. ADIM:

Sonucu :

6. Döngü

1. ADIM:
2. ADIM:
3. ADIM:
 

Sonucu :

7. Döngü

1. ADIM:
2. ADIM:

Sonucu :

8. Döngü

1. ADIM:

Sonucu :

private static void bubblesort(int[] array)
       {
           //eleman sayısı
           var n = array.Length;
           //Ana döngüyü oluşturuyoruz.
           //dizinin eleman sayısının 1 eksiği kadar döngü gerçekleşmeli.
           for (int dongu = 0; dongu < (n - 1); dongu++)
           {
               //her düngüde 1 eleman yerleşeceği için adım sayısı önceki döngüye göre 1 eksik olmalıdır.
               for (int i = 0; i < n - 1 - dongu; i++)
               {
                   var e1 = array[i];
                   var e2 = array[i + 1];
                   //sıralı ise bir sonraki adıma geç.
                   if (e1 <= e2)
                       continue;
                   //sıralı değilse yer değiştir.  
                   array[i] = e2;
                   array[i + 1] = e1;
               }
           }
       }

Örnek uygulamaya aşağıdaki link ile erişebilirsiniz.

https://github.com/ahmetozgunozcan/SortingAlgorithms

Leave a Comment