C++ में पिजनहोल सॉर्ट प्रोग्राम

पिजनहोल सॉर्ट क्या है?

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

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

पिजनहोल सॉर्टिंग, जिसे काउंट सॉर्ट के नाम से भी जाना जाता है, एक सॉर्टिंग एल्गोरिदम है जो तत्वों की सूची को सॉर्ट करने के लिए उपयुक्त है जहां तत्वों की संख्या (n) और संभावित कुंजी मानों की संख्या (N) लगभग समान होती है। इसके लिए O(n + N) समय की आवश्यकता होती है।

Input: arr[] = {7, 4, 2, 6, 3, 1, 5}
Output: 1 2 3 4 5 6 7

व्याख्या

1. सरणी में न्यूनतम और अधिकतम तत्व ढूंढें। न्यूनतम और अधिकतम तत्व क्रमशः 'min' और 'max' होंगे। फिर रेंज ज्ञात करें: 'max - min + 1'
2. रेंज के समान आकार के लिए प्रारंभ में खाली "पिजनहोल्स" के लिए एक सरणी सेट करें
3. सरणी के प्रत्येक तत्व को पार करें और फिर प्रत्येक तत्व को उसके पिजनहोल में डालें। एक तत्व arr[i] को इंडेक्स arr[i] - min पर होल में डाला जाएगा
4. लूप पिजनहोल सरणी पर क्रम में फिर से शुरू होगा और सभी तत्वों को गैर-खाली होल से वापस मूल सरणी में डालेगा

उदाहरण

#include <iostream>
using namespace std;

#define MAX 7

void pigeonhole_sort(int min, int max, int *a) {
    int size = max - min + 1;
    int holes[size];

    // होल्स को 0 से इनिशियलाइज़ करें
    for (int i = 0; i < size; i++) {
        holes[i] = 0;
    }

    // प्रत्येक तत्व को उसके होल में रखें
    int *current = a;
    for (int i = 0; i < size; i++, current++) {
        holes[*current - min] += 1;
    }

    // होल्स से वापस सरणी में कॉपी करें
    int count = 0;
    current = a;
    for (int i = 0; i < size; i++) {
        while (holes[i]-- > 0) {
            *current++ = i + min;
        }
    }
}

int main() {
    int a[] = {7, 4, 2, 6, 3, 1, 5};
    int min = a[0], max = a[0];

    for (int i = 1; i < MAX; i++) {
        if (a[i] < min) min = a[i];
        if (a[i] > max) max = a[i];
    }

    pigeonhole_sort(min, max, a);

    for (int i = 0; i < MAX; i++) {
        cout << a[i] << "\t";
    }
    return 0;
}

आउटपुट

1 2 3 4 5 6 7

जटिलता विश्लेषण

स्थान जटिलता: O(N) जहां N = max - min + 1

कब उपयोग करें

• जब तत्वों की संख्या (n) और कुंजी मानों की रेंज (N) लगभग समान हो
• जब इनपुट पूर्णांक हों और रेंज छोटी हो
• काउंटिंग सॉर्ट के समान उपयोग मामले

सीमाएं

• बड़ी रेंज के लिए उपयुक्त नहीं (मेमोरी बर्बादी)
• केवल पूर्णांकों के लिए काम करता है
• नकारात्मक संख्याओं के लिए अतिरिक्त हैंडलिंग की आवश्यकता