इन्सर्शन और सिलेक्शन सॉर्ट: पास, इनवेरिएंट और स्थिरता

लक्ष्य और पूर्वज्ञान

कुंजी (key) के अनुसार array तब अघटते क्रम में sorted है जब हर कुंजी अगली कुंजी से छोटी या बराबर हो। सॉर्टिंग में हर मूल रिकॉर्ड ठीक एक बार बचना चाहिए; असंबंधित कुंजियों का sorted क्रम लिख देना सॉर्टिंग नहीं है। यहाँ दो comparison sorts और नीचे दिए उनके निश्चित implementations पढ़ेंगे, सभी संभव variants नहीं।

पूर्वज्ञान: array elements और valid indices; array parameters और caller-visible changes; algorithm growth और asymptotic bounds। Θ के tight bound को O के upper bound से, तथा best-case input को worst-case input से अलग समझें। n सक्रिय prefix की लंबाई है। खाली और एक-रिकॉर्ड वाला prefix पहले से sorted है; दोनों में शून्य पास होते हैं।

एक पास outer loop के body का एक execution है। n >= 1 पर दोनों versions ठीक n-1 पास करते हैं, भले कोई पास कुछ न हिलाए। n=0 पर शून्य पास हैं। swaps या comparisons की संख्या को passes की संख्या न मानें।

रिकॉर्ड और स्थिरता: पहले syntax

कुंजी बताती है कि रिकॉर्ड किस क्रम में आएगा; पहचान (identity) बताती है कि वह कौन-सा मूल रिकॉर्ड है। [2a,2b,1c] में a और b अलग रिकॉर्ड हैं जिनकी कुंजी 2 है। केवल संख्यात्मक कुंजी की तुलना होती है। स्थिर (stable) sort बराबर कुंजी वाले रिकॉर्डों का मूल आपसी क्रम बचाता है, इसलिए a को b से पहले रहना चाहिए। स्थिरता का अर्थ अपने पुराने index पर बने रहना नहीं है।

C में struct Record { int key; int id; }; दो int fields को एक रिकॉर्ड में रखता है। struct Record item ऐसा एक रिकॉर्ड बनाता है; a[i].key array के iवें रिकॉर्ड की key field है। a[j] = a[j-1] दोनों fields copy करता है, इसलिए key और identity साथ चलते हैं। {{2,0},{2,1},{1,2}} घोषणा-क्रम में तीन रिकॉर्ड initialize करता है; बाकी array elements शून्य से initialize होते हैं। IDs 0,1,2 उदाहरण के a,b,c हैं। algorithm IDs की तुलना नहीं करता।

Function parameter struct Record a[CAP] pointer में adjust होता है; इससे array की copy नहीं बनती और capacity प्रमाणित नहीं होती। Caller एक live, writable CAP-record array देगा, उसके active elements initialized होंगे तथा 0 <= n <= CAP होगा। Functions a[0..n-1] को उसी array में sort करते हैं और inactive elements नहीं बदलते। NULL और n की जाँच स्पष्ट गलत arguments रोकती है, पर dangling pointer या छोटे array को नहीं पहचान सकती। इस contract में n=0 पर भी non-NULL live array चाहिए। Dynamic allocation नहीं है।

enum { CAP = 8 }; उदाहरण की capacity है। ++i बढ़ाता और --j घटाता है। && दायाँ भाग तभी जाँचता है जब बायाँ सत्य हो। इसलिए j > 0 && a[j-1].key > item.key कभी negative index नहीं पढ़ता। INT_MIN और INT_MAX पर भी सीधी key comparison सुरक्षित है; keys घटाकर तुलना करने पर overflow हो सकता है।

इन्सर्शन सॉर्ट: sorted prefix बढ़ाना

Outer index i पर a[i] को item में बचाएँ। i से पहले का prefix sorted है। पीछे के हर strictly larger रिकॉर्ड को एक स्थान दाएँ खिसकाएँ। शुरुआत पर या item की कुंजी से छोटी/बराबर कुंजी पर रुकें। बने हुए खाली स्थान में item रखें।

Outer-loop invariant: पास i से ठीक पहले (1 <= i < n), a[0..i-1] मूल पहले i रिकॉर्डों का sorted, stable permutation है; a[i..n-1] अभी नहीं बदला है। शुरू में i=1 पर एक-रिकॉर्ड prefix यह शर्त पूरी करता है। पास अगले मूल रिकॉर्ड को पुराने बराबर रिकॉर्डों के बाद डालता है, इसलिए क्रम और स्थिरता दोनों बने रहते हैं। अंत में पूरा active prefix sorted है और हर मूल रिकॉर्ड बचा है।

Shifting के दौरान saved item array से बाहर है और j खाली स्थान दर्शाता है। इस पास की शुरुआत में स्थान j से i-1 पर रहे खिसकाए गए रिकॉर्ड अब j+1 से i पर हैं; उनकी कुंजियाँ item.key से बड़ी हैं। खाली स्थान में अस्थायी रूप से किसी दूसरे रिकॉर्ड की duplicate copy हो सकती है। इसलिए हर assignment के बाद अकेले array को permutation कहना गलत होगा। Saved item और खाली स्थान को छोड़कर बाकी रिकॉर्ड मिलकर डेटा बचाते हैं। j पर item रखने से पूरा permutation लौट आता है।

Strict > ज़रूरी है: पुराना बराबर-key रिकॉर्ड नए item के पार नहीं खिसकता। इसे >= करने पर बराबर रिकॉर्डों का क्रम उलट सकता है और स्थिरता का दावा गलत हो जाएगा।

हल किया trace 1: इन्सर्शन के पास

Input [4a,2b,3c,2d] लें। खड़ी रेखा हर पास के बाद sorted prefix दिखाती है।

• शुरुआत: [4a | 2b,3c,2d]।
• पास i=1: 2b बचाएँ; 4a दाएँ खिसकाएँ; 0 पर insert करें। [2b,4a | 3c,2d]।
• पास i=2: 3c बचाएँ; 4a खिसकाएँ; 2b से तुलना करके रुकें। [2b,3c,4a | 2d]।
• पास i=3: 2d बचाएँ; 4a फिर 3c खिसकाएँ; 2b.key > 2d.key असत्य है। [2b,2d,3c,4a |]।

तीन पास, चार right shifts और छह key comparisons (1+2+3) हुए। Key comparison का अर्थ executed a[j-1].key > item.key है, उसका असत्य परिणाम भी गिना जाता है; j>0 boundary test नहीं गिनते। पहले पास में j=0 पर रुकते हैं, इसलिए अंत में false key comparison नहीं है। बराबर कुंजी के लिए b, d से पहले रहता है।

सिलेक्शन सॉर्ट: हर पास में एक स्थान अंतिम करना

Index i पर min_index=i से शुरू करें। j=i+1 से n-1 तक scan करें; min_index केवल strictly smaller key मिलने पर बदलें। इससे वर्तमान suffix का पहला minimum मिलता है। पूरा scan समाप्त होने पर उस रिकॉर्ड और a[i] को swap करें, यदि min_index=i नहीं है। यह सामान्य swap-based selection sort है। Minimum निकालकर बीच के रिकॉर्डों को shift करने वाला stable variant अलग है।

Outer-loop invariant: पास i से पहले prefix a[0..i-1] sorted है, उसकी हर key शेष suffix की हर key से छोटी या बराबर है, और पूरा array input records का permutation है। शुरू में prefix खाली है। Inner scan में min_index पहले से देखे गए हिस्से a[i..j-1] के पहले minimum पर है। अगले रिकॉर्ड की तुलना से यही तथ्य एक स्थान आगे तक फैलता है। पूरा suffix scan होने पर उसका minimum i पर रखने से finalized prefix बढ़ता है। Swap रिकॉर्डों को बचाता है। n-1 passes के बाद बचा आखिरी रिकॉर्ड prefix से छोटा नहीं हो सकता; पूरा array sorted है।

इन invariants में बराबर रिकॉर्डों का आपसी क्रम सुरक्षित रखने की शर्त नहीं है। पहला minimum चुनने से लंबी दूरी का swap स्थिर नहीं हो जाता।

हल किया trace 2: सिलेक्शन के पास

वही input [4a,2b,3c,2d] लें।

• पास i=0: 2b,3c,2d scan होते हैं; strict < पहला minimum 2b रखता है। 0 और 1 swap करें: [2b | 4a,3c,2d]।
• पास i=1: suffix का minimum 2d स्थान 3 पर है। 1 और 3 swap करें: [2b,2d | 3c,4a]।
• पास i=2: 4a की 3c से तुलना करें; minimum पहले से 2 पर है। Swap नहीं: [2b,2d,3c | 4a]। यह फिर भी एक पास है।

तीन पास, छह key comparisons (3+2+1) और दो वास्तविक swaps हैं। इस input में बराबर रिकॉर्डों का क्रम संयोग से बचा। इससे सभी inputs पर स्थिरता सिद्ध नहीं होती।

हल किया trace 3: स्थिरता का counterexample

Input [2a,2b,1c] है। Selection के पहले पास में 2a और 1c swap होते हैं: [1c,2b,2a]। अगले पास में बराबर 2 keys की तुलना होती है, पहला minimum रहता है और swap नहीं होता। अंत में b, a से पहले है: मूल equal-key क्रम उलट गया। इसलिए strict < और पहला minimum चुनने पर भी यह selection variant अस्थिर है।

Insertion का पहला पास [2a,2b] को नहीं बदलता। अगला पास 1c बचाकर 2b फिर 2a को खिसकाता है और [1c,2a,2b] देता है। दोनों बराबर रिकॉर्डों का क्रम बचता है। स्थिरता सभी अनुमत inputs के लिए guarantee है; अस्थिरता सिद्ध करने को एक counterexample पर्याप्त है।

पूरा bounded C11 प्रोग्राम

नीचे sorting.c का पूरा source है। main दोनों sorting functions को explicit success check में call करता है और किसी की विफलता पर 1 लौटाता है। NDEBUG define करने पर भी sorting चलती है। अलग test program में assert है, इसलिए उसे NDEBUG define किए बिना build करें।

#include <limits.h>
#include <stdio.h>

enum { CAP = 8 };
struct Record { int key; int id; };

/* The caller supplies a live CAP-element array, even when n is zero. */
int insertion_sort(struct Record a[CAP], int n) {
    if (a == NULL || n < 0 || n > CAP) { return 0; }
    for (int i = 1; i < n; ++i) {
        struct Record item = a[i];
        int j = i;
        while (j > 0 && a[j - 1].key > item.key) {
            a[j] = a[j - 1];
            --j;
        }
        a[j] = item;
    }
    return 1;
}

int selection_sort(struct Record a[CAP], int n) {
    if (a == NULL || n < 0 || n > CAP) { return 0; }
    for (int i = 0; i < n - 1; ++i) {
        int min_index = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j].key < a[min_index].key) { min_index = j; }
        }
        if (min_index != i) {
            struct Record temp = a[i];
            a[i] = a[min_index];
            a[min_index] = temp;
        }
    }
    return 1;
}

static void print_records(const struct Record a[CAP], int n) {
    for (int i = 0; i < n; ++i) {
        printf("%s%d(%d)", i == 0 ? "" : " ", a[i].key, a[i].id);
    }
    putchar('\n');
}

int main(void) {
    struct Record insertion[CAP] = {{2, 0}, {2, 1}, {1, 2}};
    struct Record selection[CAP] = {{2, 0}, {2, 1}, {1, 2}};
    if (!insertion_sort(insertion, 3) || !selection_sort(selection, 3)) {
        return 1;
    }
    printf("insertion: "); print_records(insertion, 3);
    printf("selection: "); print_records(selection, 3);
    return 0;
}

ठीक output (key के बाद कोष्ठक में मूल ID):

insertion: 1(2) 2(0) 2(1)
selection: 1(2) 2(1) 2(0)

दोनों functions success पर 1 लौटाते हैं; valid empty/singleton prefixes भी success हैं। NULL pointer या 0..CAP से बाहर n पर 0 लौटाते हैं। Invalid call कोई write करने से पहले लौटता है। Caller का capacity/lifetime वादा फिर भी आवश्यक है। print_records केवल active elements पढ़ता है। इसका static declaration इस helper का नाम केवल इसी source file तक सीमित रखता है। Conditional expression i == 0 ? "" : " " पहले रिकॉर्ड के लिए खाली string और बाद के रिकॉर्डों के लिए एक-space string चुनता है, इसलिए शुरुआत में space नहीं आता। printf का %s वह string और हर %d एक int छापता है; putchar newline लिखता है।

गिनती, input cases और space

केवल दो record keys के बीच executed comparisons गिनें, loop bounds, index tests या assignments नहीं। Selection के हर पास में सभी बचे candidates की running minimum से तुलना होती है: n>=1 पर (n-1)+(n-2)+...+1 = n(n-1)/2 key comparisons; n=0 पर शून्य। Input क्रम का इससे संबंध नहीं; पहले से sorted input में भी यही संख्या है। अधिकतम n-1 वास्तविक swaps हैं; यह code self-swaps छोड़ता है। शून्य swaps का अर्थ शून्य काम नहीं है।

Insertion में nondecreasing sorted input, जिसमें all-equal array भी आता है, n>=1 पर ठीक n-1 key comparisons और शून्य right shifts लेता है। हर पास item को फिर भी बचाता और लिखता है। अलग-अलग keys का strictly decreasing input 1+2+...+(n-1) = n(n-1)/2 key comparisons और उतने ही shifts लेता है। Shift while loop के अंदर एक रिकॉर्ड का दाएँ assignment है, अंतिम insertion assignment नहीं। अन्य inputs पर successful shift comparisons के साथ एक false stopping comparison भी हो सकता है।

Constant-cost record/key model में सामान्य scalable algorithms के लिए insertion का best-case समय Θ(n) और worst-case Θ(n²) है। Selection का best और worst दोनों Θ(n²) हैं। ये बढ़ते n के asymptotic कथन हैं (n>=2), O और Θ के अलग अर्थ नहीं। दोनों का auxiliary space Θ(1) है: कुछ indices और एक saved record। Input array का Θ(n) space auxiliary नहीं है। main के दो अलग arrays समान input पर दोनों algorithms दिखाते हैं; एक sorting call कोई छिपी array copy नहीं बनाता। Test harness की verification copies sorting algorithms के बाहर हैं।

CAP=8 जानबूझकर executable तथा index arithmetic को सीमित करता है। सचमुच इस fixed program की सभी runs का finite constant bound है। Asymptotic कथन बड़े अनुमत arrays पर उन्हीं algorithms के बारे में हैं, इस घोषित capacity से बाहर execution के बारे में नहीं। n(n-1)/2 एक गणितीय count है; sorting code उसे evaluate नहीं करता। n=0 या 1 पर constant setup समय है, zero passes और zero key comparisons हैं।

मुख्य बातें: परीक्षा की सामान्य भूलें

• पूरे records sort करें, केवल keys compare करें; स्थिरता बराबर keys के मूल क्रम का गुण है।
• Strict > shifting इस insertion sort को stable रखती है। Strict < first-minimum selection swap-based selection को stable नहीं बनाती।
• Invariant बताए कि हर पास से पहले क्या सत्य है और एक पास उसे कैसे बनाए रखता है।
• पहले से sorted array में भी n>=1 पर n-1 passes हैं। Selection हर suffix scan करता है; insertion का shift loop तुरंत रुकता है।
• No-op selection pass swap नहीं है। अंतिम insertion write right shift नहीं है। कौन-सी क्रिया गिन रहे हैं, स्पष्ट करें।
• Θ(1) auxiliary space का अर्थ scalable model में input array का constant size नहीं है।

दो अतिरिक्त अभ्यास और हल

1. [3a,1b,2c] पर दोनों methods चलाएँ। हर पास के बाद state और key-comparison count बताएँ।

हल: insertion में [1b,3a,2c], फिर [1b,2c,3a]; comparisons 1+2=3 और shifts दो हैं। Selection में [1b,3a,2c], फिर [1b,2c,3a]; comparisons 2+1=3 और swaps दो हैं। यहाँ states एक जैसी होने से algorithms एक नहीं हो जाते।

2. Insertion की while comparison को >= करें और [2a,2b,1c] sort करें। क्या बदलता है?

हल: पहला पास 2a खिसकाकर 2b उससे पहले रखता है: [2b,2a,1c]। दूसरा पास दोनों 2 records खिसकाकर 1c रखता है: [1c,2b,2a]। Keys sorted हैं, पर बराबर identities उलट गईं; स्थिरता खत्म है। n>=1 के all-equal input पर बदला variant n(n-1)/2 shifts और key comparisons करता है; मूल variant शून्य shifts और n-1 comparisons करता है।

अगले छह प्रश्न मौलिक अभ्यास हैं; हर प्रश्न में ठीक एक सही विकल्प है।

S01

इन्सर्शन सॉर्ट के दो पूरे पास के बाद [4a,2b,3c,2d] किस रूप में होगा?

A. [2b,3c,4a,2d] B. [2b,2d,3c,4a] C. [2b,4a,3c,2d] D. [4a,2b,2d,3c]

उत्तर: A

A सही है: i=1 और i=2 पर 2b फिर 3c prefix में insert होते हैं; 2d अभी नहीं बदलता।

B गलत है: यह तीसरे पास के बाद पूरा sorted परिणाम है।

C गलत है: यह केवल पहले पास का परिणाम है।

D गलत है: insertion बायाँ prefix बढ़ाता है, पहले आखिरी जोड़ी नहीं sort करता।

S02

बताए गए selection sort में पाँच अलग keys का sorted array कितने passes, key comparisons और वास्तविक swaps लेता है?

A. 0 पास, 0 comparisons, 0 swaps B. 4 पास, 4 comparisons, 0 swaps C. 4 पास, 10 comparisons, 0 swaps D. 5 पास, 10 comparisons, 5 swaps

उत्तर: C

A गलत है: यह implementation sorted क्रम देखकर scans छोड़ता नहीं है।

B गलत है: चार comparisons इस input पर insertion के हैं; selection सभी suffix candidates scan करता है।

C सही है: n-1=4 पास और 4+3+2+1=10 key comparisons हैं; हर बार min_index=i है इसलिए swap नहीं है।

D गलत है: अंतिम singleton suffix को पास नहीं चाहिए और self-swaps स्पष्ट रूप से छोड़े गए हैं।

S03

[2a,2b,1c] को केवल key से sort करने पर बताए insertion और selection versions क्रमशः कौन-से अंतिम arrays देते हैं?

A. [1c,2b,2a]; [1c,2a,2b] B. [1c,2a,2b]; [1c,2b,2a] C. [1c,2a,2b]; [1c,2a,2b] D. [2a,2b,1c]; [1c,2b,2a]

उत्तर: B

A गलत है: परिणाम उलटे हैं; strict-greater insertion a को b से पहले रखता है।

B सही है: insertion बराबर जोड़ी का क्रम बचाता है; selection पहले 2a और 1c swap करके b को a से पहले रखता है।

C गलत है: first-minimum selection पहले long-distance swap में फिर भी 2a को 2b के पार भेजता है।

D गलत है: insertion 1c को आगे insert करता है; स्थिरता movement पर रोक नहीं है।

S04

Selection के पास i से पहले कौन-सा कथन इस implementation का सही outer-loop invariant है?

A. Suffix sorted है और prefix मनमाना हो सकता है। B. Prefix में ठीक मूल पहले i records स्थिर क्रम में हैं। C. हर जगह बराबर-key records का मूल आपसी क्रम बचा है। D. Prefix sorted है, उसकी हर key हर suffix key से <= है, और सभी मूल records बचे हैं।

उत्तर: D

A गलत है: selection बायाँ prefix अंतिम करता है; शेष suffix sorted होना ज़रूरी नहीं।

B गलत है: यह insertion के processed-original-prefix वाला गुण है; selection suffix में कहीं से रिकॉर्ड ला सकता है।

C गलत है: swap-based selection अस्थिर है, जैसा [2a,2b,1c] दिखाता है।

D सही है: अगला suffix minimum रखने से prefix का गुण बढ़ता है, और swaps सभी records बचाते हैं।

S05

n>=2 के scalable constant-cost model में इन implementations के लिए कौन-सा time-bound कथन tight है?

A. Insertion best Θ(n), worst Θ(n²); selection best और worst Θ(n²)। B. दोनों algorithms के best और worst Θ(n) हैं। C. Sorted होने पर insertion best Θ(1); selection best Θ(1) है। D. Insertion हमेशा Θ(n²); selection हमेशा Θ(n log n) है।

उत्तर: A

A सही है: sorted input पर insertion हर पास तुरंत रुकता है; selection हर बार सभी remaining suffix candidates scan करता है।

B गलत है: reverse distinct keys पर insertion के shifts quadratic हैं; selection comparisons हर क्रम में quadratic हैं।

C गलत है: दोनों n-1 passes करते हैं; selection अतिरिक्त रूप से n(n-1)/2 comparisons करता है।

D गलत है: insertion का best case linear है और इस selection algorithm की scan count quadratic है, n log n नहीं।

S06

Insertion sort में a[j-1].key > item.key से पहले j > 0 क्यों evaluate होता है?

A. इससे selection sort stable बनता है। B. यह keys घटाकर integer overflow रोकता है। C. && short-circuiting से hole के index 0 पर पहुँचने पर a[-1] पढ़ने से बचता है। D. यह साबित करता है कि हर non-NULL pointer में CAP live elements हैं।

उत्तर: C

A गलत है: यह guard insertion में है; स्थिरता केवल boundary test से नहीं, strict key comparison से आती है।

B गलत है: code keys घटाता नहीं, सीधे compare करता है; j>0 array index सुरक्षित करता है।

C सही है: j=0 पर && दायाँ operand छोड़ देता है, इसलिए j-1 array index के रूप में उपयोग नहीं होता।

D गलत है: capacity और lifetime caller के वादे हैं; boundary check pointer validity सिद्ध नहीं करता।