O(n) जटिलता में 100 से कम संख्याओं की छँटाई को लागू करने के लिए C++ कार्यक्रम

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

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

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

• समय की जटिलता :ओ(एन + आर)

• अंतरिक्ष जटिलता :ओ(एन + आर)

Input − A list of unsorted data: 2 5 6 2 3 10 3 6 7 8
Output − Array after Sorting: 2 2 3 3 5 6 6 7 8 10

एल्गोरिदम

काउंटिंगसॉर्ट (सरणी, आकार)

इनपुट - डेटा की एक सरणी, और सरणी में कुल संख्या

आउटपुट - क्रमबद्ध सरणी

Begin
   max = get maximum element from array.
   define count array of size [max+1]
   for i := 0 to max do
      count[i] = 0 //set all elements in the count array to 0
   done
   for i := 1 to size do
      increase count of each number which have found in the array
   done
   for i := 1 to max do
      count[i] = count[i] + count[i + 1] //find cumulative frequency
   done
   for i := size to 1 decrease by 1 do
      store the number in the output array
      decrease count[i]
   done
   return the output array
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