क्रमबद्धन (Sorting)

शब्दकोश इसलिए उपयोगी है कि उसके शब्द वर्णक्रम में हैं; वही शब्द यादृच्छिक क्रम में हों तो खोजना लगभग असंभव होगा। क्रमबद्धन (sorting) — तत्वों को आरोही या अवरोही क्रम में, संख्यात्मक या वर्णानुक्रमिक रूप से, व्यवस्थित करना — ही तेज़ खोज, श्रेणीकरण और रिपोर्टिंग संभव बनाता है। यह अध्याय पाठ्यक्रम के तीन क्रमबद्धन एल्गोरिद्म — बबल, सेलेक्शन और इंसर्शन सॉर्ट — पर काम करता है, यह दिखाते हुए कि हर पास के बाद सूची ठीक कैसी दिखती है, और फिर यह कि सूची के आकार के साथ उनका चलने का समय कैसे बढ़ता है। पेपर तीनों के लिए "दूसरे पास के बाद सूची" वाले प्रश्न बनाता है, अतः पास काग़ज़ पर तब तक अभ्यास करें जब तक वे स्वाभाविक न हो जाएँ।

बबल सॉर्ट

बबल सॉर्ट सूची में बार-बार चलता है, आसन्न (adjacent) तत्वों की तुलना करता है और क्रम से बाहर हर जोड़े की अदला-बदली करता है। एक पास में अक्रमित भाग का सबसे बड़ा तत्व अंत तक ले जाया जाता है — वह "बुलबुले की तरह ऊपर उठता है" — अतः पास 1 के बाद सबसे बड़ा अंतिम होता है, पास 2 के बाद दो सबसे बड़े अपनी जगह, इत्यादि। n तत्वों की सूची को n − 1 पास चाहिए, और पास k (1 से गिनते हुए) n − k तुलनाएँ करता है, क्योंकि अंतिम k − 1 तत्व पहले ही स्थिर हैं। कुल (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 तुलनाएँ: पाँच तत्वों के लिए 10।

[5, 1, 4, 2, 8] पर बबल सॉर्ट का पास 1, आरोही
तुलनाक्रियाबाद में सूची
5 और 1अदला-बदली[1, 5, 4, 2, 8]
5 और 4अदला-बदली[1, 4, 5, 2, 8]
5 और 2अदला-बदली[1, 4, 2, 5, 8]
5 और 8अदला-बदली नहीं[1, 4, 2, 5, 8]

पायथन में पुस्तक का रूप दो नेस्टेड लूप है; > को < में बदलने पर क्रम अवरोही हो जाता है:
n = len(L)
for i in range(n - 1):
for j in range(n - 1 - i):
if L[j] > L[j + 1]:
L[j], L[j + 1] = L[j + 1], L[j]
एक आम सुधार एक फ़्लैग रखता है जो दर्ज करता है कि पास में कोई अदला-बदली हुई या नहीं, और जैसे ही कोई पास बिना अदला-बदली के हो, रुक जाता है — पहले से क्रमित सूची पर यह एक ही पास के बाद रुक जाता है।

सेलेक्शन सॉर्ट

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

[29, 10, 14, 37, 13] पर हल किया गया उदाहरण। पास 1: सबसे छोटा 10 है; उसे 29 से बदलें → [10, 29, 14, 37, 13]। पास 2: [29, 14, 37, 13] में सबसे छोटा 13 है; उसे 29 से बदलें → [10, 13, 14, 37, 29]। पास 3: शेष में 14 पहले से सबसे छोटा है, अतः वह स्वयं से बदलता है। पास 4: 37 और 29 बदलें → [10, 13, 14, 29, 37]।

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

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

[7, 3, 5, 1] पर हल किया गया उदाहरण। 3 डालें: यह 7 से छोटा है, अतः 7 दाईं ओर खिसकता है → [3, 7, 5, 1]। 5 डालें: 7 दाईं ओर खिसकता है, 3 नहीं → [3, 5, 7, 1]। 1 डालें: 7, 5 और 3 सब खिसकते हैं → [1, 3, 5, 7]। पहले से क्रमित सूची पर हर नए तत्व की एक ही तुलना होती है और वह कभी नहीं खिसकता, अतः इंसर्शन सॉर्ट n − 1 तुलनाओं के एक ही दौर में पूरा हो जाता है।

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

समय-जटिलता (Time Complexity)

समय-जटिलता बताती है कि इनपुट-आकार n बढ़ने पर एल्गोरिद्म के मूल चरणों की संख्या कैसे बढ़ती है, किसी विशेष मशीन की गति की अनदेखी करते हुए। पुस्तक तीन सरल नियम प्रयोग करती है। बिना लूप का एल्गोरिद्म, जो निश्चित मात्रा में काम करता है, स्थिर (constant) समय-जटिलता रखता है। 1 से n तक चलने वाले एक लूप वाला एल्गोरिद्म रैखिक (linear) जटिलता रखता है, n के अनुपाती। लूप के भीतर लूप वाला, प्रत्येक n तक चलता हुआ, द्विघाती (quadratic) जटिलता रखता है, n² के अनुपाती। बबल, सेलेक्शन और इंसर्शन सॉर्ट तीनों नेस्टेड लूपों से बने हैं, अतः तीनों द्विघाती हैं: सबसे बुरी स्थिति में सूची दोगुनी करने पर काम लगभग चौगुना हो जाता है।

मुख्य बिंदु

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

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. सूची [5, 1, 4, 2, 8] को बबल सॉर्ट से आरोही क्रम में क्रमित किया जाता है। पहले पास के बाद सूची कैसी दिखती है?

    1. [1, 5, 4, 2, 8]
    2. [1, 2, 4, 5, 8]
    3. [1, 4, 2, 5, 8]
    4. [1, 4, 5, 2, 8]
    उत्तर देखें

    उत्तर: C — [1, 4, 2, 5, 8]

    पड़ोसियों की तुलना: 5 और 1 बदलते हैं, 5 और 4 बदलते हैं, 5 और 2 बदलते हैं, और 5 व 8 वहीं रहते हैं, अतः 5 ठीक 8 से पहले तक जाता है और सूची [1, 4, 2, 5, 8] होती है। [1, 5, 4, 2, 8] पहली तुलना के बाद रुक जाता है, और [1, 4, 5, 2, 8] दूसरी के बाद। पूर्णतः क्रमित सूची के लिए 2 को 4 से आगे ले जाने हेतु दूसरा पास चाहिए।

  2. [29, 10, 14, 37, 13] को आरोही क्रम में लगाने के लिए सेलेक्शन सॉर्ट लगाया जाता है। दूसरे पास के बाद सूची क्या है?

    1. [10, 13, 14, 37, 29]
    2. [10, 14, 29, 37, 13]
    3. [10, 13, 14, 29, 37]
    4. [10, 29, 14, 37, 13]
    उत्तर देखें

    उत्तर: A — [10, 13, 14, 37, 29]

    पास 1 सबसे छोटे, 10, को 29 से बदलता है: [10, 29, 14, 37, 13]। पास 2 शेष चार में सबसे छोटा, 13, ढूँढकर उसे 29 से बदलता है: [10, 13, 14, 37, 29]। [10, 29, 14, 37, 13] केवल एक पास के बाद की स्थिति है। [10, 14, 29, 37, 13] अदला-बदली के बजाय सम्मिलित करता है, जो इंसर्शन सॉर्ट है, और पूर्णतः क्रमित सूची को चार पास चाहिए।

  3. [7, 3, 5, 1] पर आरोही क्रम में इंसर्शन सॉर्ट लगाया जाता है। तत्वों 3 और 5 के डाले जाने के बाद सूची क्या है?

    1. [1, 3, 5, 7]
    2. [3, 7, 5, 1]
    3. [1, 3, 7, 5]
    4. [3, 5, 7, 1]
    उत्तर देखें

    उत्तर: D — [3, 5, 7, 1]

    3 डालने पर 7 दाईं ओर खिसकता है: [3, 7, 5, 1]। 5 डालने पर 7 फिर दाईं ओर खिसकता है पर 3 नहीं: [3, 5, 7, 1]। 1 तक अभी पहुँचा नहीं गया, अतः वह अंत में ही रहता है। [3, 7, 5, 1] केवल एक प्रविष्टि के बाद की सूची है, और [1, 3, 7, 5] सबसे छोटे तत्व को पहले आगे ले आता है, जो सेलेक्शन सॉर्ट करता है।

  4. बिना किसी शीघ्र-निकास जाँच वाला बबल सॉर्ट 5 तत्वों की सूची पर चलाया जाता है। वह कुल कितनी तुलनाएँ करता है?

    1. 25
    2. 20
    3. 10
    4. 4
    उत्तर देखें

    उत्तर: C — 10

    चार पास हैं, और हर पास पिछले से एक जोड़ा कम तुलना करता है क्योंकि एक और तत्व अंत में स्थिर हो चुका है: 4 + 3 + 2 + 1 = 10, जो n = 5 के साथ n(n − 1)/2 है। 25 तो n² है, वृद्धि का क्रम, सटीक गिनती नहीं। 20 मानता है कि हर पास चार तुलनाएँ करता है, और 4 तुलनाओं के बजाय पास गिनता है।

  5. निम्नलिखित कोड का आउटपुट क्या है?
    L = [4, 2, 6, 1]
    n = len(L)
    for i in range(n - 1):
    for j in range(n - 1 - i):
    if L[j] < L[j + 1]:
    L[j], L[j + 1] = L[j + 1], L[j]
    print(L)

    1. [1, 2, 4, 6]
    2. [6, 4, 2, 1]
    3. [4, 6, 2, 1]
    4. [2, 4, 1, 6]
    उत्तर देखें

    उत्तर: B — `[6, 4, 2, 1]`

    यह उलटी तुलना वाला बबल सॉर्ट लूप है: जोड़ा तब बदला जाता है जब बायाँ तत्व छोटा हो, अतः छोटे मान अंत की ओर डूबते हैं और सूची अवरोही क्रम में समाप्त होती है, [6, 4, 2, 1]। आरोही उत्तर उनके लिए जाल है जो < चिह्न पढ़े बिना लूप का आकार पहचान लेते हैं। [4, 6, 2, 1] केवल पहले पास के बाद की सूची है।

  6. किसी एल्गोरिद्म में एक लूप दूसरे लूप के भीतर है, और प्रत्येक लूप n बार तक चलता है। पाठ्यपुस्तक के वर्गीकरण के अनुसार उसकी समय-जटिलता है:

    1. स्थिर
    2. रैखिक, n के अनुपाती
    3. 2n के अनुपाती, क्योंकि दो लूप हैं
    4. द्विघाती, n² के अनुपाती
    उत्तर देखें

    उत्तर: D — द्विघाती, n² के अनुपाती

    बाहरी लूप के n में से हर चक्र के लिए भीतरी लूप n बार तक चलता है, अतः चरण गुणा होकर लगभग n × n होते हैं — द्विघाती, यहाँ के तीनों क्रमबद्धन एल्गोरिद्मों का वर्ग। 2n वाला विकल्प लूपों को गुणा करने के बजाय जोड़ता है, जो तभी सही होता जब वे एक के बाद एक चलते। रैखिक एक लूप है, और स्थिर में कोई लूप नहीं होता।

  7. इनमें से किस क्रमबद्धन एल्गोरिद्म में हर पास अधिकतम एक अदला-बदली करता है?

    1. बबल सॉर्ट
    2. सेलेक्शन सॉर्ट
    3. इंसर्शन सॉर्ट
    4. तीनों समान रूप से
    उत्तर देखें

    उत्तर: B — सेलेक्शन सॉर्ट

    सेलेक्शन सॉर्ट अक्रमित भाग में सबसे छोटा तत्व ढूँढता है और उसके बाद ही उसे जगह पर रखने के लिए एक अदला-बदली करता है, अतः हर पास में अधिकतम एक अदला-बदली होती है। बबल सॉर्ट एक पास की हर तुलना पर अदला-बदली कर सकता है, जैसे [5, 1, 4, 2, 8] पर पहला पास तीन बार करता है। इंसर्शन सॉर्ट रिक्त स्थान बनाने के लिए कई तत्व खिसकाता है, अतः वह भी एक चाल तक सीमित नहीं।

  8. अभिकथन (A): आरोही क्रम में बबल सॉर्ट के k पासों के बाद सूची के अंतिम k तत्व अपनी अंतिम स्थिति में होते हैं। कारण (R): बबल सॉर्ट का हर पास अक्रमित भाग के सबसे बड़े तत्व को उस भाग के अंत तक ले जाता है।

    1. A और R दोनों सत्य हैं, और R, A की सही व्याख्या है
    2. A और R दोनों सत्य हैं, पर R, A की सही व्याख्या नहीं है
    3. A सत्य है, पर R असत्य है
    4. A असत्य है, पर R सत्य है
    उत्तर देखें

    उत्तर: A — A और R दोनों सत्य हैं, और R, A की सही व्याख्या है

    हर आसन्न अदला-बदली बड़े मान को दाईं ओर ले जाती है, अतः हर पास में सबसे बड़ा अक्रमित मान अक्रमित भाग के अंत तक धकेल दिया जाता है; k पासों के बाद k सबसे बड़े मान अंतिम k स्थान घेरते हैं, और कोई बाद का पास उन्हें नहीं हिलाता। R वह क्रियाविधि बताता है जिससे A बनता है, अतः वह उसकी व्याख्या है। A को असत्य कहना बबल सॉर्ट को इंसर्शन सॉर्ट से उलझाना होगा, जिसका क्रमित भाग अभी अंतिम नहीं होता।