आकार एन

Question

की सॉर्ट सरणी यदि आकार एन की एक सरणी में केवल 3 मान 0, 1 और 2 (किसी भी बार दोहराया गया है) उन्हें सॉर्ट करने का सबसे अच्छा तरीका क्या है। सबसे अच्छा जटिलता इंगित करता है। स्थान और समय जटिलता दोनों

Answer 1

पर विचार प्रत्येक संख्या का आवृत्तियां गणना और बाद में सही मायने रखता है के साथ सरणी को भरने, इस O(n)

Answer 2

ध्वनि डिज्कस्ट्रा के डच राष्ट्रीय ध्वज समस्या की तरह एक बहुत कुछ है।

आप एक समाधान है कि उनकी गिनती का उपयोग नहीं करता की जरूरत है, बाहर की जाँच http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

Answer 3

Untested सी शैली समाधान:

int count[3] = {0, 0, 0}; 

for (int i = 0; i < n; ++i) 
    ++count[array[i]]; 

int pos = 0; 
for (int c = 0; c < 3; ++c) 
    for (int i = array[c]; i; --i) 
     array[pos++] = c; 

Answer 4

हास्केल दो लाइनर:

count xs = Map.toList $ Map.fromListWith (+) [ (x, 1) | x <- xs ] 

countingSort xs = concatMap (\(x, n) -> replicate n x) (count xs) 

> countingSort [2,0,2,1,2,2,1,0,2,1] 
[0,0,1,1,1,2,2,2,2,2]