हीपसॉर्ट

लिस्ट को हीप में बदलता है, यानी ऐसा ट्री जिसमें हर पैरेंट अपने चाइल्ड से बड़ा होता है। फिर बार-बार सबसे बड़ी वैल्यू को अंत में ले जाता है।

  • Ω(n log n)
  • Θ(n log n)
  • O(n log n)
  • O(1)
  • नहीं
  • हाँ
  • तुलना हो रही है
  • खिसक रहा है
  • अंतिम जगह पर
0 / 299 चरण
तुलनाएं अदला-बदली

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

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

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

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

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

हीप इसी लिस्ट के अंदर रखी जाती है: जगह i वाली वैल्यू के चाइल्ड जगह 2i+1 और 2i+2 पर होते हैं, और सबसे बड़ी वैल्यू हमेशा सबसे आगे रहती है। अदला-बदली से उसे अंत में भेजें, हीप को एक जगह छोटा करें और ठीक करें। सॉर्टेड हिस्सा दाईं ओर से बढ़ता है।

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

जब ऐसी रफ़्तार चाहिए जो सबसे बुरी स्थिति में भी अच्छी रहे और अतिरिक्त मेमोरी न लगे, जैसे छोटे डिवाइसों पर। औसतन यह क्विकसॉर्ट से धीमा है, इसलिए अक्सर इसे बैकअप के तौर पर इस्तेमाल किया जाता है।