डेटा संरचना में रेडिक्स सॉर्ट एल्गोरिथ्म

रेडिक्स सॉर्ट एल्गोरिथ्म क्या है?

रेडिक्स सॉर्ट एक गैर-तुलनात्मक सॉर्टिंग एल्गोरिदम है। यह सॉर्ट किए जाने वाले तत्वों के अलग-अलग अंकों को समूहीकृत करके काम करता है। फिर तत्वों को उनके रेडिक्स के आधार पर व्यवस्थित करने के लिए एक स्थिर सॉर्टिंग तकनीक का उपयोग किया जाता है। यह एक रैखिक सॉर्टिंग एल्गोरिदम है।

छंटाई प्रक्रिया में निम्नलिखित गुण शामिल हैं:

• अधिकतम तत्व ढूँढना और उस तत्व के अंकों की संख्या प्राप्त करना। यह हमें सॉर्टिंग प्रक्रिया में होने वाली पुनरावृत्तियों की संख्या बताता है।
• प्रत्येक पुनरावृत्ति में तत्वों के अलग-अलग अंकों को समान सार्थक स्थान पर समूहित करें।
• समूहीकरण प्रक्रिया सबसे कम महत्वपूर्ण अंक से शुरू होगी और सबसे महत्वपूर्ण अंक पर समाप्त होगी।
• महत्वपूर्ण स्थान पर अंकों के आधार पर तत्वों को क्रमबद्ध करना।
• समान कुंजी मान वाले तत्वों के सापेक्ष क्रम को बनाए रखना। रेडिक्स सॉर्ट का यह गुण इसे एक स्थिर सॉर्ट बनाता है।

अंतिम पुनरावृत्ति हमें पूर्णतः क्रमबद्ध सूची देगी।

रेडिक्स सॉर्ट एल्गोरिथ्म का कार्य

आइए रेडिक्स सॉर्ट एल्गोरिथ्म का उपयोग करके उपरोक्त चित्र में पूर्णांकों की सूची को आरोही क्रम में सॉर्ट करने का प्रयास करें।

रेडिक्स सॉर्टिंग प्रक्रिया करने के लिए निम्नलिखित चरण हैं:

चरण 1) सूची में अधिकतम मान वाले तत्व की पहचान करें। इस मामले में, यह 835 है।

चरण 2) अधिकतम तत्व के अंकों की संख्या की गणना करें। 835 में ठीक 3 अंक हैं।

चरण 3) चरण 2 के आधार पर पुनरावृत्तियों की संख्या निर्धारित करें। 835 में 3 अंक हैं, अर्थात पुनरावृत्तियों की संख्या 3 होगी।

चरण 4) तत्वों का आधार निर्धारित करें: चूंकि यह दशमलव प्रणाली है, इसलिए आधार 10 होगा।

चरण 5) प्रथम पुनरावृति प्रारंभ करें.

क) प्रथम पुनरावृत्ति

प्रथम पुनरावृत्ति में, हम प्रत्येक तत्व के इकाई स्थानीय मान पर विचार करते हैं।

चरण 1) तत्वों का इकाई स्थान प्राप्त करने के लिए पूर्णांक को 10 से मॉड करें। उदाहरण के लिए, 623 मॉड 10 हमें 3 का मान देता है, और 248 मॉड 10 हमें 8 देता है।

चरण 2) पूर्णांकों को उनके सबसे कम महत्वपूर्ण अंक के अनुसार व्यवस्थित करने के लिए गिनती सॉर्ट या किसी अन्य स्थिर सॉर्ट का उपयोग करें। जैसा कि चित्र से देखा जा सकता है, 248 8वीं बाल्टी में आएगा। 623 तीसरी बाल्टी में आएगा और इसी तरह आगे भी।

प्रथम पुनरावृत्ति के बाद, सूची अब इस प्रकार दिखती है।

जैसा कि आप ऊपर दिए गए चित्र में देख सकते हैं, सूची अभी तक क्रमबद्ध नहीं हुई है तथा इसे पूरी तरह क्रमबद्ध करने के लिए और अधिक प्रयास की आवश्यकता है।

बी) दूसरा पुनरावृति

इस पुनरावृत्ति में, हम 10वें स्थान के अंक पर विचार करेंगे^th छंटाई प्रक्रिया के लिए स्थान.

चरण 1) पूर्णांकों को 10 से भाग दें। 248 को 10 से भाग देने पर 24 प्राप्त होता है।

चरण 2) चरण 1 के आउटपुट को 10 से मॉड करें। 24 मॉड 10 हमें 4 देता है।

चरण 3) पिछले चरण के चरण 2 का अनुसरण करें।

दूसरे पुनरावृति के बाद, सूची अब इस तरह दिखती है

आप ऊपर दिए गए चित्र से देख सकते हैं कि सूची अभी भी पूरी तरह से क्रमबद्ध नहीं हुई है क्योंकि यह अभी भी आरोही क्रम में नहीं है।

ग) तीसरा पुनरावर्तन

अंतिम पुनरावृत्ति के लिए, हम सबसे महत्वपूर्ण अंक प्राप्त करना चाहते हैं। इस मामले में, यह 100 है^th सूची में प्रत्येक पूर्णांक के लिए स्थान.

चरण 1) पूर्णांकों को 100 से विभाजित करें... 415 को 100 से विभाजित करने पर 4 प्राप्त होता है।

चरण 2) चरण 1 के परिणाम को 10 से संशोधित करें। 4 को 10 से संशोधित करने पर हमें पुनः 4 प्राप्त होता है।

चरण 3) पिछले चरण के चरण 3 का अनुसरण करें।

जैसा कि हम देख सकते हैं, सूची अब आरोही क्रम में क्रमबद्ध है। अंतिम पुनरावृत्ति पूरी हो गई है, और अब सॉर्टिंग प्रक्रिया समाप्त हो गई है।

रेडिक्स सॉर्ट एल्गोरिथ्म का छद्म कोड

यहां रेडिक्स सॉर्ट एल्गोरिथ्म के लिए छद्म कोड दिया गया है

radixSortAlgo(arr as an array)
  Find the largest element in arr
  maximum=the element in arr that is the largest
  Find the number of digits in maximum
  k=the number of digits in maximum 
  Create buckets of size 0-9 k times
for j -> 0 to k
  Acquire the jth place of each element in arr. Here j=0 represents the least significant digit.
  Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits of the elements in the jthplace
   arr = sorted elements

C++ रेडिक्स सॉर्ट को लागू करने का कार्यक्रम

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
  int maximum = arr[0];
  for (int i = 1; i < n; i++) {
    if (maximum < arr[i]) maximum = arr[i];
  }
  return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
  const int limit = 10;
  int result[size];
  int count[limit] = {0};
  // Calculating the count of each integers
  for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
  // Calculating the cumulative count
  for (int j = 1; j < limit; j++) {
    count[j] += count[j - 1];
  }
  // Sort the integers
  for (int j = size - 1; j >= 0; j--) {
    result[count[(arr[j] / position) % 10] - 1] = arr[j];
    count[(arr[j] / position) % 10]--;
  }
  for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
  // Get the largest element in the array
  int maximum = getMaximum(arr, size);
  for (int position = 1; maximum / position > 0; position *= 10)
    countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
int main() {
  int arr[] = {162, 623, 835, 415, 248};
  int size = sizeof(arr) / sizeof(arr[0]);
  radixSortAlgo(arr, size);
  printResult(arr, size);
}

आउटपुट:

162 248 415 623 835

Python रेडिक्स सॉर्ट एल्गोरिथ्म के लिए कार्यक्रम

#Radix Sort using python
def countingSortAlgo(arr, position):
    n = len(arr)
    result = [0] * n
    count = [0] * 10  # Calculating the count of elements in the array arr
    for j in range(0, n):
        element = arr[j] // position
        count[element % 10] += 1  # Calculating the cumulative count
    for j in range(1, 10):
        count[j] += count[j - 1]  # Sorting the elements
    i = n - 1
    while i >= 0:
        element = arr[i] // position
        result[count[element % 10] - 1] = arr[i]
        count[element % 10] -= 1
        i -= 1
    for j in range(0, n):
        arr[j] = result[j]


def radixSortAlgo(arr):  # Acquiring the largest element in the array
    maximum = max(arr)  # Using counting sort to sort digit by digit
    position = 1
    while maximum // position > 0:
        countingSortAlgo(arr, position)
        position *= 10


input = [162, 623, 835, 415, 248]
radixSortAlgo(input)
print(input)

आउटपुट:

[162,248,415,623,835]

रेडिक्स सॉर्ट का जटिलता विश्लेषण

विचारणीय जटिलता के दो प्रकार हैं, स्थान जटिलता और समय जटिलता।

• स्थान जटिलता: O(n+b) जहां n सारणी का आकार है और b आधार माना गया है।
• समय जटिलता: O(d*(n+b)) जहाँ d सारणी में सबसे बड़े तत्व के अंकों की संख्या है।

रेडिक्स सॉर्ट की स्पेस जटिलता

अंतरिक्ष जटिलता पर ध्यान देने योग्य दो विशेषताएं

• सारणी में तत्वों की संख्या, n.
• तत्वों को दर्शाने का आधार, b.

कभी-कभी यह आधार सरणी के आकार से बड़ा हो सकता है।

इस प्रकार समग्र जटिलता O(n+b) है।

सूची में तत्वों के निम्नलिखित गुण रेडिक्स सॉर्ट स्पेस को अकुशल बना सकते हैं:

• बड़ी संख्या में अंकों वाले तत्व.
• तत्वों का आधार बड़ा है, 64-बिट संख्याओं जैसा।

रेडिक्स सॉर्ट की समय जटिलता

आप गिनती सॉर्ट को सबरूटीन के रूप में उपयोग कर सकते हैं, क्योंकि प्रत्येक पुनरावृत्ति में समय लगेगाई ओ(एन+बी) समय। यदि d पुनरावृत्तियाँ मौजूद हैं, तो कुल चलने का समय बन जाता है ओ(डी*(एन+बी)). यहाँ, “O” का अर्थ जटिलता फ़ंक्शन है।

रेडिक्स सॉर्ट की रैखिकता

रेडिक्स सॉर्ट रैखिक होता है जब

• d स्थिर है, जहाँ d सबसे बड़े तत्व के अंकों की संख्या है।
• b की तुलना में बहुत हद तक बड़ा नहीं है n.

अन्य तुलनात्मक एल्गोरिदम के साथ रेडिक्स सॉर्ट की तुलना

जैसा कि हमने देखा है, रेडिक्स सॉर्ट की जटिलता एक शब्द या संख्या के आकार पर आधारित होती है। औसत और सर्वोत्तम मामलों के लिए इसकी जटिलता समान होगी। और वह O(d*(n+b)) है। साथ ही, यह बीच में आपके द्वारा उपयोग की जाने वाली सॉर्टिंग तकनीक के अनुसार भिन्न होता है। उदाहरण के लिए, आप रेडिक्स सॉर्ट के अंदर मध्यवर्ती सॉर्टिंग एल्गोरिदम के लिए काउंटिंग सॉर्ट या क्विक सॉर्ट का उपयोग कर सकते हैं।

रेडिक्स सॉर्ट एल्गोरिथ्म के अनुप्रयोग

रेडिक्स सॉर्ट के महत्वपूर्ण अनुप्रयोग हैं:

• रेडिक्स सॉर्ट का उपयोग स्थान खोजने वाले एल्गोरिदम के रूप में किया जा सकता है जहां मानों की बड़ी रेंज का उपयोग किया जाता है।
• इसका उपयोग DC3 एल्गोरिथम में प्रत्यय सरणी के निर्माण में किया जाता है।
• इसका उपयोग एक अनुक्रमिक, यादृच्छिक-पहुंच मशीन में किया जाता है जो एक विशिष्ट कंप्यूटर में मौजूद होती है, जहां रिकॉर्ड को कुंजीबद्ध किया जाता है।