Merge Sort এবং Quick Sort গাইড ও নোট

Merge Sort এবং Quick Sort হল দুটি জনপ্রিয় এবং কার্যকরী divide-and-conquer অ্যালগরিদম, যা ডাটা সোর্টিং করতে ব্যবহৃত হয়। এই দুটি অ্যালগরিদম বিভিন্ন পদ্ধতিতে কাজ করে এবং প্রতিটি অ্যালগরিদমের কিছু শক্তি এবং দুর্বলতা রয়েছে। এখানে আমরা Merge Sort এবং Quick Sort এর কার্যপ্রণালী, বৈশিষ্ট্য, এবং Java তে তাদের বাস্তবায়ন নিয়ে আলোচনা করব।

1. Merge Sort

Merge Sort হল একটি ডিভাইড-এন্ড-কনকার অ্যালগরিদম যা divide-and-conquer পদ্ধতি ব্যবহার করে একটি অ্যারে বা তালিকাকে সজ্জিত করতে সাহায্য করে। এটি একটি stable sort এবং O(n log n) টাইম কমপ্লেক্সিটি সহ একটি নির্ভরযোগ্য সোর্টিং অ্যালগরিদম।

1.1. Merge Sort Algorithm

1. Divide: একটি অ্যারে বা তালিকাকে দুইটি ভাগে বিভক্ত করুন যতক্ষণ না প্রতিটি সাব-অ্যারেতে একক উপাদান থাকে।
2. Conquer: প্রত্যেকটি সাব-অ্যারেকে সজ্জিত করুন। একটি অ্যারে দুটি ছোট অ্যারেতে বিভক্ত হয়ে যায় এবং পুনরাবৃত্তি অব্যাহত থাকে।
3. Combine: দুটি সাজানো অ্যারে একত্রিত করুন এবং তাদের একত্রিত করলে একটি সাজানো অ্যারে পাওয়া যায়।

1.2. Merge Sort Example in Java

import java.util.Arrays;

public class MergeSort {
    
    // Merge Sort Function
    public static void mergeSort(int[] array) {
        if (array.length < 2) return;  // Base case, array is already sorted
        
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);  // Left subarray
        int[] right = Arrays.copyOfRange(array, mid, array.length);  // Right subarray
        
        mergeSort(left);   // Recursively sort the left subarray
        mergeSort(right);  // Recursively sort the right subarray
        
        merge(array, left, right);  // Merge the two sorted subarrays
    }

    // Merge two sorted subarrays
    private static void merge(int[] array, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                array[k++] = left[i++];
            } else {
                array[k++] = right[j++];
            }
        }
        
        // Copy remaining elements of left array
        while (i < left.length) {
            array[k++] = left[i++];
        }
        
        // Copy remaining elements of right array
        while (j < right.length) {
            array[k++] = right[j++];
        }
    }

    // Main method to test MergeSort
    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Before Sorting: " + Arrays.toString(array));
        mergeSort(array);
        System.out.println("After Sorting: " + Arrays.toString(array));
    }
}

ব্যাখ্যা:

• mergeSort(): অ্যারেটি রিকার্সিভভাবে বিভক্ত করার জন্য ব্যবহৃত হচ্ছে।
• merge(): দুইটি সাজানো সাব-অ্যারেকে একত্রিত করার জন্য ব্যবহৃত হচ্ছে।

আউটপুট:

Before Sorting: [38, 27, 43, 3, 9, 82, 10]
After Sorting: [3, 9, 10, 27, 38, 43, 82]

সময় জটিলতা:

• Worst Case: O(n log n)
• Best Case: O(n log n)
• Average Case: O(n log n)

2. Quick Sort

Quick Sort একটি অন্যরকম divide-and-conquer অ্যালগরিদম, যা pivot উপাদান নির্বাচন করে এবং ডাটা সেই pivot এর তুলনায় ছোট এবং বড় অংশে ভাগ করে দেয়। এটি একটি অস্থির অ্যালগরিদম এবং প্রায়ই কার্যকরী হয়, তবে সঠিক pivot নির্বাচন করা খুবই গুরুত্বপূর্ণ।

2.1. Quick Sort Algorithm

1. Pivot Selection: একটি pivot নির্বাচন করুন।
2. Partition: ডাটা দুটি ভাগে বিভক্ত করুন যেখানে একটি ভাগের উপাদানগুলির মান pivot এর চেয়ে ছোট, এবং অন্যটি pivot এর চেয়ে বড়।
3. Recur: প্রতিটি ভাগে QuickSort প্রয়োগ করুন।
4. Base Case: যদি সাব-অ্যারের আকার ১ বা ০ হয়, তাহলে পুনরাবৃত্তি বন্ধ করুন।

2.2. Quick Sort Example in Java

import java.util.Arrays;

public class QuickSort {

    // QuickSort function
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            quickSort(array, low, pivotIndex - 1);  // Recursively sort the left subarray
            quickSort(array, pivotIndex + 1, high); // Recursively sort the right subarray
        }
    }

    // Partition function
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];  // Choosing the last element as pivot
        int i = low - 1;

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

        // Swap the pivot element with the element at i + 1
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;

        return i + 1;
    }

    // Main method to test QuickSort
    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Before Sorting: " + Arrays.toString(array));
        quickSort(array, 0, array.length - 1);
        System.out.println("After Sorting: " + Arrays.toString(array));
    }
}

ব্যাখ্যা:

• quickSort(): রিকার্সিভভাবে সাব-অ্যারে সেগুলির জন্য QuickSort প্রয়োগ করা হচ্ছে।
• partition(): একটি pivot নির্বাচন করে, এবং ছোট ও বড় উপাদানগুলি বিভক্ত করা হচ্ছে।

আউটপুট:

Before Sorting: [38, 27, 43, 3, 9, 82, 10]
After Sorting: [3, 9, 10, 27, 38, 43, 82]

সময় জটিলতা:

• Worst Case: O(n²) (যখন প্রতিবার খারাপ pivot নির্বাচন করা হয়)
• Best Case: O(n log n) (যখন pivot খুব ভালোভাবে নির্বাচন করা হয়)
• Average Case: O(n log n)

3. Merge Sort vs Quick Sort

সারাংশ

• Merge Sort: এটি একটি divide-and-conquer অ্যালগরিদম, যেখানে ডাটা দুইটি ভাগে বিভক্ত করে এবং তাদের একত্রিত (merge) করা হয়। এটি একটি stable sort এবং O(n log n) টাইম কমপ্লেক্সিটি রাখে, তবে এটি অতিরিক্ত O(n) স্পেস ব্যবহার করে।
• Quick Sort: এটি একটি divide-and-conquer অ্যালগরিদম যা pivot নির্বাচন করে ডাটাকে ছোট এবং বড় অংশে ভাগ করে দেয়। এটি সাধারণত O(n log n) সময়ে কাজ করে, তবে খারাপ pivot নির্বাচন করলে এর O(n²) টাইম কমপ্লেক্সিটি হতে পারে।

যেহেতু Quick Sort সাধারণত দ্রুততর হয় এবং in-place সোর্টিং করে, এটি সাধারণত ছোট এবং মাঝারি আকারের ডেটাসেটের জন্য ব্যবহৃত হয়, যেখানে Merge Sort ব্যবহার করা হয় বড় ডেটাসেটের জন্য বা যখন stability প্রয়োজন হয়।