Sekkaşı’nın Bayırı

Algoritma Adı: Birleştirmeli Sıralama Algoritması (Merge Sort)
Algoritma Türü: Sıralama Algoritması
Açıklama: Parçala yönet mantığıyla geliştirilmiş özyinelemeli (recursive) sıralama algoritmasıdır. Temel olarak üç aşamadan oluşur. Algoritma kendine verilen diziye ikiye böler. Birinci ve ikinci parçaların sıralanmasını sağlar. Son olarak da sıralı iki altdiziyi birleştirir. Örnek olarak 6 elemanlı 6 5 4 3 2 1 dizisini sıralayalım.

1. Adım : Dizi 6 5 4 ve 3 2 1 olmak üzere ikik alt diziye ayrılır.
2. Adım : 6 5 4 alt dizisi 6 ve 5 4 olmak üzere ikiye ayrılır.
3. Adım : 6 tek elemanlı olduğu için sıralanmış kabul edilir.
4. Adım : 5 4 dizisi 5 ve 4 olmak üzere ikiye ayrılır.
5. Adım : 5 ve 4 tek elemanlı olduklarından sıralanmış kabul edilir.
6. Adım : 5 ve 4 birleştirilir. Sıralama 4 5 şeklinde olur.
7. Adım : 6 ve 4 5 dizisi birleştirilir. Sıralama 4 5 6 şeklinde olur. İlk dizimizin ilk alt dizisi sıralanmış olur. 2
8. Adım : 3 2 1 dizisi 3 ve 2 1 olarak ikiye ayrılır.
9. Adım : 3 tek elemanlı olduğundan sıralı kabul edilir.
10. Adım : 2 1 dizisi 2 ve 1 olmak üzere ikiye ayrılır.
11. Adım : 2 ve 1 tek elemanlı olduklarından sıralanmış kabul edilir.
12. Adım : 2 ve 1 birleştirilir. Sıralama 1 2 olur.
13. Adım : 3 ve 2 1 dizileri birleştirilir. Sıralama 1 2 3 şeklinde olur. İlk dizimizin ikinci alt dizisi de sıralanmış olur.
14. Adım : 4 5 6 ve 1 2 3 alt dizileri birleştirilerek 1 2 3 4 5 6 sıralı dizisi oluşur. Algoritma sonlanır.

Algoritma Java Kodu :

int[] mergeSort(int[] siralanacakArray) {

        //eğer sıralanacak dizi uzunluğu 2'den küçükse
        //dizi sıralı sayılır
        if (siralanacakArray.length < 2) {
            return siralanacakArray;
        }

        //ikiye bölünen dizi boyutlarını hesaplıyoruz
        int ilkArrayBoyutu = siralanacakArray.length / 2;
        int ikinciArrayBoyutu = siralanacakArray.length - ilkArrayBoyutu;

        //iki alt diziyi ilklendiriyoruz
        int[] ilkArray = new int[ilkArrayBoyutu];
        int[] ikinciArray = new int[ikinciArrayBoyutu];

        //dizinin ilk parçasını bölüyoruz
        for (int i = 0; i < ilkArrayBoyutu; i++) {
            ilkArray[i] = siralanacakArray[i];
        }

        //Dizinin geri kalanını ikinci diziye atıyoruz
        int j = 0;
        for (int k = ilkArrayBoyutu; k < siralanacakArray.length && j < ikinciArrayBoyutu; k++, j++) {
            ikinciArray[j] = siralanacakArray[k];
        }

        //Böldüğümüz ilk diziyi sıralıyoruz
        int[] siraliIlkArray = mergeSort(ilkArray);

        //Böldüğümüz ikinci diziyi sıralıyoruz
        int[] siraliIkinciArray = mergeSort(ikinciArray);

        int m = 0, n = 0, y = 0;

        //Sıralı iki diziyi tekrar birleştiriyoruz.
        //Sırasıyla bütün elemanları karşılaştırarak küçük olanı önce
        //olmak kaydıyla ilk dizide birleştiriyoruz
        while (m < ilkArrayBoyutu && n < ikinciArrayBoyutu) {
            if (siraliIlkArray[m] <= siraliIkinciArray[n]) {
                siralanacakArray[y] = siraliIlkArray[m];
                m++;
                y++;
            } else if (siraliIlkArray[m] > siraliIkinciArray[n]) {
                siralanacakArray[y] = siraliIkinciArray[n];
                n++;
                y++;
            }
        }

        //Eğer ilk dizide eleman kalmışsa bunları listenin sonuna ekliyoruz
        while (m < ilkArrayBoyutu) {
            siralanacakArray[y] = siraliIlkArray[m];
            y++;
            m++;
        }

        //Eğer ikinci dizide eleman kalmışsa bunları listenin sonuna ekliyoruz
        while (n < ikinciArrayBoyutu) {
            siralanacakArray[y] = siraliIkinciArray[n];
            y++;
            n++;
        }

        //Sıralanmış diziyi dışarı veriyoruz.
        return siralanacakArray;
    }

İlgili Yazılar:

1. Eklemeli Sıralama (Insertion Sort) Algoritma Appleti Algoritma Adı: Eklemeli Sıralama Algoritması(Insertion Sort) Algoritma Türü: Sıralama Algoritması...
2. Seçim Sıralama(Selection Sort) Algoritma Appleti Algoritma Adı: Seçim Sıralama Algoritması(Selection Sort) Algoritma Türü: Sıralama Algoritması...
3. Kabarcık Sıralama (Bubble Sort ) Algoritma Appleti Algoritma Adı: Kabarcık Sıralama Algoritması (Bubble Sort) Algoritma Türü: Sıralama...