आप में से कुछ इस सुंदर लेख पर ठोकर खाई हो सकता है - http://igoro.com/archive/quicksort-killer/ \के बारे में त्वरित क्रमबद्ध खूनी
क्या वाकई दिलचस्प है कि कैसे वह जल्दी प्रकार (एन लॉग ऑन एन) में परिभाषित किया गया विरोधी के खिलाफ हे में प्रदर्शन करने के लिए ठीक करता है।
क्विक्सॉर्ट प्रत्येक चरण में पिवट के रूप में औसत तत्व का चयन कर सकता है, इस प्रकार हमेशा इनपुट अनुक्रम का एक पूर्ण विभाजन दो हिस्सों में प्राप्त कर सकता है। मध्यस्थ ओ (एन) चलने का समय निर्धारित रूप से पाया जा सकता है, और इसलिए कुल चलने का समय हमेशा ओ (एन लॉग एन) होता है।
मेरा प्रश्न रेखीय समय मंझला खोजने एल्गोरिथ्म एक ही समारोह की तुलना और हे (एन^2) हे (एन) के बजाय में प्रदर्शन का उपयोग कर खत्म नहीं होगा?
संपादित करें:
सटीक होना: मैं विभाजन आधारित मंझला-चयन एल्गोरिथ्म जो एक रणनीति त्वरित तरह और यह एक ही एक के रूप में समारोह की तुलना का उपयोग करेगा के समान का उपयोग करता है की जटिलता पर सवाल कर रहा हूँ त्वरित प्रकार का उपयोग करता है। यह इस विरोधी के साथ ओ (एन) में कैसे काम कर सकता है?
संपादित करें पुन: तुलनात्मक कार्य में जटिलता से कोई लेना देना नहीं है, और मध्य चयन ओ (एन) है। –