algorithm
मतगणना क्रमबद्ध करें

आधारभूत सूचनाओं की गणना करना

सॉर्टिंग काउंटिंग ऑब्जेक्ट्स के संग्रह के लिए एक पूर्णांक सॉर्टिंग एल्गोरिदम है जो ऑब्जेक्ट्स की कुंजी के अनुसार सॉर्ट करता है।

कदम

1. एक कार्य सरणी C का निर्माण करें जिसका आकार इनपुट सरणी A की सीमा के बराबर है।
2. A के माध्यम से Iterate, C [x] को असाइन करते हुए x में A की संख्या के आधार पर दिखाई देता है।
3. C को किसी ऐसी सरणी में बदलना जहाँ C [x] सरणी के माध्यम से पुनरावृत्ति करके मानों की संख्या को संदर्भित करता है it x, प्रत्येक C [x] को उसके पूर्व मान का मूल्य और C से पहले आने वाले सभी मानों को निर्दिष्ट करता है।
4. C में दर्ज इंडेक्स पर एक नए सॉर्ट किए गए सरणी B में प्रत्येक मान रखते हुए A के माध्यम से पीछे की ओर जाएं। इसमें दिए गए एक के लिए किया जाता है [x] बताए बी [सी [एक [x]]] एक [x] के लिए, और decrementing सी द्वारा [एक [x]] मामले में मूल अवर्गीकृत सरणी में डुप्लिकेट मानों थे।

काउंटिंग सॉर्ट का उदाहरण

सहायक स्थान: O(n+k)
समय जटिलता: सबसे खराब स्थिति: O(n+k) , सर्वश्रेष्ठ-मामला: O(n) , औसत-केस O(n+k)

Psuedocode कार्यान्वयन

प्रतिबंध:

1. इनपुट (सॉर्ट की जाने वाली सरणी)
2. इनपुट में तत्व की संख्या (n)
3. 0..k-1 (k) की सीमा में कुंजियाँ
4. गणना (संख्या की एक सरणी)

स्यूडोकोड:

for x in input:
    count[key(x)] += 1
total = 0
for i in range(k):
    oldCount = count[i]
    count[i] = total
    total += oldCount
for x in input:
    output[count[key(x)]] = x
    count[key(x)] += 1
return output

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

public class CountingSort
{
    public static void SortCounting(int[] input, int min, int max)
    {
        var count = new int[max - min + 1];
        var z = 0;

        for (var i = 0; i < count.Length; i++)
            count[i] = 0;

        foreach (int i in input)
            count[i - min]++;

        for (var i = min; i <= max; i++)
        {
            while (count[i - min]-- > 0)
            {
                input[z] = i;
                ++z;
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortCounting(input, input.Min(), input.Max());
        return input;
    }
}