SIRALAMA ALGORİTMALARI Birleşmeli Sıralama (Merge Sort)

Bu makalemde sizlere “Birleşmeli Sıralama (Merge Sort)” 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.

Merge sort böl ve yönet yaklaşımına dayanır. Sürekli dizinin ortadan ikiye bölünmesi ile yürütülür. Bu davranışı rekürsif tasarlanabileceğini gösterir. Her parçalama işlemi ile oluşan kümeler aynı yöntem ile parçalanır. Yani alt kümede 1 adet eleman kalıncaya kadar 2 adet parçalara bölünür. Bir adet eleman kalınca da rekürsif dönüşler başlar.  Geriye dönüşlerde alt küme elemanlarının sıralanması işlemi yapılır. Her geri dönüşte alt küme üst küme ile birleştirilir. Algoritma adını bu birleştirme işleminden almıştır.

Basit bir kod parçası ile göstermek gerekirse;

bol(Dizi[],sol,sag)
{
   if(sol<sag)                       
   {
      int orta=(sol+sag)/2;
      bol(D,sol,orta);
      bol(D,orta+1,sag);
      birlestir(D,sol,orta,sag);
   }
}

Yukarıdaki kod örneğine göre algoritma basit gibi görünse de geçekleştirilmesi diğer sıralama algoritmalarına göre daha karmaşıktır.

Sıralanmak istenen elemanlar bir dizi ile tutuluyorsa parçalamak kolay, birleştirilmesi zordur. Bağlı listede tutuluyorsa parçalanması zor, birleştirilmesi kolaydır. Dizi üzerinde tutulan parçaların birleştirilmesi için ek dizi alanlarına ihtiyaç vardır. Bağlı listede de orta elemana doğrudan erişim olmadığı için parçalamada zaman maliyeti fazla olur. Eğer eleman sayısı biliniyorsa N/2 çevrim yapılır.

Dizi bazlı veri setinde;

Heap Sort algoritması Merge Sort algoritmasına göre daha az bellek kullanır ve daha hızlı çalışır. Aynı şekilde bellek tabanlı dizi kullanımında Quick Sort algoritması daha hızlı çalışır.

Bağlı listelerde;

Bağlı listelerde sıralama yapılmak istenirse Merge Sort algoritması seçilebilir. Çünkü performans açısından daha iyi olabilmektedir. Heap Sort algoritmasının kullanımı imkansızdır. Quick Sort için ise performansın düşmesin beklenir.

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.

class MergeSort
    {
        int[] dizi;
        public MergeSort(int[] dizi)
        {
            this.dizi = dizi;
        }

        public int[] Sort()
        {
            Sort(0, dizi.Length - 1);

            return dizi;
        }

        private void Sort(int sol, int sag)
        {
            if (sol < sag)//Eleman sayısı 1 den büyük ise
            {

                //orta indexi bul
                int orta = (sol + sag) / 2;

                //Sol kümeyi böl sırala
                Sort(sol, orta);

                //Sağ kümeyi böl sırala
                Sort(orta + 1, sag);

                Birlestir(sol, orta, sag);//Bölüp sıraladıklarını birleştir.
            }
        }

        private void Birlestir(int sol, int orta, int sag)
        {
            int solElemanSayisi = orta - sol + 1;
            int sagElemanSayisi = sag - orta;

            int[] SOL = new int[solElemanSayisi];
            int[] SAG = new int[sagElemanSayisi];

            for (int t = 0; t < solElemanSayisi; ++t)
                SOL[t] = dizi[sol + t];

            for (int z = 0; z < sagElemanSayisi; ++z)
                SAG[z] = dizi[orta + 1 + z];

            int i = 0, j = 0;
            int k = sol;
            while (i < solElemanSayisi && j < sagElemanSayisi)
            {
                //Soldaki sayi sağdakinden küçük eşitse diziye önce onu koy.
                if (SOL[i] <= SAG[j])
                {
                    dizi[k] = SOL[i];
                    i++;
                }

                //Sağdaki sayi soldakinden küçük eşitse diziye önce onu koy.
                else
                {
                    dizi[k] = SAG[j];
                    j++;
                }
                k++;
            }

            //SOL da kalanları diziye ekle
            while (i < solElemanSayisi)
            {
                dizi[k] = SOL[i];
                i++;
                k++;
            }

            //SAĞ da kalanları diziye ekle
            while (j < sagElemanSayisi)
            {
                dizi[k] = SAG[j];
                j++;
                k++;
            }

        }
    }

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

https://github.com/ahmetozgunozcan/SortingAlgorithms