एक तेज़, रैंक आधारित रैडिक्स फ्लोट के लिए सॉर्ट करें?

Question

मैं एक तेज़ स्थिर रेडिक्स सॉर्ट कार्यान्वयन (फ्लोट्स के समर्थन के साथ) की तलाश कर रहा हूं जो सॉर्ट किए गए मानों के बजाय क्रमबद्ध क्रम के सूचकांक लौटाता है।

पियरे Terdiman के अपने लेख "Radix Sort Revisited" से संस्करण वास्तव में क्या करता है मैं फिर भी चाहते हैं कि उसे और अधिक से अधिक 13 साल है, और आधुनिक pipelined CPU के लिए उपयुक्त नहीं है।

माइकल Herf के RadixSort11 "Radix Tricks" से बहुत तेजी से है, केवल समस्या यह है कि सूचकांक के बजाय क्रमबद्ध मान देता है, इसके अलावा यह इनपुट सरणी के मूल्यों भ्रष्ट।

किसी भी मदद की सराहना की जाएगी।

Answer 1

आप या तो

1. अपने मूल सूचकांक (यह पहली गिनती पास के दौरान किया जा सकता है) शामिल करने के लिए प्रत्येक आइटम का विस्तार कर सकते हैं। बेशक, सॉर्टिंग उद्देश्यों के लिए इंडेक्स अंकों को अनदेखा किया जाता है।

2. मूल्यों के बजाय बाल्टी में सूचकांक स्टोर करें। प्रत्येक बार अंकों की आवश्यकता होने पर मान को देखो।

पहले स्थान लेता है लेकिन संदर्भ में बेहतर इलाका है, दूसरा स्थान बचाता है।

Answer 2

यह किसी भी प्रकार की अनुक्रमणिका आधारित बनाने के लिए काफी सीधे है। कोई भी प्रकार तुलना और स्वैप की श्रृंखला है, इसलिए ऐसा करें।

// data to be sorted is in data[ 0 .. n ] 
int index[ n + 1 ]; 
for(int i = 0; i <= n; i++) index[i] = i; 
// To compare data, compare data[index[j]] < data[index[k]] 
// To swap values, swap index[j] <=> index[k] 

Answer 3

मैं उन कार्यान्वयन से परिचित नहीं हूँ, लेकिन यहाँ केवल पूर्णांकों के लिए, मेरे कार्यान्वयन में से एक में आंतरिक समारोह है:

//------------------------------------------------------------------------------------- 
//! sort the source array based on b-th byte and store the result in destination array 
//! and keep index (how to go from the sorted array to the un-sorted) 

template<typename T, typename SS, typename SD> inline 
void radix_sort_byte(size_t b, array<T, SS>& src, array<T, SD>& dest, 
      size_array& ind_src, size_array& ind_dest) 
{ 
    b *= 8; 
    size_t B = 256, N = src.size(); 

    size_array bytes = (src >> b) & 0xff; // current byte of each element 
    size_array count(B, size_t(0)); // occurrences of each element 
    ++count[bytes]; 

    if(count[0] == N) // all bytes are zero; order remains unchanged 
     { dest = src; ind_dest = ind_src; return; } 

    size_array index = shift(cumsum(count), 1); // index-list for each element 
    size_array pos(N); // position of each element in the destination array 
    for(size_t i=0; i<N; i++) pos[i] = index[bytes[i]]++; 

    dest[pos] = src; // place elements in the destination array 
    ind_dest[pos] = ind_src; // place indices 
} 

यह सीधे पठनीय है क्योंकि यह सहायक संरचनाओं और कार्यों के बहुत सारे का उपयोग करता है नहीं है, लेकिन विचार यह है कि आप सूचकांक के साथ एक अलग सरणी रखते हैं। एक बार आपके पास गंतव्य सरणी (pos) में तत्वों की स्थिति हो जाने के बाद, अंतिम दो पंक्तियां वैल्यू सरणी और इंडेक्स सरणी को उसी तरह अद्यतन करती हैं।

मुझे लगता है कि आप किसी भी कार्यान्वयन के लिए एक ही विचार लागू कर सकते हैं, लेकिन आपको कोड को संशोधित करना होगा।