ओ (एन लॉग एन) से जेनेरिक और व्यावहारिक सॉर्टिंग एल्गोरिदम तेजी से?

Question

क्या जेनेरिक तत्वों (गिनती सॉर्ट या बाल्टी सॉर्ट के विपरीत) के लिए कोई व्यावहारिक एल्गोरिदम है जो ओ (एन लॉग एन) से तेज़ चलता है?

Answer 1

कई लोगों ने सूचना-सैद्धांतिक Ω (एन एलजी एन) तुलना सॉर्टिंग एल्गोरिदम पर बाध्य किया है, जो तुलनात्मक प्रकार में टूटा नहीं जा सकता है। (This earlier question की पड़ताल क्यों ऐसी बात है।)

हालांकि, वहाँ है कि, जबकि औसत के मामले में O (n एलजी एन) को तोड़ने नहीं, आदानों कि पहले से ही कर रहे हैं presorted पर तेजी से चलाने के लिए दिखाया जा सकता है तुलना प्रकार के कुछ प्रकार के होते हैं कुछ हद तक। उदाहरण के लिए, डिजस्ट्रा का चिकनाई ओ (एन) में ओ (एन) के साथ पहले से क्रमबद्ध इनपुट पर चलता है जिसमें ओ (एन एलजी एन) सबसे खराब केस व्यवहार होता है। मेरे पसंदीदा प्रकारों में से एक, Cartesian tree sort, कुछ मेट्रिक्स में प्रत्यारोपण का इष्टतम लाभ लेता है। उदाहरण के लिए, यह किसी भी अनुक्रम को समय ओ (एन) में बढ़ती या घटती हुई निरंतर संख्या के साथ क्रमबद्ध कर सकता है, जो सबसे खराब मामले में ओ (एन एलजी एन) को गहराई से घट रहा है।

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

संक्षेप में, नहीं, आप ओ (एन एलजी एन) से ज्यादा बेहतर नहीं कर सकते हैं, लेकिन अगर आप अपने इनपुट के बारे में कुछ जानते हैं तो आप थोड़ा बेहतर कर सकते हैं।

Answer 2

जेनेरिक तत्वों के लिए जिन्हें आप केवल तुलना कर सकते हैं और आंतरिक रूप से नहीं पहुंच सकते हैं, थैटा (एन लॉग एन) से एक सॉर्टिंग एल्गोरिदम तेजी से असंभव है। ऐसा इसलिए है क्योंकि एन हैं! (एन फैक्टोरियल) तत्वों के संभावित आदेश, और आपको उन सभी को अलग करने के लिए थेटा (एन लॉग एन) तुलना की आवश्यकता है।

Answer 3

कितने तत्वों के लिए? भले ही यह एन ^1.2 जैसा कुछ है, फिर भी शैल-मेटज़नर सॉर्ट कुछ अन्य तत्वों (या तो) तक अधिकतर लोगों की तुलना में तेज़ होता है।

यह "जेनेरिक" और "व्यावहारिक" से आपका क्या मतलब है इस पर निर्भर करता है। एक रेडिक्स सॉर्ट ओ (एन लॉग एन) को हरा सकता है, और यह काफी विस्तृत प्रकार के डेटा के लिए काम करता है (लेकिन निश्चित रूप से सब कुछ नहीं)।

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

Answer 4

नहीं। यह हमारे पास एल्गोरिदम के लिए कुछ कठोर न्यूनतम सीमाओं में से एक है। एन तत्वों के संग्रह के लिए, एन हैं! अलग-अलग ऑर्डर, इसलिए किसी दिए गए ऑर्डर को निर्दिष्ट करने के लिए हमें लॉग (एन!) बिट्स की आवश्यकता होती है। स्टर्लिंग के अनुमान से यह लगभग एन लॉग एन है। प्रत्येक तुलना के लिए हम तत्वों के बीच करते हैं, हम अनिवार्य रूप से एक बिट जानकारी प्राप्त करते हैं (बराबर तत्वों की संभावना को अनदेखा करते हैं)।