📘 Lesson · Lesson 78

Selection & Insertion Sort

Selection vs Insertion Sort

दोनों sorted prefix बढ़ाते और O(1) extra space लेते हैं। Selection unsorted suffix से minimum चुनकर next slot में swap करता है। Insertion next key को save करके larger prefix elements shift करता और gap में key डालता है।

Point	Selection	Insertion
Nearly sorted	Θ(n²) comparisons	Θ(n) तक
Writes	O(n) swaps	Θ(n²) तक moves
Stable usual form	नहीं	हाँ

Selection Sort Trace

हर pass में remaining range का minimum खोजें और current position से swap करें। Prefix में final smallest values आते जाते हैं।

29 10 14 37 13
10 | 29 14 37 13
10 13 | 14 37 29
10 13 14 | 37 29
10 13 14 29 37

Selection Program

for (std::size_t i=0; i<values.size(); ++i) {
    std::size_t minimum=i;
    for (std::size_t j=i+1; j<values.size(); ++j)
        if (values[j]<values[minimum]) minimum=j;
    if (minimum!=i) std::swap(values[i],values[minimum]);
}

Minimum पूरा खोजने के बाद एक swap करें। Distant swap equal records का order बदल सकता है।

Insertion Sort Trace

Key save करें, उससे बड़े predecessors right shift करें और empty position में key लिखें।

29 10 14 37 13
10 29 | 14 37 13
10 14 29 | 37 13
10 14 29 37 | 13
10 13 14 29 37

Insertion Program

for (std::size_t i=1; i<values.size(); ++i) {
    int key=values[i];
    std::size_t j=i;
    while (j>0 && values[j-1]>key) {
        values[j]=values[j-1];
        --j;
    }
    values[j]=key;
}

Selection: 10 13 14 29 37 Insertion: 10 13 14 29 37

j>0 पहले check होने से unsigned index underflow नहीं होता।

Complexity और Stability

Property	Selection	Insertion
Best	Θ(n²)	Θ(n)
Average/Worst	Θ(n²)	Θ(n²)
Space	O(1)	O(1)
Stable	नहीं	हाँ, strict >
Adaptive	नहीं	हाँ

Decision Guide

Nearly sorted/small data: insertion अच्छा candidate।
Writes बहुत expensive: selection के limited swaps उपयोगी हो सकते हैं।
Large general range: std::sort।
Stable library result: std::stable_sort।
Θ(n log n) study: merge sort।

STL algorithms production choice समझाता है।

Mistakes, Tests और Practice

Selection inner loop में बार-बार swap न करें।
Insertion shifts से पहले key save करें।
j>0 check पहले रखें।
Stability के लिए shift condition strict > हो।

Empty, sorted, reverse, duplicate और negative inputs test करें; comparisons और moves count करें।

Authoritative संदर्भ

Definitions और complexity sources से verify किए गए हैं। Bubble sort भी compare करें।

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

Selection और insertion sort में मुख्य फर्क क्या है?

Selection हर pass में smallest remaining element चुनता है। Insertion next element को sorted prefix में सही position पर insert करता है।

Nearly sorted data पर कौन तेज है?

Insertion sort adaptive है और कम shifts होने पर Θ(n) के पास आ सकता है। Standard selection sort फिर भी Θ(n²) comparisons करता है।

कम writes कौन करता है?

Selection sort हर outer pass में अधिकतम एक swap करता है, इसलिए O(n) swaps। Expensive writes में यह उपयोगी हो सकता है।

क्या दोनों stable हैं?

Common swap-based selection sort stable नहीं है। Insertion sort तब stable है जब केवल key से strictly greater elements shift हों।

क्या extra array चाहिए?

नहीं। यहां के standard implementations in-place हैं और O(1) auxiliary space लेते हैं।

← Back to C++ Tutorial