हीपसॉर्ट
लिस्ट को हीप में बदलता है, यानी ऐसा ट्री जिसमें हर पैरेंट अपने चाइल्ड से बड़ा होता है। फिर बार-बार सबसे बड़ी वैल्यू को अंत में ले जाता है।
- सर्वश्रेष्ठ Ω(n log n)
- औसत Θ(n log n)
- सबसे खराब O(n log n)
- मेमोरी O(1)
- अनस्टेबल
- अतिरिक्त मेमोरी नहीं चाहिए
इनका मतलब क्या है?
- सर्वश्रेष्ठ: जब इनपुट इस एल्गोरिदम के लिए सबसे आसान हो, तब लिस्ट के आकार n के साथ समय कैसे बढ़ता है।
- औसत: n के साथ समय की आम बढ़त। n² में वैल्यू की संख्या दोगुनी होने पर लगभग चार गुना समय लगता है; n log n बहुत धीरे बढ़ता है।
- सबसे खराब: सबसे कठिन इनपुट पर बढ़त। तब काम का, जब रफ़्तार कभी नहीं गिरनी चाहिए।
- मेमोरी: लिस्ट के अलावा कितनी अतिरिक्त मेमोरी चाहिए। 1 यानी कुछ वेरिएबल, n यानी लिस्ट की एक कॉपी।
- स्टेबल: दो बराबर वैल्यू अपना मूल क्रम बनाए रखती हैं। रिकॉर्ड के किसी एक फ़ील्ड से सॉर्ट करते समय यह ज़रूरी है।
- अतिरिक्त मेमोरी नहीं चाहिए: लिस्ट के अंदर ही सॉर्ट करता है, दूसरी लिस्ट के बिना।
- तुलना हो रही है
- खिसक रहा है
- अंतिम जगह पर
प्ले दबाएं: रेखाएँ दिखाती हैं कि सॉर्ट के दौरान लागत कैसे बढ़ती है
प्ले दबाएं या एल्गोरिदम को चरण दर चरण देखें।
स्पेस: चलाएं या रोकें। बाएं और दाएं ऐरो: चरण दर चरण। Home और End: सीधे जाएं।
इसे आज़माएं: उलटी लिस्ट चुनें। हीप बनाने में लगभग कोई अदला-बदली नहीं होती, फिर हर चक्कर सबसे बड़ी वैल्यू को अंत में ले जाता है।
यह कैसे काम करता है
हीप इसी लिस्ट के अंदर रखी जाती है: जगह i वाली वैल्यू के चाइल्ड जगह 2i+1 और 2i+2 पर होते हैं, और सबसे बड़ी वैल्यू हमेशा सबसे आगे रहती है। अदला-बदली से उसे अंत में भेजें, हीप को एक जगह छोटा करें और ठीक करें। सॉर्टेड हिस्सा दाईं ओर से बढ़ता है।
यह कब सही विकल्प है
जब ऐसी रफ़्तार चाहिए जो सबसे बुरी स्थिति में भी अच्छी रहे और अतिरिक्त मेमोरी न लगे, जैसे छोटे डिवाइसों पर। औसतन यह क्विकसॉर्ट से धीमा है, इसलिए अक्सर इसे बैकअप के तौर पर इस्तेमाल किया जाता है।