C++ প্রোগ্রাম: মার্জ সর্ট বাস্তবায়ন

মার্জ সর্ট টেকনিক (Merge Sort) ডিভাইড এন্ড কনকর (Divide and Conquer) টেকনিকের উপর ভিত্তি করে। আমরা পুরো ডেটা সেটকে ছোট ছোট অংশে ভাগ করি এবং সেগুলোকে সর্টেড অর্ডারে মার্জ করে বড় করে তোলি। এটি ওasst কেসও কার্যকর কারণ এই অ্যালগরিদমের ওasst কেসের জন্যও কম টাইম কমপ্লেক্সিটি থাকে।

মার্জ সর্ট টেকনিকের জটিলতা

• সময় জটিলতা: সব কেসে O(n log n)

• স্পেস জটিলতা: O(n)

ইনপুট − আনসর্টেড লিস্ট: 14 20 78 98 20 45
আউটপুট − সর্টিংয়ের পর অ্যারে: 14 20 20 45 78 98

অ্যালগরিদম

merge(array, left, middle, right)

ইনপুট: ডেটা সেট অ্যারে, left, middle এবং right ইনডেক্স

আউটপুট: মার্জড লিস্ট

শুরু
    nLeft := m - left + 1
    nRight := right - m
    leftArr এবং rightArr অ্যারে ডিফাইন করুন nLeft এবং nRight সাইজের
    i := 0 থেকে nLeft পর্যন্ত
        leftArr[i] := array[left + i]
    শেষ
    j := 0 থেকে nRight পর্যন্ত
        rightArr[j] := array[middle + j + 1]
   inished
    i := 0, j := 0, k := left
    যতক্ষণ i < nLeft AND j < nRight
        যদি leftArr[i] <= rightArr[j] হয় তবে
            array[k] = leftArr[i]
            i := i+1
        অন্যথায়
            array[k] = rightArr[j]
            j := j+1
        k := k+1
   inished
    যতক্ষণ i < nLeft
        array[k] := leftArr[i]
        i := i+1
        k := k+1
   inished
    যতক্ষণ j < nRight
        array[k] := rightArr[j]
        j := j+1
        k := k+1
   inished
শেষ

mergeSort(array, left, right)

ইনপুট: একটি ডেটা অ্যারে, এবং অ্যারের নিম্ন ও উপরের বাউন্ড

আউটপুট: সর্টেড অ্যারে

শুরু
    যদি left < right হয় তবে
        mid := left + (right - left) / 2
        mergeSort(array, left, mid)
        mergeSort(array, mid+1, right)
        merge(array, left, mid, right)
    শেষ
শেষ

উদাহরণ কোড

#include <iostream>
using namespace std;

void swapping(int &a, int &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) {
    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);
    cout << "সর্টিংয়ের পর অ্যারে: ";
    display(arr, n);
}

আউটপুট

এলিমেন্টের সংখ্যা দিন: 6
এলিমেন্টগুলো দিন:
14 20 78 98 20 45
সর্টিংয়ের আগে অ্যারে: 14 20 78 98 20 45
সর্টিংয়ের পর অ্যারে: 14 20 20 45 78 98