एक सॉर्टिंग एल्गोरिदम स्थिर है यदि यह बराबर कुंजी वाले किसी भी दो तत्वों के सापेक्ष क्रम को सुरक्षित रखता है। किस स्थिति के तहत quicksort स्थिर है?क्विक्सोर्ट - ऐसी स्थितियां जो इसे स्थिर बनाती हैं
क्विक्सोर्ट स्थिर है जब कोई आइटम पास नहीं होता है जब तक कि कोई छोटी कुंजी न हो।
अन्य स्थितियां इसे स्थिर बनाती हैं?
ठीक है, एक स्थिर क्विकॉर्ट बनाने के लिए काफी आसान है जो O (लॉग एन) के बजाय ओ (एन) स्पेस का उपयोग करता है जो एक जगह, अस्थिर कार्यान्वयन का उपयोग करता है। बेशक, ओ (एन) स्पेस का उपयोग करने वाले एक क्विकॉर्ट को स्थिर नहीं होना चाहिए, लेकिन ऐसा किया जा सकता है।
मैंने पढ़ा है कि ओ (लॉग एन) मेमोरी का उपयोग करने वाले इन-प्लेस क्विकॉर्ट को बनाना संभव है, लेकिन यह काफी धीमी गति से समाप्त होता है (और कार्यान्वयन का विवरण जानवरों की तरह है)।
बेशक, आप हमेशा सरणी के सरणी के माध्यम से जा सकते हैं और मूल सरणी में एक अतिरिक्त कुंजी जोड़ सकते हैं। फिर क्विकॉर्ट स्थिर हो जाएगा और आप अंत में अतिरिक्त कुंजी को निकाल देंगे और हटा देंगे।
आप सूची में इन जोड़ सकते हैं, कि अगर आपके दृष्टिकोण है:
नाइटपिक: यह संरक्षित _equal_ तत्वों का क्रम नहीं है, लेकिन _equivalent_ तत्वों का क्रम है। कैनोलिक उदाहरण केस-असंवेदनशील स्ट्रिंग तुलना है: '" ए "! =" ए "', लेकिन न तो '' ए "<" ए "'न ही'" ए "<" ए "'। –
बिल्कुल एक डुप्लिकेट नहीं है, लेकिन संबंधित: [quicksort विभाजन दृष्टिकोण की स्थिरता] (http://stackoverflow.com/questions/1278243/stability-of-quicksort)। – Dukeling