C++ प्रोग्राम काउंटिंग सॉर्ट को लागू करने के लिए

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

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

• समय जटिलता: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

एल्गोरिदम

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

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

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

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>
#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; //the max element from the array
}
void countSort(int *array, int size) {
   int output[size+1];
   int max = getMax(array, size);
   int count[max+1];     //create count array (max+1 number of elements)
   for(int i = 0; i<=max; i++)
      count[i] = 0;     //initialize count array to all zero
   for(int i = 1; i <=size; i++)
      count[array[i]]++;     //increase number count in count array.
   for(int i = 1; i<=max; i++)
      count[i] += count[i-1];     //find cumulative frequency
   for(int i = size; i>=1; i--) {
      output[count[array[i]]] = array[i];
      count[array[i]] -= 1; //decrease count for same numbers
   }
   for(int i = 1; i<=size; i++) {
      array[i] = output[i]; //store output array to main array
   }
}
int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n+1];       //create an array with given number of elements
   cout << "Enter elements:" << endl;
   for(int i = 1; i<=n; i++) {
      cin >> arr[i];
   }
   cout << "Array before Sorting: ";
   display(arr, n);
   countSort(arr, n);
   cout << "Array after Sorting: ";
   display(arr, n);
}

आउटपुट

Enter the number of elements: 10
Enter elements:
2 5 6 2 3 10 3 6 7 8
Array before Sorting: 2 5 6 2 3 10 3 6 7 8
Array after Sorting: 2 2 3 3 5 6 6 7 8 10