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