रैखिक समय और निरंतर स्थान

Question

में पहले एन पूर्णांक क्रमबद्ध करें मैं एक गैर-तुलना या तुलना आधारित एल्गोरिदम की तलाश में हूं जो पहले एन पॉजिटिव पूर्णांक के किसी भी क्रमपरिवर्तन वाले सरणी को सॉर्ट कर सकता है, जो ओ (एन) समय जटिलता होनी चाहिए और ओ (1) अंतरिक्ष जटिलता।

क्या कोई मौजूदा एल्गोरिदम है जो इन विनिर्देशों को फिट करता है?

Answer 1

यदि आपके पास 1 से एन उपस्थिति के सभी पूर्णांक के साथ आकार एन की एक सरणी है, तो आप निम्न ओ (एन) एल्गोरिदम का उपयोग कर सकते हैं (नोट: सरणी इस छद्म कोड के लिए 1 आधारित हैं ताकि अनावश्यक परिचय न दें एल्गोरिदम समझाते समय जटिलता):

1. पहले सरणी तत्व पर प्रारंभ करें।
   
2. यदि इसकी सरणी अनुक्रमणिका इसके मूल्य से मेल खाती है, तो अगले पर जाएं।
   
3. यदि नहीं, तो इसे अपने मान के अनुरूप सरणी अनुक्रमणिका में मान के साथ स्वैप करें।
   
4. चरण 3 दोहराएं, जब तक कि कोई और स्वैप आवश्यक न हो।
   
5. तो सरणी के अंत में नहीं, अगले सरणी तत्व करने के लिए जाना है, अन्यथा चरण 2.
   
6. हो गया

Answer 2

In-place MSD radix sort

Answer 3

कदम 7

जाओ जाओ जब आप सुनिश्चित हैं कि सभी पूर्णांक 1 और एन के बीच हैं तो आप counting sort