लंबाई की एक सरणी को देखते हुए एन। इसमें 1 से एन^2 (एन वर्ग) दोनों के मूल्य शामिल हो सकते हैं, मूल्य समेकित हैं। ओ (एन) समय में इस सरणी को सॉर्ट करना संभव है? यदि संभव हो तो कैसे?लंबाई एन की एक सरणी में 1,2,3 मूल्य हो सकते हैं ... N^2। क्या ओ (एन) समय में सॉर्ट करना संभव है?
संपादित करें: यह एक होमवर्क नहीं है।
आधार एन में प्रत्येक पूर्णांक लिखें, प्रत्येक x को x = 1 + x1 + x2 * N के साथ (x1, x2) के रूप में दर्शाया जा सकता है। अब आप इसे दो बार क्रमबद्ध करने के साथ क्रमबद्ध कर सकते हैं, एक बार x1 पर और एक बार x2 पर, जिसके परिणामस्वरूप क्रमबद्ध सरणी होती है।
'गिनती सॉर्ट' क्या है? – Omnifarious
एक दो चरण बाल्टी प्रकार। आप पहली बार गिनती करते हैं कि बाल्टी कितनी प्रविष्टियां होगी, और उसमें से प्रत्येक बाल्टी की प्रारंभिक अनुक्रमणिका (ओ (एन) लेती है)। फिर आप ओ (एन) में भी प्रत्येक बाल्टी में प्रविष्टियों को स्वैप कर सकते हैं। – CodesInChaos
मुझे लगता है कि बाकी दुनिया इसे एक रेडिक्स प्रकार कहती है। – Omnifarious
हां, आप radix sortएन बाल्टी और दो पास के साथ उपयोग कर सकते हैं। असल में, आप संख्या एन में 2 अंकों के रूप में मानते हैं।
स्वीकार्य उत्तर में बताए गए अनुसार मैं 'x = 1 + x1 + x2 * N' को समझने में सक्षम नहीं हूं। यदि हम आधार 'एन' में संख्या का प्रतिनिधित्व करते हैं, तो' 2^2 'अधिकतम 2 बिट्स, x1 और x2 में व्यक्त किया जा सकता है, फिर 'x = x1 * n^0 + x2 * n^1' =' x1 + x2 * N' । कृपया स्पष्ट करें । –
radix sort का उपयोग कर O(n) समय में एक अच्छी तरह परिभाषित अधिकतम मान के साथ पूर्णांक के किसी भी सरणी को सॉर्ट करना संभव है। यह आपके सामने आने वाले पूर्णांक की किसी भी सूची के लिए मामला है। उदाहरण के लिए यदि आप मनमाने ढंग से सटीक पूर्णांक की एक सूची को सॉर्ट कर रहे थे तो यह सच नहीं होगा। लेकिन सभी सी अभिन्न प्रकारों में अच्छी तरह परिभाषित निश्चित सीमाएं हैं।
यदि यह एक होमवर्क प्रश्न है, तो कृपया इस तरह टैग करें। – danben
आपके मूल्य अंतरंग हैं, मुझे लगता है? आप इसे पूर्णांक – CodesInChaos
@CodeInChaos के साथ कर सकते हैं: हाँ अभिन्न, मैंने प्रश्न में जानकारी को जोड़ा, धन्यवाद। – riderchap