मर्ज सॉर्ट

मर्ज सॉर्ट तकनीक डिवाइड एंड कन्कर तकनीक पर आधारित है। हम पूरे डेटासेट को छोटे भागों में विभाजित करते हैं और उन्हें सॉर्टेड ऑर्डर में एक बड़े भाग में मर्ज करते हैं। यह सबसे खराब मामलों के लिए भी बहुत प्रभावी है क्योंकि इस एल्गोरिदम की सबसे खराब स्थिति के लिए भी कम टाइम कॉम्प्लेक्सिटी है।

मर्ज सॉर्ट तकनीक की जटिलता

• टाइम कॉम्प्लेक्सिटी: सभी मामलों के लिए O(n log n)
• स्पेस कॉम्प्लेक्सिटी: O(n)

इनपुट और आउटपुट

इनपुट: अनसॉर्टेड लिस्ट: 14 20 78 98 20 45
आउटपुट: सॉर्टिंग से पहले ऐरे: 14 20 78 98 20 45
सॉर्टिंग के बाद ऐरे: 14 20 20 45 78 98

एल्गोरिदम

merge(array, left, middle, right)

इनपुट: डेटासेट ऐरे, लेफ्ट, मिडल और राइट इंडेक्स

आउटपुट: मर्ज की गई लिस्ट

Begin
    nLeft := m - left + 1
    nRight := right - m
    लेफ्ट और राइट ऐरे को क्रमशः nLeft और nRight साइज के साथ परिभाषित करें
    for i := 0 to nLeft do
        leftArr[i] := array[left + i]
    done
    for j := 0 to nRight do
        rightArr[j] := array[middle + j + 1]
    done
    i := 0, j := 0, k := left
    while i < nLeft AND j < nRight do
        if leftArr[i] <= rightArr[j] then
            array[k] = leftArr[i]
            i := i + 1
        else
            array[k] = rightArr[j]
            j := j + 1
        k := k + 1
    done
    while i < nLeft do
        array[k] := leftArr[i]
        i := i + 1
        k := k + 1
    done
    while j < nRight do
        array[k] := rightArr[j]
        j := j + 1
        k := k + 1
    done
End

mergeSort(array, left, right)

इनपुट: डेटा का एक ऐरे, और ऐरे की निचली और ऊपरी सीमा

आउटपुट: सॉर्टेड ऐरे

Begin
    if left < right then
        mid := left + (right - left) / 2
        mergeSort(array, left, mid)
        mergeSort(array, mid + 1, right)
        merge(array, left, mid, right)
End

उदाहरण

#include <iostream>
using namespace std;

void swapping(int &a, int &b) {
    // a और b की सामग्री को स्वैप करें
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void display(int *array, int size) {
    for(int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void merge(int *array, int l, int m, int r) {
    int i, j, k, nl, nr;
    // लेफ्ट और राइट सब-ऐरे का साइज
    nl = m - l + 1; nr = r - m;
    int larr[nl], rarr[nr];
    // लेफ्ट और राइट सब-ऐरे भरें
    for(i = 0; i < nl; i++)
        larr[i] = array[l + i];
    for(j = 0; j < nr; j++)
        rarr[j] = array[m + 1 + j];
    i = 0; j = 0; k = l;
    // अस्थायी ऐरे को रियल ऐरे में मर्ज करें
    while(i < nl && j < nr) {
        if(larr[i] <= rarr[j]) {
            array[k] = larr[i];
            i++;
        } else {
            array[k] = rarr[j];
            j++;
        }
        k++;
    }
    while(i < nl) {
        // लेफ्ट ऐरे में अतिरिक्त एलिमेंट
        array[k] = larr[i];
        i++; k++;
    }
    while(j < nr) {
        // राइट ऐरे में अतिरिक्त एलिमेंट
        array[k] = rarr[j];
        j++; k++;
    }
}

void mergeSort(int *array, int l, int r) {
    int m;
    if(l < r) {
        int m = l + (r - l) / 2;
        // पहले और दूसरे ऐरे को सॉर्ट करें
        mergeSort(array, l, m);
        mergeSort(array, m + 1, r);
        merge(array, l, m, r);
    }
}

int main() {
    int n;
    cout << "एलिमेंट्स की संख्या दर्ज करें: ";
    cin >> n;
    int arr[n]; // दिए गए एलिमेंट्स की संख्या के साथ ऐरे बनाएं
    cout << "एलिमेंट्स दर्ज करें:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "सॉर्टिंग से पहले ऐरे: ";
    display(arr, n);
    mergeSort(arr, 0, n - 1); // (n-1) अंतिम इंडेक्स के लिए
    cout << "सॉर्टिंग के बाद ऐरे: ";
    display(arr, n);
}

आउटपुट

एलिमेंट्स की संख्या दर्ज करें: 6
एलिमेंट्स दर्ज करें: 14 20 78 98 20 45
सॉर्टिंग से पहले ऐरे: 14 20 78 98 20 45
सॉर्टिंग के बाद ऐरे: 14 20 20 45 78 98