काउंटिंग सॉर्ट

काउंटिंग सॉर्ट एक स्टेबल सॉर्टिंग तकनीक है, जिसका उपयोग ऑब्जेक्ट्स को छोटी संख्याओं की कीज़ के अनुसार सॉर्ट करने के लिए किया जाता है। यह उन कीज़ की संख्या गिनता है जिनके की वैल्यूज़ समान हैं। यह सॉर्टिंग तकनीक तब प्रभावी होती है जब विभिन्न कीज़ के बीच का अंतर अधिक बड़ा नहीं होता, अन्यथा यह स्पेस कॉम्प्लेक्सिटी बढ़ा सकती है।

काउंटिंग सॉर्ट तकनीक की जटिलता

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

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

इनपुट: अनसॉर्टेड डेटा की लिस्ट: 2 5 6 2 3 10 3 6 7 8
आउटपुट: सॉर्टिंग से पहले ऐरे: 2 5 6 2 3 10 3 6 7 8
सॉर्टिंग के बाद ऐरे: 2 2 3 3 5 6 6 7 8 10

एल्गोरिदम

countingSort(array, size)

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

Begin
    max = ऐरे से अधिकतम एलिमेंट प्राप्त करें
    साइज [max+1] का काउंट ऐरे परिभाषित करें
    for i := 0 to max do
        count[i] = 0 // काउंट ऐरे में सभी एलिमेंट्स को 0 पर सेट करें
    done
    for i := 1 to size do
        ऐरे में पाए गए प्रत्येक नंबर की काउंट बढ़ाएं
    done
    for i := 1 to max do
        count[i] = count[i] + count[i-1] // संचयी फ्रीक्वेंसी ढूंढें
    done
    for i := size to 1 decrease by 1 do
        आउटपुट ऐरे में नंबर स्टोर करें
        count[i] घटाएं
    done
    आउटपुट ऐरे वापस करें
End

उदाहरण

#include <iostream>
#include <algorithm>
using namespace std;

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

int getMax(int array[], int size) {
    int max = array[1];
    for(int i = 2; i <= size; i++) {
        if(array[i] > max)
            max = array[i];
    }
    return max; // ऐरे से मैक्स एलिमेंट
}

void countSort(int *array, int size) {
    int output[size + 1];
    int max = getMax(array, size);
    int count[max + 1]; // काउंट ऐरे बनाएं (max+1 एलिमेंट्स)
    for(int i = 0; i <= max; i++)
        count[i] = 0; // काउंट ऐरे को ऑल जीरो से इनिशियलाइज़ करें
    for(int i = 1; i <= size; i++)
        count[array[i]]++; // काउंट ऐरे में नंबर काउंट बढ़ाएं
    for(int i = 1; i <= max; i++)
        count[i] += count[i - 1]; // संचयी फ्रीक्वेंसी ढूंढें
    for(int i = size; i >= 1; i--) {
        output[count[array[i]]] = array[i];
        count[array[i]] -= 1; // समान नंबर्स के लिए काउंट घटाएं
    }
    for(int i = 1; i <= size; i++) {
        array[i] = output[i]; // आउटपुट ऐरे को मेन ऐरे में स्टोर करें
    }
}

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

आउटपुट

एलिमेंट्स की संख्या दर्ज करें: 10
एलिमेंट्स दर्ज करें: 2 5 6 2 3 10 3 6 7 8
सॉर्टिंग से पहले ऐरे: 2 5 6 2 3 10 3 6 7 8
सॉर्टिंग के बाद ऐरे: 2 2 3 3 5 6 6 7 8 10