पिजनहोल सॉर्ट

यह नॉन-कंपेरिजन सॉर्टिंग तकनीक का एक उदाहरण है। इसका उपयोग वहां किया जाता है जहां आइटम्स की संख्या और संभावित की वैल्यूज़ की रेंज लगभग समान होती है।

इस सॉर्ट को करने के लिए, हमें कुछ होल्स बनाने की आवश्यकता होती है। आवश्यक होल्स की संख्या नंबर्स की रेंज द्वारा तय की जाती है। प्रत्येक होल में, आइटम्स इन्सर्ट किए जाते हैं। अंत में होल से डिलीट करके सॉर्टेड ऑर्डर के लिए एक ऐरे में स्टोर किया जाता है।

पिजन-होल सॉर्ट तकनीक की जटिलता

• टाइम कॉम्प्लेक्सिटी: O(n + 2^k)
• स्पेस कॉम्प्लेक्सिटी: O(2^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

एल्गोरिदम

pigeonHoleSort(array, size)

इनपुट: डेटा का एक ऐरे, और ऐरे में कुल संख्या
आउटपुट: सॉर्टेड ऐरे

Begin
    ऐरे लिस्ट से मैक्स और मिन ढूंढें
    holeRange := max - min + 1
    holeRange संख्या के लिस्ट्स परिभाषित करें
    for i := 0 to n-1 do
        hole[array[i] - min].append(array[i])
    done
    count := 0
    for j := 0 to holeRange - 1 do
        while hole[j] खाली नहीं है do
            array[count] := hole[j] का पहला नोड प्राप्त करें और इसे डिलीट करें
            count := count + 1
        done
    done
End

उदाहरण

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

void getMaxMin(int *arr, int n, int &maximum, int &minimum) {
    maximum = minimum = arr[0]; // प्रारंभ में मैक्स और मिन arr[0] हैं
    for(int i = 1; i < n; i++) {
        if(arr[i] > maximum)
            maximum = arr[i]; // अधिकतम डेटा प्राप्त करें
        if(arr[i] < minimum)
            minimum = arr[i]; // न्यूनतम डेटा प्राप्त करें
    }
}

void pegionHoleSort(int *arr, int n) {
    int max, min;
    getMaxMin(arr, n, max, min);
    int holeRange = max - min + 1;
    list<int> hole[holeRange]; // होल्स का एक ऐरे बनाएं
    for(int i = 0; i < n; i++) {
        hole[arr[i] - min].push_back(arr[i]);
    }
    int count = 0;
    for(int j = 0; j < holeRange; j++) {
        // लिंक्ड लिस्ट्स से डिलीट करें और ऐरे में स्टोर करें
        while(!hole[j].empty()) {
            arr[count] = *(hole[j].begin());
            hole[j].erase(hole[j].begin());
            count++;
        }
    }
}

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

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

आउटपुट

एलिमेंट्स की संख्या दर्ज करें: 10
एलिमेंट्स दर्ज करें: 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