C++ प्रोग्राम: 100 से कम संख्याओं को O(n) कॉम्प्लेक्सिटी में सॉर्ट करना

कुछ छोटी संख्याओं को रैखिक समय में सॉर्ट करने के लिए हम काउंटिंग सॉर्ट तकनीक का उपयोग कर सकते हैं।

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

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

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

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

इनपुट - अनसॉर्टेड डेटा की लिस्ट: 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] का काउंट ऐरे परिभाषित करें
    i := 0 से max तक करें
        count[i] = 0 // काउंट ऐरे के सभी एलिमेंट्स को 0 पर सेट करें
    किया
    i := 1 से size तक करें
        ऐरे में मिली प्रत्येक संख्या की काउंट बढ़ाएं
    किया
    i := 1 से max तक करें
        count[i] = count[i] + count[i + 1] // संचयी फ्रीक्वेंसी ढूंढें
    किया
    i := size से 1 तक 1 से घटाते हुए करें
        आउटपुट ऐरे में नंबर स्टोर करें
        count[i] घटाएं
    किया
    आउटपुट ऐरे लौटाएं
End

उदाहरण कोड

#include <iostream>
using namespace std;

void counting_sort(int array[], int n) {
    int i, j;
    int count[n];
    for (i = 0; i < n; i++)
        count[i] = 0;
    for (i = 0; i < n; i++)
        (count[array[i]])++;
    for (i = 0, j = 0; i < n; i++)
        for (; count[i] > 0; (count[i])--)
            array[j++] = i;
}

int main() {
    int array[100], i, num;
    cout << "Enter the size of array : ";
    cin >> num;
    cout << "Enter the " << num << " elements to be sorted:" << endl;
    for (i = 0; i < num; i++)
        cin >> array[i];
    cout << "\nThe array of elements before sorting : " << endl;
    for (i = 0; i < num; i++)
        cout << array[i] << " ";
    cout << "\nThe array of elements after sorting : " << endl;
    counting_sort(array, num);
    for (i = 0; i < num; i++)
        cout << array[i] << " ";
    return 0;
}

आउटपुट

Enter the size of array : 8
Enter the 8 elements to be sorted: 54 89 23 20 18 88 65 31
The array of elements before sorting : 54 89 23 20 18 88 65 31
The array of elements after sorting : 54 89 23 20 18 88 65 31