algorithm
कबूतर छाँटना

कबूतर छाँटना बुनियादी जानकारी

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

कबूतर के लिए कार्य (छद्म कोड) क्रमबद्ध करें:

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

कबूतर छँटाई गिनती के समान है, इसलिए यहाँ कबूतर छाँटना और गिनती छँटाई के बीच तुलना है।

कबूतर का उदाहरण क्रमबद्ध करें:

अंतरिक्ष सहायक: O(n)
समय जटिलता: O(n + N)

C # कार्यान्वयन

public class PigeonholeSort
{
    private static void SortPigeonhole(int[] input, int n)
    {
        int min = input[0], max = input[n];
        for (int i = 1; i < n; i++)
        {
            if (input[i] < min) min = input[i];
            if (input[i] > max) max = input[i];
        }
        int range = max - min + 1;
        int[] holes = new int[range];

        for (int i = 0; i < n; i++)
        {
            holes[input[i] - min] = input[i];
        }
        int index = 0;

        for (int i = 0; i < range; i++)
        {
            foreach (var value in holes)
            {
                input[index++] = value;
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortPigeonhole(input, input.Length);
        return input;
    }
}