Merge Sort এবং Quick Sort এর মাধ্যমে Divide and Conquer

Divide and Conquer একটি শক্তিশালী অ্যালগরিদমিক কৌশল যা কোনো বড় সমস্যাকে ছোট ছোট উপ-সমস্যায় বিভক্ত করে এবং তারপর সেই উপ-সমস্যাগুলির সমাধান একত্রিত করে। এই পদ্ধতিতে, আমরা প্রথমে একটি সমস্যাকে দুটি বা তার বেশি ছোট উপ-সমস্যায় ভাগ করি, তারপর সেই উপ-সমস্যাগুলির সমাধান করি এবং সবশেষে তাদের সমাধান একত্রিত করে মূল সমস্যার সমাধান পেয়ে যাই। Merge Sort এবং Quick Sort দুটি জনপ্রিয় অ্যালগরিদম যা Divide and Conquer পদ্ধতিতে কাজ করে।

Merge Sort

Merge Sort একটি কার্যকরী Divide and Conquer অ্যালগরিদম যা একটি অ্যারে বা তালিকা সন্নিবেশ করতে ব্যবহার করা হয়। এটি অ্যারের মাঝখানে বিভক্ত করে, তারপর প্রতিটি ভাগের উপাদানগুলোকে সন্নিবেশিতভাবে একত্রিত (merge) করে সম্পূর্ণ অ্যারে সাজানোর কাজ করে।

Merge Sort এর ধাপ:

1. অ্যারেটি মাঝখানে ভাগ করা হয়।
2. প্রতিটি ভাগকে আবার ভাগ করা হয় যতক্ষণ না অ্যারের মধ্যে একক উপাদান (1 element) থাকে।
3. পরে, ছোট ছোট অ্যারের উপাদানগুলো একত্রিত হয়ে সাজানো অ্যারে তৈরি হয়।

সময় জটিলতা:

• Worst-case time complexity: O(n log n)
• Best-case time complexity: O(n log n)
• Space complexity: O(n)

উদাহরণ:

public class MergeSort {

    // Merge Sort function
    public static void mergeSort(int[] arr) {
        if (arr.length < 2) return;

        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];

        // Copy elements into left and right sub-arrays
        System.arraycopy(arr, 0, left, 0, mid);
        System.arraycopy(arr, mid, right, 0, arr.length - mid);

        // Recursively sort both halves
        mergeSort(left);
        mergeSort(right);

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

    // Merge function to combine two sorted sub-arrays
    private static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        // Merge the two arrays into the original array
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        // Copy remaining elements from left or right
        while (i < left.length) {
            arr[k++] = left[i++];
        }
        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        mergeSort(arr);
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Merge Sort এর কার্যকারিতা:

1. mergeSort() ফাংশনটি অ্যারেটিকে দুটি ভাগে বিভক্ত করে।
2. merge() ফাংশনটি দুইটি সাজানো অ্যারে (left এবং right) একত্রিত করে একটি নতুন সাজানো অ্যারে তৈরি করে।

Quick Sort

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

Quick Sort এর ধাপ:

1. একটি পিভট উপাদান নির্বাচন করা হয় (সাধারণত শেষ বা প্রথম উপাদান নির্বাচন করা হয়)।
2. অ্যারের এলিমেন্টগুলোকে পিভটের চারপাশে সজ্জিত করা হয়।
3. দুটি সাব-অ্যারেতে পুনরায় Quick Sort প্রক্রিয়া চালানো হয়।

সময় জটিলতা:

• Worst-case time complexity: O(n^2) (যখন পিভট সবচেয়ে খারাপভাবে নির্বাচন করা হয়)
• Best-case time complexity: O(n log n)
• Average-case time complexity: O(n log n)
• Space complexity: O(log n) (স্ট্যাকের গভীরতা)

উদাহরণ:

public class QuickSort {

    // QuickSort function
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Find pivot element
            int pivotIndex = partition(arr, low, high);

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

    // Partition function to rearrange elements around pivot
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Swap arr[i+1] and arr[high] (pivot element)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1; // Return the partition index
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Quick Sort এর কার্যকারিতা:

1. quickSort() ফাংশনটি অ্যারে ভাগ করে পিভটের চারপাশে সজ্জিত করে, তারপর দুইটি সাব অ্যারেতে পুনরায় Quick Sort চালায়।
2. partition() ফাংশনটি পিভট এলিমেন্ট নির্বাচন করে এবং তার চারপাশের এলিমেন্টগুলোকে সঠিক অবস্থানে রেখে পিভটের সঠিক স্থান নির্ধারণ করে।

Merge Sort এবং Quick Sort এর মধ্যে পার্থক্য

সারাংশ

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