मूलांक सॉर्ट एल्गोरिथ्म

इस ट्यूटोरियल में, आप सीखेंगे कि मूलांक कैसे काम करता है। साथ ही, आपको C, C ++, Java और पायथन में मूलांक के प्रकार के काम के उदाहरण मिलेंगे।

रेडिक्स सॉर्ट एक सॉर्टिंग तकनीक है जो तत्वों को पहले उसी स्थान मान के अलग-अलग अंकों को समूहित करके सॉर्ट करती है । फिर, तत्वों को उनके बढ़ते / घटते क्रम के अनुसार क्रमबद्ध करें।

मान लीजिए, हमारे पास 8 तत्वों की एक सरणी है। सबसे पहले, हम यूनिट जगह के मूल्य के आधार पर तत्वों को सॉर्ट करेंगे। फिर, हम दसवें स्थान के मूल्य के आधार पर तत्वों को सॉर्ट करेंगे। यह प्रक्रिया अंतिम महत्वपूर्ण स्थान तक चलती है।

प्रारंभिक सरणी होने दें (121, 432, 564, 23, 1, 45, 788)। इसे मूलांक के अनुसार क्रमबद्ध किया गया है जैसा कि नीचे दिए गए चित्र में दिखाया गया है।

रेडिक्स सॉर्ट का कार्य करना

कृपया इस लेख को पढ़ने से पहले मतगणना क्रमांक से गुजरें क्योंकि मतगणना क्रमांक का उपयोग मूलांक छँटनी में एक मध्यवर्ती छाँटे के रूप में किया जाता है।

रेडिक्स कैसे काम करता है?

1. सरणी में सबसे बड़ा तत्व खोजें, अर्थात अधिकतम। आज्ञा देना Xअंकों की संख्या में हो max। Xगणना की जाती है क्योंकि हमें सभी तत्वों के सभी महत्वपूर्ण स्थानों से गुजरना पड़ता है।
   इस सरणी में (121, 432, 564, 23, 1, 45, 788), हमारे पास सबसे बड़ी संख्या 788 है। इसके 3 अंक हैं। इसलिए, लूप को सैकड़ों जगह (3 बार) तक जाना चाहिए।
2. अब, प्रत्येक महत्वपूर्ण स्थान पर एक-एक करके जाएँ।
   प्रत्येक महत्वपूर्ण स्थान पर अंकों को छाँटने के लिए किसी स्थिर छँटाई तकनीक का उपयोग करें। हमने इसके लिए काउंटिंग सॉर्ट का इस्तेमाल किया है।
   इकाई स्थान अंक ( X=0) के आधार पर तत्वों को क्रमबद्ध करें । इकाई जगह के आधार पर तत्वों को क्रमबद्ध करने के लिए गिनती का उपयोग करना
3. अब, दसियों स्थान पर अंकों के आधार पर तत्वों को क्रमबद्ध करें। दसवें स्थान पर आधारित तत्वों को क्रमबद्ध करें
4. अंत में, सैकड़ों स्थानों पर अंकों के आधार पर तत्वों को क्रमबद्ध करें। सैकड़ों स्थानों पर आधारित तत्वों को क्रमबद्ध करें

मूलांक सॉर्ट एल्गोरिथ्म

 radixSort (सरणी) d <- सबसे बड़े तत्व में अधिकतम संख्या के अंक d बाल्टी को आकार 0-9 के लिए बनाते हैं i - - 0 के लिए तत्वों को ith स्थान अंकों के अनुसार छांटकर गिनती का उपयोग करते हुए गिनते हैंअंतरराष्ट्रीयकरण (सरणी, घ) अधिकतम <- ढूँढें dth जगह तत्वों में से सबसे बड़ा तत्व j के लिए सभी शून्य के साथ गिनती सरणी को आरम्भ करता है - तत्वों के dth स्थान में प्रत्येक अद्वितीय अंक की कुल संख्या को खोजने के लिए आकार की गणना करें और i <- 1 से अधिकतम खोजने के लिए गिनती के सरणी में jth सूचकांक में गिनती को संग्रहीत करें संचयी राशि और इसे गणना सरणी में j के लिए ही स्टोर करें <- 1 से नीचे आकार दें 1 के लिए प्रत्येक तत्व की गणना में कमी करने के लिए तत्वों को पुनर्स्थापित करें

पायथन, जावा और सी / सी ++ उदाहरण

पायथन जावा सी सी ++

 # Radix sort in Python # Using counting sort to sort the elements in the basis of significant places def countingSort(array, place): size = len(array) output = (0) * size count = (0) * 10 # Calculate count of elements for i in range(0, size): index = array(i) // place count(index % 10) += 1 # Calculate cummulative count for i in range(1, 10): count(i) += count(i - 1) # Place the elements in sorted order i = size - 1 while i>= 0: index = array(i) // place output(count(index % 10) - 1) = array(i) count(index % 10) -= 1 i -= 1 for i in range(0, size): array(i) = output(i) # Main function to implement radix sort def radixSort(array): # Get maximum element max_element = max(array) # Apply counting sort to sort elements based on place value. place = 1 while max_element // place> 0: countingSort(array, place) place *= 10 data = (121, 432, 564, 23, 1, 45, 788) radixSort(data) print(data) 

 // Radix Sort in Java Programming import java.util.Arrays; class RadixSort ( // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int() output = new int(size + 1); int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i < size; i++) array(i) = output(i); ) // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Main function to implement radix sort void radixSort(int array(), int size) ( // Get maximum element int max = getMax(array, size); // Apply counting sort to sort elements based on place value. for (int place = 1; max / place> 0; place *= 10) countingSort(array, size, place); ) // Driver code public static void main(String args()) ( int() data = ( 121, 432, 564, 23, 1, 45, 788 ); int size = data.length; RadixSort rs = new RadixSort(); rs.radixSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Radix Sort in C Programming #include // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int output(size + 1); int max = (array(0) / place) % 10; for (int i = 1; i max) max = array(i); ) int count(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // 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() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )

 // Radix Sort in C++ Programming #include using namespace std; // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( const int max = 10; int output(size); int count(max); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i  = 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); ) 

जटिलता

चूंकि मूलांक सॉर्ट एक गैर-तुलनात्मक एल्गोरिथ्म है, इसलिए तुलनात्मक सॉर्टिंग एल्गोरिदम पर इसके फायदे हैं।

मूलांक सॉर्ट के लिए जो इंटरमीडिएट स्थिर सॉर्ट के रूप में काउंटिंग सॉर्ट का उपयोग करता है, समय जटिलता है O(d(n+k))।

यहाँ, dसंख्या चक्र है और O(n+k)गणना प्रकार की समय जटिलता है।

इस प्रकार, मूलांक सॉर्ट में रैखिक समय की जटिलता है जो O(nlog n)तुलनात्मक छँटाई एल्गोरिदम से बेहतर है ।

यदि हम बहुत बड़े अंकों की संख्या या 32-बिट और 64-बिट संख्या जैसे अन्य आधारों की संख्या लेते हैं तो यह रैखिक समय में प्रदर्शन कर सकता है, हालांकि मध्यवर्ती सॉर्ट बड़ी जगह लेता है।

यह मूलांक छाँटने की जगह को अक्षम बनाता है। यही कारण है कि सॉफ्टवेयर पुस्तकालयों में इस प्रकार का उपयोग नहीं किया जाता है।

मूलांक सॉर्ट एप्लीकेशन

रेडिक्स सॉर्ट में लागू किया गया है

• DC3 एल्गोरिथ्म (Kärkkäinen-Sanders-Burkhardt) एक प्रत्यय सरणी बनाते हुए।
• ऐसी जगहें जहां बड़ी रेंज में नंबर हैं।