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

मूलांक छँटाई गैर-तुलनात्मक छँटाई एल्गोरिथ्म है। यह सॉर्टिंग एल्गोरिदम समान स्थिति और मान साझा करने वाले अंकों को समूहीकृत करके पूर्णांक कुंजियों पर काम करता है। मूलांक एक संख्या प्रणाली का आधार है। जैसा कि हम जानते हैं कि दशमलव प्रणाली में मूलांक या आधार 10 होता है। इसलिए कुछ दशमलव संख्याओं को छांटने के लिए, हमें संख्याओं को संग्रहीत करने के लिए 10 स्थितीय बॉक्स की आवश्यकता होती है।

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

• समय जटिलता:ओ (एनके)

• अंतरिक्ष जटिलता:O(n+k)

Input − The unsorted list: 802 630 20 745 52 300 612 932 78 187
Output − Data after Sorting: 20 52 78 187 300 612 630 745 802 932

एल्गोरिदम

radixSort(array, size, maxDigit)

इनपुट :डेटा की एक सरणी, और सरणी में कुल संख्या, अधिकतम संख्या की अंकों की संख्या।

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

Begin
   define 10 lists as pocket
   for i := 0 to max -1 do
      m = 10i+1
      p := 10i
      for j := 0 to n-1 do
      temp := array[j] mod m
      index := temp / p
      pocket[index].append(array[j])
   done
   count := 0
   for j := 0 to radix do
      while pocket[j] is not empty
         array[count] := get first node of pocket[j] and delete it
         count := count +1
      done
   done
End

उदाहरण कोड

#include<iostream>
#include<list>
#include<cmath>
using namespace std;
void display(int *array, int size) {
   for(int i = 0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}
void radixSort(int *arr, int n, int max) {
   int i, j, m, p = 1, index, temp, count = 0;
   list<int> pocket[10];      //radix of decimal number is 10
   for(i = 0; i< max; i++) {
      m = pow(10, i+1);
      p = pow(10, i);
      for(j = 0; j<n; j++) {
         temp = arr[j]%m;
         index = temp/p;      //find index for pocket array
         pocket[index].push_back(arr[j]);
      }
      count = 0;
      for(j = 0; j<10; j++) {
         //delete from linked lists and store to array
         while(!pocket[j].empty()) {
            arr[count] = *(pocket[j].begin());
            pocket[j].erase(pocket[j].begin());
            count++;
         }
      }
   }
}
int main() {
   int n, max;
   cout << "Enter the number of elements: ";
   cin >> n;
   cout << "Enter the maximum digit of elements: ";
   cin >> max;
   int arr[n]; //create an array with given number of elements
   cout << "Enter elements:" << endl;
   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }
   cout << "Data before Sorting: ";
   display(arr, n);
   radixSort(arr, n, max);
   cout << "Data after Sorting: ";
   display(arr, n);
}

आउटपुट

Enter the number of elements: 10
Enter the maximum digit of elements: 3
Enter elements:
802 630 20 745 52 300 612 932 78 187
Data before Sorting: 802 630 20 745 52 300 612 932 78 187
Data after Sorting: 20 52 78 187 300 612 630 745 802 932