Merge Sort

"Merge sort" (birləşmə ilə sıralama) rekursiv, "böl və idarə et" (divide-and-conquer) prinsipinə əsaslanan sıralama alqoritmidir; o, sabit performansı və stabil sıralama xüsusiyyətləri ilə tanınır. Əsas ideya massivi davamlı olaraq iki hissəyə bölmək, hər hissəni ayrı-ayrılıqda sıralamaq və sonra sıralanmış hissələri bir-biri ilə birləşdirməkdən ibarətdir.

Addımlar

1. Böl (Divide): Əgər massiv bir və ya sıfır elementdən ibarətdirrsə, o, sıralanmış hesab olunur. Əks halda, massivi iki hissəyə bölün.

2. Həll et (Conquer): Massivin hər iki hissəsini rekursiv olaraq sıralayın.

3. Birləşdir (Merge): Tək bir sıralanmış massiv yaratmaq üçün sıralanmış hissələri birləşdirin. Bu addım həlledicidir və burada hər iki hissə sıralı ardıcıllıqla bir araya gətirilir.

C++ Tətbiqi

merge (birləşdirmə) metodu ilə başlayın. Bu metod tam ədədlərdən ibarət bir massiv və sol indeksi, orta nöqtəni, həmçinin sağ indeksi təmsil edən üç tam ədəd qəbul edir. Sol massivin uzunluğunu (n1) və sağ massivin uzunluğunu (n2) hesablayın. Daha sonra sol və sağ hissələr üçün müvəqqəti massivlər yaradın.

static void merge(int arr[], int left, int mid, int right) {
    // Sol və sağ hissələrin ölçülərini hesablayırıq
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Müvəqqəti massivlərin yaradılması
    int L[n1], R[n2];

    // Məlumatların müvəqqəti massivlərə kopyalanması
    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    
    for (int j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];
}

Birləşdirmə Mərhələsi

İndi ki, orijinal massiv müvəqqəti massivlərə bölünüb, elementləri yenidən ardıcıllıqla orijinal massivə birləşdirin. i, j və kindeks dəyişənlərini yaradın. Onlar müvafiq olaraq sol massivdəki (i), sağ massivdəki (j) və orijinal massivdəki (k) mövqelərə işarə edəcək.

Həm i, həm də j öz massivlərinin sonuna çatmadığı müddətcə, müvəqqəti sol və sağ massivlərdəki elementləri müqayisə edin. Əgər müvəqqəti sol massivdəki element müvəqqəti sağ massivdəki elementdən kiçik və ya ona bərabərdirsə, sol massivdəki elementi orijinal massivə yerləşdirin. Əks halda, müvəqqəti sağ massivdəki elementi orijinal massivə yerləşdirin. Dövr yenidən təkrarlanmazdan əvvəl k indeksini artırın.

static void merge(int arr[], int left, int mid, int right) {
    // Müvəqqəti massivlərin ölçülərini hesablayırıq
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Müvəqqəti massivlər (Temporary arrays)
    int L[n1], R[n2];

    // Məlumatların müvəqqəti massivlərə kopyalanması
    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    
    for (int j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];

    // Birləşdirmə (Merge) prosesi
    int i = 0;    // Sol massiv üçün indeks
    int j = 0;    // Sağ massiv üçün indeks
    int k = left; // Orijinal massiv üçün indeks

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
}

Qalıq Elementlərin Köçürülməsi

Sol və sağ massivlərdə hələ birləşdirilməmiş qalıq məlumatlar ola bilər. Bu, i və ya j indekslərindən birinin digərindən əvvəl öz massivinin sonuna çatdığı halda baş verə bilər. Müvəqqəti massivlərdə qalan hər hansı məlumatı yenidən orijinal massivə kopyalayın.

static void merge(int arr[], int left, int mid, int right) {
    // Müvəqqəti massivlərin ölçülərini hesablayırıq
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Müvəqqəti massivlər (Temporary arrays)
    int L[n1], R[n2];

    // Məlumatların müvəqqəti massivlərə kopyalanması
    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    
    for (int j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];

    // Birləşdirmə (Merge) prosesi
    int i = 0;    // Sol massiv üçün indeks
    int j = 0;    // Sağ massiv üçün indeks
    int k = left; // Orijinal massiv üçün indeks

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Əgər L[] massivində qalan elementlər varsa, onları kopyalayırıq
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Əgər R[] massivində qalan elementlər varsa, onları kopyalayırıq
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

mergeSort Metodunun Yaradılması

Növbəti addım olaraq, tam ədədlərdən ibarət bir massiv, sol indeksi təmsil edən tam ədəd və sağ indeksi təmsil edən tam ədəd qəbul edən mergeSort metodunu yaradın. Bu metod geriyə heç nə qaytarmamalıdır. Bu, rekursiv bir alqoritmdir, ona görə də biz baza halını (base case) təyin etməliyik. Sol indeks sağ indeksdən kiçik olduğu müddətcə, orta nöqtəni hesablayın, sol hissəni sıralayın, sağ hissəni sıralayın və sonra hər iki hissəni birləşdirin.

static void mergeSort(int arr[], int left, int right) {
    // Baza halı: massivdə birdən çox element olduğu müddətcə davam edir
    if (left < right) {
        // Orta nöqtəni hesablayırıq
        int mid = (left + right) / 2;

        // Hissələri rekursiv olaraq sıralayırıq (Sort the halves)
        mergeSort(arr, left, mid);      // Sol hissə
        mergeSort(arr, mid + 1, right); // Sağ hissə

        // Sıralanmış hissələri birləşdiririk (Merge the sorted halves)
        merge(arr, left, mid, right);
    }
}

Kod

Sonda kodunuz bu şəkildə olmalıdır:

class MergeSort {
public:
    // İki alt massivi birləşdirən funksiya:
    // Birinci alt massiv: arr[left..mid]
    // İkinci alt massiv: arr[mid+1..right]
    static void merge(int arr[], int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Müvəqqəti massivlərin yaradılması
        int L[n1], R[n2];

        // Məlumatların L[] və R[] müvəqqəti massivlərinə kopyalanması
        for (int i = 0; i < n1; ++i)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[mid + 1 + j];

        // Müvəqqəti massivlərin yenidən arr[left..right] daxilində birləşdirilməsi
        int i = 0, j = 0; // Alt massivlərin ilkin indeksləri
        int k = left;     // Birləşmiş massivin ilkin indeksi

        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // L[] massivində qalıq elementlər varsa, kopyalanır
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // R[] massivində qalıq elementlər varsa, kopyalanır
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Sıralamanı həyata keçirən əsas funksiya
    static void mergeSort(int arr[], int left, int right) {
        if (left < right) {
            // (left+right)/2 ilə eynidir, lakin böyük rəqəmlərdə aşmanın qarşısını alır
            int mid = left + (right - left) / 2;

            // Birinci və ikinci hissələri sıralayırıq
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // Sıralanmış hissələri birləşdiririk
            merge(arr, left, mid, right);
        }
    }
};

main Metodu və Nəticə

main metodunda kodunuza aşağıdakı sıralanmamış massiv təqdim olunacaq: {12, 11, 13, 5, 6, 7}

Kodunuzun istehsal etməli olduğu nəticə: Sıralanmış Massiv: 5 6 7 11 12 13

"Merge sort" alqoritmləri öz proqnozlaşdırıla bilən və sabit performansı ilə fərqlənir. Bu, onları bir çox tətbiqlərdə populyar seçimə çevirir. Bütün hallarda (ən yaxşı, orta və ən pis) zaman mürəkkəbliyi eynidir. Birləşdirmə mərhələsində istifadə olunan müvəqqəti massivlərə görə əlavə yaddaş (space overhead) tələb etsə də, stabil və ardıcıl performansı onu bir çox sahələrdə etibarlı seçim edir.

Merge Sort-un Analizi

Merge Sort: Detallı Analiz

"Merge sort" alqoritmləri öz proqnozlaşdırıla bilən performansına görə populyardır. Lakin bu, onun hər zaman istifadə üçün ən yaxşı sıralama alqoritmi olduğu mənasına gəlmir. "Merge sort"un optimal həll yolu sayılmadığı bir neçə hal mövcuddur. Gəlin, bu sıralama üsuluna daha yaxından və detallı şəkildə nəzər salaq.

Zaman Mürəkkəbliyi (Time Complexity)

• Ən yaxşı hal (Best Case): "Merge sort" üçün ən yaxşı ssenari massivin artıq sıralanmış və ya demək olar ki, sıralanmış olduğu haldır. Lakin alqoritmin rekursiv təbiəti və massivi bölmə və birləşdirmə formasına görə, zaman mürəkkəbliyi O(nlogn) olaraq qalır.

• Orta hal (Average Case): Orta hesabla, elementlərin ilkin düzülüşündən asılı olmayaraq, "merge sort" massivi sıralamaq üçün O(nlogn) qədər zaman sərf edir.

• Ən pis hal (Worst Case): Hətta ən pis ssenaridə belə, "merge sort"un zaman mürəkkəbliyi O(nlogn) təşkil edir ki, bu da onu performans baxımından ən stabil sıralama alqoritmlərindən biri edir.

Məkan Mürəkkəbliyi (Space Complexity)

"Merge sort" birləşdirmə mərhələsində müvəqqəti sol (L[]) və sağ (R[]) massivləri üçün əlavə yaddaş sahəsindən istifadə edir. Buna görə də, onun məkan mürəkkəbliyi O(n) təşkil edir ki, bu da onu bəzi "yerində sıralama" (in-place) alqoritmləri ilə müqayisədə yaddaş baxımından daha az səmərəli edir.

Stabillik

"Merge sort" stabil sıralama alqoritmidir. Bu o deməkdir ki, eyni dəyərə malik elementlərin bir-birinə nəzərən ilkin ardıcıllığı sıralamadan sonra dəyişməz qalır. Stabillik, çoxmeyarlı sıralama kimi bir neçə mərhələli sıralama proseslərinin tələb olunduğu ssenarilərdə mühüm əhəmiyyət kəsb edir.

Üstünlüklər

"Merge sort", məlumatların ilkin ardıcıllığından asılı olmayaraq, sabit performans göstərməyə zəmanət verir. Bir çox proqram təminatı mütəxəssisi bu alqoritmin təklif etdiyi davamlılığı üstün tutur. "Merge sort" həm də stabil bir alqoritmdir ki, bu da xüsusilə verilənlər bazasının idarə edilməsi və məlumatların bütövlüyü ilə ardıcıllığının həlledici olduğu digər sahələrdə çox faydalıdır.

Onlar həmçinin xarici sıralama (external sorting) üçün çox əlverişlidir; bu, sıralanacaq məlumatların yaddaşa (RAM) sığmadığı və daha yavaş xarici yaddaşda (məsələn, diskdə) saxlanıldığı hallar üçün keçərlidir. Bu alqoritm məlumat bloklarını səmərəli şəkildə idarə edir ki, bu da onu belə ssenarilərdə prioritet seçimə çevirir.

Əsas üstünlüklərin xülasəsi:

• Proqnozlaşdırılan vaxt: Heç bir "ən pis ssenari" onu yavaşlada bilməz.

• Məlumat bütövlüyü: Stabillik sayəsində bərabər elementlərin sırası pozulmursa.

• Böyük verilənlər: RAM-dan böyük olan nəhəng faylları hissə-hissə sıralaya bilmə qabiliyyəti.

Çatışmazlıqlar

Əsas çatışmazlıq O(n) məkan mürəkkəbliyidir. Bu əlavə yaddaş tələbi böyük massivlər üçün problem yarada bilər. Lakin bu, "merge sort"un kiçik məlumat dəstləri üçün tam uyğun olduğu mənasına da gəlmir. Kiçik siyahılar üçün "insertion sort" kimi digər alqoritmlər, "merge sort"dakı rekursiv metod çağırışlarının və yaddaş ayırmalarının yaratdığı əlavə yük (overhead) səbəbindən daha sürətli ola bilər.

"Merge sort" stabil və ardıcıl performansın balansını təklif edir ki, bu da onu bir çox sıralama tapşırıqları üçün standart seçimə çevirir. Proqnozlaşdırıla bilən zaman mürəkkəbliyi onun güclü tərəfi olsa da, potensial istifadəçilər, xüsusən yaddaşın məhdud olduğu mühitlərdə, onun əlavə məkan tələblərinə qarşı diqqətli olmalıdırlar. Sıralama alqoritmini seçərkən məlumat dəstinin ölçüsünü, mövcud yaddaşı və sıralamada stabilliyin əhəmiyyətini nəzərə almaq həyatı dərəcədə vacibdir.

Yekun Müqayisə:

• Məkan (Space): Böyük massivlərdə yaddaş çatışmazlığı yarada bilər.

• Kiçik məlumatlar: Rekursiya zənciri kiçik massivlərdə vaxt itkisidir.

• Qərar vermə: Əgər yaddaş (RAM) boldursa və performansın sabitliyi vacibdirsə, Merge Sort ən yaxşısıdır.