रेडिक्स सॉर्ट

रेडिक्स सॉर्ट एक नॉन-कंपेरेटिव सॉर्टिंग एल्गोरिदम है। यह सॉर्टिंग एल्गोरिदम पूर्णांक कुंजियों पर काम करता है उन अंकों को ग्रुप करके जो समान स्थिति और मान साझा करते हैं। रेडिक्स एक संख्या प्रणाली का आधार है। जैसा कि हम जानते हैं कि दशमलव प्रणाली में रेडिक्स या आधार 10 है। इसलिए कुछ दशमलव संख्याओं को सॉर्ट करने के लिए, हमें संख्याओं को स्टोर करने के लिए 10 स्थितिगत बॉक्स की आवश्यकता होती है।

रेडिक्स सॉर्ट तकनीक की जटिलता

• टाइम कॉम्प्लेक्सिटी: O(nk)
• स्पेस कॉम्प्लेक्सिटी: O(n + k)

इनपुट और आउटपुट

इनपुट: अनसॉर्टेड लिस्ट: 802 630 20 745 52 300 612 932 78 187
आउटपुट: सॉर्टिंग से पहले डेटा: 802 630 20 745 52 300 612 932 78 187
सॉर्टिंग के बाद डेटा: 20 52 78 187 300 612 630 745 802 932

एल्गोरिदम

radixSort(array, size, maxDigit)

इनपुट: डेटा का एक ऐरे, और ऐरे में कुल संख्या, मैक्स नंबर की अंक गणना
आउटपुट: सॉर्टेड ऐरे।

Begin
    10 लिस्ट को पॉकेट के रूप में परिभाषित करें
    for i := 0 to max - 1 do
        m = 10^(i+1)
        p := 10^i
        for j := 0 to n-1 do
            temp := array[j] mod m
            index := temp / p
            pocket[index].append(array[j])
        done
        count := 0
        for j := 0 to radix do
            while pocket[j] is not empty
                array[count] := pocket[j] का पहला नोड प्राप्त करें और इसे डिलीट करें
                count := count + 1
            done
        done
    done
End

उदाहरण

#include <iostream>
#include <list>
#include <cmath>
using namespace std;

void display(int *array, int size) {
    for(int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void radixSort(int *arr, int n, int max) {
    int i, j, m, p = 1, index, temp, count = 0;
    list<int> pocket[10]; // दशमलव संख्या का रेडिक्स 10 है
    for(i = 0; i < max; i++) {
        m = pow(10, i + 1);
        p = pow(10, i);
        for(j = 0; j < n; j++) {
            temp = arr[j] % m;
            index = temp / p; // पॉकेट ऐरे के लिए इंडेक्स ढूंढें
            pocket[index].push_back(arr[j]);
        }
        count = 0;
        for(j = 0; j < 10; j++) {
            // लिंक्ड लिस्ट्स से डिलीट करें और ऐरे में स्टोर करें
            while(!pocket[j].empty()) {
                arr[count] = *(pocket[j].begin());
                pocket[j].erase(pocket[j].begin());
                count++;
            }
        }
    }
}

int main() {
    int n, max;
    cout << "एलिमेंट्स की संख्या दर्ज करें: ";
    cin >> n;
    cout << "एलिमेंट्स के अधिकतम अंक दर्ज करें: ";
    cin >> max;
    int arr[n]; // दिए गए एलिमेंट्स की संख्या के साथ ऐरे बनाएं
    cout << "एलिमेंट्स दर्ज करें:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "सॉर्टिंग से पहले डेटा: ";
    display(arr, n);
    radixSort(arr, n, max);
    cout << "सॉर्टिंग के बाद डेटा: ";
    display(arr, n);
}

आउटपुट

एलिमेंट्स की संख्या दर्ज करें: 10
एलिमेंट्स के अधिकतम अंक दर्ज करें: 3
एलिमेंट्स दर्ज करें: 802 630 20 745 52 300 612 932 78 187
सॉर्टिंग से पहले डेटा: 802 630 20 745 52 300 612 932 78 187
सॉर्टिंग के बाद डेटा: 20 52 78 187 300 612 630 745 802 932