इस ट्यूटोरियल में, आप सीखेंगे कि किस तरह से गिनती काम करती है। इसके अलावा, आपको C, C ++, Java और पायथन में गिनती के काम के उदाहरण मिलेंगे।
काउंटिंग सॉर्ट एक छँटाई एल्गोरिथ्म है जो सरणी में प्रत्येक अद्वितीय तत्व की घटनाओं की संख्या की गणना करके एक सरणी के तत्वों को सॉर्ट करता है। गिनती सहायक सरणी में संग्रहीत की जाती है और सहायक सरणी के सूचकांक के रूप में गणना को मैप करके छँटाई की जाती है।
कैसे काम करता है?
maxदिए गए सरणी से अधिकतम तत्व (इसे रहने दें ) का पता लगाएं ।
दिए गए सरणीmax+1सभी तत्वों के साथ लंबाई की एक सरणी को आरम्भ करें । यह सरणी में तत्वों की गिनती को संग्रहीत करने के लिए उपयोग किया जाता है।
काउंट ऐरे- प्रत्येक तत्व की गिनती को उनके संबंधित सूचकांक में
countसरणी में स्टोर करें
उदाहरण के लिए: यदि तत्व 3 की गिनती 2 है, तो 2 को गिनती सरणी के तीसरे स्थान पर संग्रहीत किया जाता है। यदि तत्व "5" सरणी में मौजूद नहीं है, तो 0 को 5 वें स्थान पर संग्रहीत किया जाता है।
संग्रहीत प्रत्येक तत्व की गणना - गिनती सरणी के तत्वों का संचयी योग करें। यह तत्वों को क्रमबद्ध सरणी के सही सूचकांक में रखने में मदद करता है।
संचयी गिनती - गिनती सरणी में मूल सरणी के प्रत्येक तत्व के सूचकांक का पता लगाएं। यह संचयी गिनती देता है। नीचे दी गई आकृति में दिखाए गए अनुसार सूचकांक पर तत्व को रखें।
गिनती की तरह - प्रत्येक तत्व को उसकी सही स्थिति पर रखने के बाद, उसकी गिनती को एक घटा दें।
काउंटिंग अलगोरिथम
CountSort (सरणी, आकार) अधिकतम <- सरणी में सबसे बड़ा तत्व ढूंढें सभी के लिए शून्य के साथ गणना सरणी को आरम्भ करें <- 0 आकार के लिए प्रत्येक अद्वितीय तत्व की कुल संख्या का पता लगाएं और गिनती सरणी में jth सूचकांक में गिनती को <i - 1 के लिए स्टोर करें अधिकतम करने के लिए संचयी योग को खोजने और गणना सरणी में इसे जम्मू के लिए ही स्टोर करें <- 1 को आकार दें 1 को बहाल करने वाले तत्वों की संख्या को कम करने के लिए तत्वों को पुनर्स्थापित करें 1
पायथन, जावा और सी / सी ++ उदाहरण
पायथन जावा सी सी ++ # Counting sort in Python programming def countingSort(array): size = len(array) output = (0) * size # Initialize count array count = (0) * 10 # Store the count of each elements in count array for i in range(0, size): count(array(i)) += 1 # Store the cummulative count for i in range(1, 10): count(i) += count(i - 1) # Find the index of each element of the original array in count array # place the elements in output array i = size - 1 while i>= 0: output(count(array(i)) - 1) = array(i) count(array(i)) -= 1 i -= 1 # Copy the sorted elements into original array for i in range(0, size): array(i) = output(i) data = (4, 2, 2, 8, 3, 3, 1) countingSort(data) print("Sorted Array in Ascending Order: ") print(data)
// Counting sort in Java programming import java.util.Arrays; class CountingSort ( void countSort(int array(), int size) ( int() output = new int(size + 1); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); // Initialize count array with all zeros. for (int i = 0; i < max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Driver code public static void main(String args()) ( int() data = ( 4, 2, 2, 8, 3, 3, 1 ); int size = data.length; CountingSort cs = new CountingSort(); cs.countSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Counting sort in C programming #include void countingSort(int array(), int size) ( int output(10); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) // The size of count must be at least (max+1) but // we cannot declare it as int count(max+1) in C as // it does not support dynamic memory allocation. // So, its size is provided statically. int count(10); // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countingSort(array, n); printArray(array, n); )
// Counting sort in C++ programming #include using namespace std; void countSort(int array(), int size) ( // The size of count must be at least the (max+1) but // we cannot assign declare it as int count(max+1) in C++ as // it does not support dynamic memory allocation. // So, its size is provided statically. int output(10); int count(10); int max = array(0); // Find the largest element of the array for (int i = 1; i max) max = array(i); ) // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countSort(array, n); printArray(array, n); )
जटिलता
समय जटिलताएं:
मुख्य रूप से चार मुख्य छोर हैं। (सबसे बड़ी कीमत ढूँढना समारोह के बाहर किया जा सकता है।)
| पाश के लिए | मतगणना का समय |
|---|---|
| पहली बार | ओ (अधिकतम) |
| 2 रा | ओ (आकार) |
| ३ | ओ (अधिकतम) |
| ४ था | ओ (आकार) |
समग्र जटिलता = O(max)+O(size)+O(max)+O(size)=O(max+size)
- सबसे खराब मामला जटिलता:
O(n+k) - सर्वश्रेष्ठ मामले की जटिलता:
O(n+k) - औसत केस जटिलता:
O(n+k)
उपरोक्त सभी मामलों में, जटिलता समान है क्योंकि तत्वों को सरणी में कैसे रखा जाता है, कोई फर्क नहीं पड़ता, एल्गोरिथ्म n+kकई बार गुजरता है।
किसी भी तत्व के बीच कोई तुलना नहीं है, इसलिए यह तुलना आधारित छंटाई तकनीकों से बेहतर है। लेकिन, यह बुरा है अगर पूर्णांक बहुत बड़े हैं, क्योंकि उस आकार का सरणी बनाया जाना चाहिए।
अंतरिक्ष जटिलता:
काउंटिंग सॉर्ट की अंतरिक्ष जटिलता है O(max)। तत्वों की सीमा से बड़ा, अंतरिक्ष की जटिलता है।
क्रमबद्ध अनुप्रयोगों की गिनती
जब प्रकार की गणना का उपयोग किया जाता है:
- कई संख्याओं के साथ छोटे पूर्णांक होते हैं।
- रैखिक जटिलता की आवश्यकता है।
