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