रेडिक्स सॉर्ट गैर-तुलनात्मक सॉर्टिंग एल्गोरिदम है। यह सॉर्टिंग एल्गोरिदम पूर्णांक कुंजियों पर काम करता है उन अंकों को समूहित करके जो समान स्थिति और मान साझा करते हैं। रेडिक्स एक संख्या प्रणाली का आधार है। जैसा कि हम जानते हैं कि दशमलव प्रणाली में रेडिक्स या आधार 10 है। इसलिए कुछ दशमलव संख्याओं को सॉर्ट करने के लिए, हमें संख्याओं को संग्रहीत करने के लिए 10 स्थितिगत बॉक्स की आवश्यकता होती है।
रेडिक्स सॉर्ट तकनीक की जटिलता
समय जटिलता: O(nk)
स्पेस जटिलता: O(n+k)
इनपुट − असॉर्टेड सूची: 802 630 20 745 52 300 612 932 78 187 आउटपुट − सॉर्टिंग के बाद डेटा: 20 52 78 187 300 612 630 745 802 932
एल्गोरिदम
radixSort(array, size, maxDigit)
इनपुट: डेटा की एक सरणी, और सरणी में कुल संख्या, अधिकतम संख्या का अंक गणना।
आउटपुट: क्रमबद्ध सरणी।
शुरुआत 10 सूचियों को पॉकेट के रूप में परिभाषित करें i := 0 से max -1 तक करें m = 10i+1 p := 10i j := 0 से n-1 तक करें temp := array[j] मॉड m index := temp / p pocket[index].append(array[j]) हो गया count := 0 j := 0 से रेडिक्स तक करें जब तक pocket[j] खाली नहीं है array[count] := pocket[j] का पहला नोड प्राप्त करें और इसे हटाएं count := count +1 हो गया हो गया अंत
उदाहरण कोड
#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]; //दशमलव संख्या का रेडिक्स 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; //पॉकेट सरणी के लिए सूचकांक ढूंढें pocket[index].push_back(arr[j]); } count = 0; for(j = 0; j<10; j++) { //लिंक्ड सूचियों से हटाएं और सरणी में संग्रहीत करें while(!pocket[j].empty()) { arr[count] = *(pocket[j].begin()); pocket[j].erase(pocket[j].begin()); count++; } } } } int main() { int n, max; cout << "तत्वों की संख्या दर्ज करें: "; cin >> n; cout << "तत्वों के अधिकतम अंक दर्ज करें: "; cin >> max; int arr[n]; //दिए गए तत्वों की संख्या के साथ एक सरणी बनाएं cout << "तत्व दर्ज करें:" << endl; for(int i = 0; i<n; i++) { cin >> arr[i]; } cout << "सॉर्टिंग से पहले डेटा: "; display(arr, n); radixSort(arr, n, max); cout << "सॉर्टिंग के बाद डेटा: "; display(arr, n); }
आउटपुट
तत्वों की संख्या दर्ज करें: 10 अधिकतम अंक दर्ज करें: 3 तत्व दर्ज करें: 802 630 20 745 52 300 612 932 78 187 सॉर्टिंग से पहले डेटा: 802 630 20 745 52 300 612 932 78 187 सॉर्टिंग के बाद डेटा: 20 52 78 187 300 612 630 745 802 932
