क्विकसॉर्ट

एक वैल्यू चुनता है, जिसे पिवट कहते हैं, और छोटी वैल्यू उसके बाईं ओर व बड़ी दाईं ओर ले जाता है। फिर हर तरफ यही दोहराता है।

  • Ω(n log n)
  • Θ(n log n)
  • O(n²)
  • O(log n)
  • नहीं
  • हाँ
  • तुलना हो रही है
  • खिसक रहा है
  • पिवट
  • अंतिम जगह पर
0 / 187 चरण

रिकर्शन की गहराई: 0 · कम से कम संभव: 4 · सबसे खराब: 23 अपने पिवट का इंतज़ार

तुलनाएं अदला-बदली

प्ले दबाएं: रेखाएँ दिखाती हैं कि सॉर्ट के दौरान लागत कैसे बढ़ती है

प्ले दबाएं या एल्गोरिदम को चरण दर चरण देखें।

स्पेस: चलाएं या रोकें। बाएं और दाएं ऐरो: चरण दर चरण। Home और End: सीधे जाएं।

इसे आज़माएं: उलटी लिस्ट चुनें। पिवट हमेशा बची सबसे छोटी या सबसे बड़ी वैल्यू होता है, इसलिए हर बार एक तरफ खाली रहती है और लागत n² तक जाती है।

यह कैसे काम करता है

यहां पिवट रेंज की आखिरी वैल्यू है। बाएं से दाएं चलते हुए, जो भी वैल्यू पिवट से बड़ी नहीं है, उसे अदला-बदली से बाएं हिस्से में भेजा जाता है। फिर पिवट दोनों हिस्सों के बीच आता है और हमेशा वहीं रहता है। इसके बाद हर हिस्से को इसी तरह सॉर्ट किया जाता है।

यह कब सही विकल्प है

असल में सॉर्ट करने के सबसे तेज़ तरीकों में से एक, और इसे लगभग कोई अतिरिक्त मेमोरी नहीं चाहिए। पर अगर यह बार-बार खराब पिवट चुने, जैसे पहले से सॉर्टेड लिस्ट पर, तो धीमा हो जाता है। असली वर्शन पिवट ज़्यादा सोच-समझकर चुनते हैं।