Counting Sort, Radix Sort, এবং Bucket Sort গাইড ও নোট

Counting Sort, Radix Sort, এবং Bucket Sort হল non-comparison-based sorting algorithms। এই অ্যালগরিদমগুলি O(n) টাইম কমপ্লেক্সিটিতে কাজ করতে সক্ষম, যেখানে n হল উপাদান সংখ্যা। এগুলি তুলনামূলকভাবে দ্রুত হতে পারে যখন ডাটা নির্দিষ্ট সীমার মধ্যে থাকে। এই গাইডে, আমরা প্রতিটি অ্যালগরিদমের কাজের প্রক্রিয়া এবং জাভাতে তাদের বাস্তবায়ন নিয়ে আলোচনা করব।

1. Counting Sort

Counting Sort একটি স্থির সংখ্যা (integers) ভিত্তিক সোর্টিং অ্যালগরিদম। এটি একটি অতিরিক্ত অ্যারে ব্যবহার করে যাতে প্রতিটি সম্ভাব্য মানের গণনা রাখা হয় এবং তারপর সেই গুণগত সংখ্যাগুলি ব্যবহার করে সঠিকভাবে ডাটা সাজানো হয়। Counting Sort শুধুমাত্র তখন কার্যকরী যখন ইনপুট ডাটার পরিসীমা (range) সীমিত হয় এবং তা ইন্টিজার হতে হবে।

1.1. Counting Sort Algorithm Steps

1. Count the frequency of each element in the input array.
2. Modify the count array by adding each element's frequency with the sum of the previous counts.
3. Place elements in the output array based on their frequencies.

1.2. Counting Sort in Java

import java.util.Arrays;

public class CountingSort {

    public void countingSort(int[] arr) {
        int n = arr.length;

        // Find the maximum element in the array
        int max = Arrays.stream(arr).max().getAsInt();

        // Create count array and initialize with 0
        int[] count = new int[max + 1];

        // Count the frequency of each element
        for (int i = 0; i < n; i++) {
            count[arr[i]]++;
        }

        // Update the count array to contain the actual position of each element
        for (int i = 1; i <= max; i++) {
            count[i] += count[i - 1];
        }

        // Output array to store the sorted elements
        int[] output = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            output[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }

        // Copy the sorted array to the original array
        System.arraycopy(output, 0, arr, 0, n);
    }

    // Utility function to print the array
    public void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        CountingSort sorter = new CountingSort();
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        
        System.out.println("Original Array:");
        sorter.printArray(arr);
        
        sorter.countingSort(arr);
        
        System.out.println("Sorted Array:");
        sorter.printArray(arr);  // Output: 1 2 2 3 3 4 8
    }
}

1.3. Explanation:

• Step 1: আমরা ইনপুট অ্যারেতে প্রতিটি সংখ্যার ফ্রিকোয়েন্সি হিসাব করি।
• Step 2: Count array আপডেট করা হয় যাতে এতে প্রতিটি উপাদানের সঠিক অবস্থান পাওয়া যায়।
• Step 3: সঠিক স্থানে উপাদানগুলি output array তে রাখার পর, আমরা সেগুলি মূল অ্যারে তে কপি করি।

2. Radix Sort

Radix Sort একটি ডিজিট ভিত্তিক সোর্টিং অ্যালগরিদম যা সংখ্যাগুলির প্রতিটি ডিজিট নিয়ে কাজ করে। এটি LSD (Least Significant Digit) বা MSD (Most Significant Digit) পদ্ধতিতে কাজ করতে পারে, তবে সাধারণত LSD পদ্ধতি বেশি ব্যবহৃত হয়।

2.1. Radix Sort Algorithm Steps

1. Sort the elements based on the least significant digit (LSD) first.
2. Move to the next digit and sort the elements again.
3. Repeat this process for all the digits (until the largest digit's place).

2.2. Radix Sort in Java

import java.util.Arrays;

public class RadixSort {

    // Function to perform counting sort on the basis of digit
    private void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10]; // Counting digits from 0 to 9

        // Store count of occurrences in count[]
        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }

        // Change count[i] so that count[i] now contains actual position of this digit in output[]
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // Build the output array
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        // Copy the output array to arr[], so that arr[] now contains sorted numbers based on current digit
        System.arraycopy(output, 0, arr, 0, n);
    }

    // Function to perform radix sort
    public void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();

        // Perform counting sort for every digit. The exp is 10^i where i is current digit number
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    // Utility function to print the array
    public void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        RadixSort sorter = new RadixSort();
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        
        System.out.println("Original Array:");
        sorter.printArray(arr);
        
        sorter.radixSort(arr);
        
        System.out.println("Sorted Array:");
        sorter.printArray(arr);  // Output: 2 24 45 66 75 90 170 802
    }
}

2.3. Explanation:

• Counting Sort is applied to each digit of the numbers in increasing significance (LSD).
• We start from the least significant digit and move towards the most significant digit.
• At each step, the array is sorted based on the current digit, and this process continues for all digits.

3. Bucket Sort

Bucket Sort একটি ডিস্ট্রিবিউশন ভিত্তিক অ্যালগরিদম যা ইনপুট ডাটাকে ছোট buckets (বালতিতে) ভাগ করে এবং পরে প্রতিটি বালতিতে আলাদাভাবে সোর্টিং করে।

3.1. Bucket Sort Algorithm Steps

1. Create buckets: Input array-এর উপাদানগুলিকে বিভিন্ন বালতিতে ভাগ করুন।
2. Sort the buckets: প্রতিটি বালতিকে আলাদাভাবে সোর্ট করুন।
3. Concatenate the results: সব বালতি একত্রিত করে সঠিকভাবে সাজানো অ্যারে তৈরি করুন।

3.2. Bucket Sort in Java

import java.util.*;

public class BucketSort {

    public void bucketSort(float[] arr) {
        // 1. Create an array of empty buckets
        int n = arr.length;
        if (n <= 0) return;

        @SuppressWarnings("unchecked")
        List<Float>[] buckets = new List[n];

        // 2. Put elements into different buckets
        for (int i = 0; i < n; i++) {
            int index = (int) (n * arr[i]);  // Get the index of the bucket
            if (buckets[index] == null) {
                buckets[index] = new ArrayList<>();
            }
            buckets[index].add(arr[i]);
        }

        // 3. Sort each bucket and concatenate the results
        int k = 0;
        for (int i = 0; i < n; i++) {
            if (buckets[i] != null) {
                Collections.sort(buckets[i]);
                for (float num : buckets[i]) {
                    arr[k++] = num;
                }
            }
        }
    }

    // Utility function to print the array
    public void printArray(float[] arr) {
        for (float num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        BucketSort sorter = new BucketSort();
        float[] arr = {0.42f, 0.32f, 0.23f, 0.85f, 0.91f, 0.61f};

        System.out.println("Original Array:");
        sorter.printArray(arr);

        sorter.bucketSort(arr);

        System.out.println("Sorted Array:");
        sorter.printArray(arr);  // Output: 0.23 0.32 0.42 0.61 0.85 0.91
    }
}

3.3. Explanation:

• Bucket Sort প্রথমে উপাদানগুলোকে বিভিন্ন বালতিতে বিভক্ত করে, তারপর প্রতিটি বালতিকে সোর্ট করে এবং সবার শেষে বালতিগুলি একত্রিত করে একটি সাজানো অ্যারে তৈরি করে।
• Bucket Sort অ্যালগরিদমটি বিশেষভাবে উপকারী যখন উপাদানগুলো অনেকটা সমানভাবে বিতরিত থাকে।

সারাংশ

Counting Sort, Radix Sort, এবং Bucket Sort হল non-comparison-based sorting algorithms যা বিভিন্ন সমস্যা সমাধান করতে ব্যবহার করা হয়। Counting Sort ইন্টিজার এবং সীমিত পরিসরের ডাটার জন্য উপযোগী, Radix Sort সংখ্যার ডিজিট ভিত্তিক সোর্টিং এবং Bucket Sort সাধারণত ধারাবাহিক বা সরল সংখ্যা সংগ্রহের জন্য ভাল কাজ করে। এই তিনটি অ্যালগরিদমের মধ্যে Bucket Sort এবং Radix Sort সাধারণত O(n) টাইম কমপ্লেক্সিটিতে কাজ করতে পারে, যখন Counting Sort একটি নির্দিষ্ট সীমার মধ্যে কার্যকরী হয়।