Birleştirme Sıralama(Merge Sort) Algoritması ve Kodu

Merhaba arkadaşlar, daha önce Kabarcık sıralama ve Seçmeli sıralamaya bakmıştık. Bu yazımda da Birleştirme sıralamaya bakacağız.

Aşağıdaki videoyu izlerseniz algoritmanın çalışma mantığını daha iyi anlayabilirsiniz. Daha sonra anlatıp koduna geçeceğim.

Birleştirme Sıralama Algoritması

Algoritma diziyi sürekli ikiye bölme üzerine kuruludur. En son iki eleman kaldığında o ikisi arasında sıralama yapar ve sıralamaya göre geri gönderir. Sonra 4 eleman arasında sıralama yapar ve geri gönderir. Daha sonra 8 16 32 diye gider bu. Basit bir algoritmadır. Çalışma hızı olarak baktığımızda T(n)=O(n lg n)’dır. Kabarcık ve Seçme sıralamaya göre daha hızlı çalışmaktadır.

ve Kodu

Aşağıdaki kod C# dili ile yazılmıştır. Genel olarak incelenirse Java diline çok rahat uyarlanabilmektedir.

static void Main(string[] args)
        {
            //dizimizi tanımlıyoruz
            int[] dizi = MergeSort(new int[] { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 });


            for (int i = 0; i < dizi.Length; i++) //dizimiz sıralandıktan sonra elemanlarını dönüyoruz
            {
                Console.Write(dizi[i] + " ");
            }

            Console.ReadLine();
        }

        //MergeSort 
        static int[] MergeSort(int[] d)
        {
            if (d.Length <= 1)
                return d; //1 eleman zaten kıyaslanacak bir şey yok yukarı yolluyoruz.

            int i = 0;
            int bol = d.Length / 2; //ikiye bölüyoruz

            int[] sol = new int[bol]; //sol kısıma ilk yarısını
            int[] sag = new int[d.Length - bol]; //sağ kısma diğer yarısını atıyoruz



            for (i = 0; i < bol; i++)
            {
                sol[i] = d[i]; // sol diziyi dolduruyoruz
            }

            int k = 0;
            for (i = bol; i < d.Length; i++)
            {
                sag[k] = d[i]; //sağ diziyi dolduruyoruz
                k++;
            }

            sol = MergeSort(sol); //kalan diziyi tekrar yolluyoruz ikiye bölünsün diye
            sag = MergeSort(sag); //kalan diziyi tekrar yolluyoruz ikiye bölünsün diye

            return birlestir(sol, sag); // daha sonra birleştire gidiyoruz.
        }

        static int[] birlestir(int[] sol, int[] sag)
        {

            int[] a = new int[sol.Length + sag.Length]; // a dizisi oluşturduk.

            int i = 0, j = 0, k = 0;

            while (j < sol.Length && i < sag.Length)
                a[k++] = (sag[i] > sol[j]) ? sag[i++] : sol[j++];//sağ soldan büyük ise sağın bir sonrakine bak
            //değilse solun bir sonraki indisine git ve a dizisine yaz.

            while (i < sag.Length)
                a[k++] = sag[i++]; //sağ kısım dönene kadar a dizisine sağı at

            while (j < sol.Length) //sol kısım tamamen bitene kadar a dizisine at
                a[k++] = sol[j++];

            return a; // en son a dizisini gönder diyoruz..
        }

Gereklil açıklamaları kod üzerinde yaptım. Yukarıdaki kodda büyükten küçüğe sıralama yaptık. Eğer kod içerisindeki büyüktür kısmını küçüktür yaparsanız küçükten büyüğe sıralayabilirsiniz. Anlamadığınız kısımları yorum yaparak sorabilirsiniz. Umarım faydalı olmuştur.

Bunlara Göz Atmak İsteyebilirsiniz

Bir yanıt yazın

E-posta adresiniz yayınlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir