Merge Sort এবং Quick Sort এর ধারণা এবং প্রয়োগ

Merge Sort এবং Quick Sort হল দুটি অত্যন্ত কার্যকরী বিভাজন ও বিজয় (Divide and Conquer) ভিত্তিক সর্টিং অ্যালগরিদম। এই উভয় অ্যালগরিদম বড় ডেটা সেটের জন্য দ্রুত এবং কার্যকরী, এবং তারা সাধারণত বাস্তব জীবনের পরিস্থিতিতে ব্যবহৃত হয়। নিচে তাদের ধারণা এবং C প্রোগ্রামে তাদের প্রয়োগের উদাহরণ দেওয়া হলো।

১. Merge Sort

১.১ Merge Sort এর ধারণা

Merge Sort হল একটি বিভাজন ও বিজয় ভিত্তিক সর্টিং অ্যালগরিদম যা তালিকাকে দুইটি অংশে ভাগ করে, প্রতিটি অংশকে পৃথকভাবে সাজিয়ে পরে উভয় অংশকে একত্রিত করে। এটি নিম্নলিখিত ধাপগুলো অনুসরণ করে:

1. যদি তালিকার মধ্যে ১টির বেশি উপাদান থাকে, তবে এটি তালিকাকে দুটি অংশে বিভক্ত করে।
2. প্রতিটি অংশকে পুনরায় সাজানো হয় (Recursive step)।
3. দুটি সাজানো অংশকে একত্রিত করা হয় (Merging step)।

১.২ C প্রোগ্রামে Merge Sort উদাহরণ

#include <stdio.h>

// Function to merge two subarrays
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int L[n1], R[n2];

    // Copy data to temporary arrays L[] and R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // Merge the temporary arrays back into arr[left..right]
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = left; // Initial index of merged subarray
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if there are any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Function to perform Merge Sort
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // Sort first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int size = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, size - 1);

    printf("Sorted array: \n");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

১.৩ Merge Sort এর বিশ্লেষণ

• Worst Case Time Complexity: O(n log n)
• Best Case Time Complexity: O(n log n)
• Average Case Time Complexity: O(n log n)
• Space Complexity: O(n) (কারণ এটি অতিরিক্ত স্থান ব্যবহার করে, মূলত মর্জিংয়ের জন্য)

২. Quick Sort

২.১ Quick Sort এর ধারণা

Quick Sort হল একটি দ্রুত এবং কার্যকরী সর্টিং অ্যালগরিদম যা তালিকাকে একটি পিভট (pivot) উপাদানের ভিত্তিতে বিভক্ত করে। পিভটের মাধ্যমে ডেটাকে দুটি অংশে ভাগ করা হয়: একটিতে পিভটের চেয়ে ছোট উপাদান এবং অন্যটিতে বড় উপাদান। এটি নিম্নলিখিত ধাপগুলো অনুসরণ করে:

1. একটি পিভট উপাদান নির্বাচন করুন।
2. তালিকাকে পিভটের ভিত্তিতে দুটি উপ-তালিকায় বিভক্ত করুন।
3. উভয় উপ-তালিকার জন্য Quick Sort প্রয়োগ করুন (Recursive step)।

২.২ C প্রোগ্রামে Quick Sort উদাহরণ

#include <stdio.h>

// Function to swap two elements
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Partition function
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Choosing the rightmost element as pivot
    int i = (low - 1); // Index of smaller element

    for (int j = low; j < high; j++) {
        // If current element is smaller than or equal to pivot
        if (arr[j] <= pivot) {
            i++; // Increment index of smaller element
            swap(&arr[i], &arr[j]); // Swap elements
        }
    }
    swap(&arr[i + 1], &arr[high]); // Swap the pivot element with the element at i+1
    return (i + 1); // Return the partitioning index
}

// Function to perform Quick Sort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // Partitioning index

        // Recursively sort elements before and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 80, 30, 90, 40, 50, 70};
    int size = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, size - 1);

    printf("Sorted array: \n");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

২.৩ Quick Sort এর বিশ্লেষণ

• Worst Case Time Complexity: O(n²) (যখন পিভট প্রতিবার সর্বাধিক বা সর্বনিম্ন নির্বাচিত হয়, যেমন সন্নিবেশিত তালিকায়)
• Best Case Time Complexity: O(n log n)
• Average Case Time Complexity: O(n log n)
• Space Complexity: O(log n) (কিছু সীমিত স্ট্যাক ব্যবহার করে)

৩. তুলনা এবং উপসংহার

Merge Sort এবং Quick Sort উভয়ই কার্যকরী এবং জনপ্রিয় সর্টিং অ্যালগরিদম। Merge Sort সর্বদা O(n log n) সময় জটিলতা বজায় রাখে, তবে এটি অতিরিক্ত স্থান প্রয়োজন। অন্যদিকে, Quick Sort সাধারণত দ্রুত কিন্তু এর worst-case সময় জটিলতা O(n²) হতে পারে, বিশেষত যখন পিভট অকার্যকরভাবে নির্বাচিত হয়। আপনার সমস্যা এবং ডেটার প্রয়োজন অনুসারে সঠিক এলগরিদম নির্বাচন করা গুরুত্বপূর্ণ।