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