इंसर्शन सॉर्ट

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

सॉर्ट होते बार: बाईं ओर सॉर्ट हुआ हिस्सा, और एक बार बड़े बारों के पार पीछे खिसककर उसमें जाता हुआ
सॉर्ट होते बार: बाईं ओर सॉर्ट हुआ हिस्सा, और एक बार बड़े बारों के पार पीछे खिसककर उसमें जाता हुआ

मूल विचार

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

एक उदाहरण

5, 1, 4, 2, 8 लें। पास 1 में 1 लिया जाता है: 5 बड़ा है, इसलिए अदला-बदली होती है, और 1 शुरुआत तक पहुँच जाता है: 1, 5, 4, 2, 8। पास 2 में 4 लिया जाता है: यह 5 से अदला-बदली करता है, फिर 1 पर रुकता है: 1, 4, 5, 2, 8। पास 3 में 2 लिया जाता है: यह 5 और 4 से अदला-बदली करता है, फिर 1 पर रुकता है: 1, 2, 4, 5, 8। पास 4 में 8 लिया जाता है, जो पहले से 5 से बड़ा है, इसलिए एक तुलना काफ़ी है। कुल 7 तुलनाएँ और 4 अदला-बदली। इसी सूची पर बबल सॉर्ट को 9 तुलनाएँ चाहिए, सिलेक्शन सॉर्ट को 10।

अदला-बदली = इनवर्ज़न

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

अडैप्टिव: सूची लगभग सॉर्ट हो तो तेज़

क्योंकि काम इनवर्ज़न की संख्या और लगभग n के जोड़ जितना है, इसलिए जब भी इनवर्ज़न कम हों, इंसर्शन सॉर्ट तेज़ होता है। सॉर्ट की हुई सूची में n − 1 तुलनाएँ लगती हैं और कोई अदला-बदली नहीं। जिस सूची में हर मान अपनी जगह से बस कुछ ही स्थान दूर हो, उसमें n के क़रीब समय लगता है। सिर्फ़ सॉर्ट से बहुत दूर वाली सूची, जैसे n(n − 1)/2 इनवर्ज़न वाली उल्टी सूची, में n² के अनुपात में समय लगता है। रैंडम सूची पर औसतन लगभग n²/4 अदला-बदली होती हैं।

इसका इस्तेमाल कहाँ होता है

इंसर्शन सॉर्ट स्टेबल है, इसे अतिरिक्त मेमोरी नहीं चाहिए, और इसका ओवरहेड बहुत कम है। छोटी सूचियों पर यह उन एल्गोरिदम से भी तेज़ है जो कागज़ पर तेज़ हैं। कई लाइब्रेरी सॉर्ट, जैसे Python और Java का Timsort और C++ में इस्तेमाल होने वाला introsort, सूची के छोटे टुकड़ों के लिए, आम तौर पर कुछ दर्जन मानों तक, इंसर्शन सॉर्ट पर चले जाते हैं। यह उस डेटा के लिए भी ठीक है जो एक-एक मान करके आता है, क्योंकि हर नया मान आते ही डाला जा सकता है।

ख़ुद आज़माएँ

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

अक्सर पूछे जाने वाले प्रश्न

इंसर्शन सॉर्ट की टाइम कॉम्प्लेक्सिटी क्या है?

सबसे ख़राब और औसत स्थिति में O(n²), और सबसे अच्छी स्थिति में, यानी पहले से सॉर्ट की हुई सूची पर, O(n)। ज़्यादा सटीक कहें तो इसमें n और इनवर्ज़न की संख्या के जोड़ के अनुपात में समय लगता है। इसे सिर्फ़ O(1) अतिरिक्त मेमोरी चाहिए।

इंसर्शन सॉर्ट और सिलेक्शन सॉर्ट में क्या अंतर है?

सिलेक्शन सॉर्ट सबसे छोटा मान ढूँढने के लिए पूरे अनसॉर्टेड हिस्से को देखता है, इसलिए हमेशा n(n − 1)/2 तुलनाएँ करता है, पर अदला-बदली कम। इंसर्शन सॉर्ट अगला मान जैसे आता है वैसे लेता है और उसे सिर्फ़ ज़रूरत भर पीछे ले जाता है, इसलिए तुलनाएँ कम करता है, ख़ासकर लगभग सॉर्ट सूचियों पर, पर अदला-बदली ज़्यादा।

बाइनरी इंसर्शन सॉर्ट क्या है?

एक रूप जो सॉर्ट हुए हिस्से में बाइनरी सर्च से पता लगाता है कि नया मान कहाँ जाएगा, जिसमें n तक की जगह लगभग log n तुलनाएँ लगती हैं। जगह बनाने के लिए मानों को अब भी खिसकाना पड़ता है, इसलिए खिसकाने की संख्या और O(n²) वाली सबसे ख़राब स्थिति वही रहती है।

क्या इंसर्शन सॉर्ट स्टेबल है?

हाँ। कोई मान सिर्फ़ उन मानों के पार पीछे जाता है जो सख़्ती से बड़े हैं, इसलिए बराबर मान अपना मूल क्रम बनाए रखते हैं।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

इंसर्शन सॉर्ट आज़माएँ