Bubble, Selection, Insertion Sort

हर एक डेटा कैसे हिलाता है

Bubble: बार-बार आसन्न गलत-क्रम जोड़े swap करें; बड़े मान अंत तक "bubble" होते हैं। Selection: हर पास बाकी का न्यूनतम खोजकर अगला रखता है। Insertion: अगला तत्व लेकर उसे बाएँ अपने sorted स्थान में सरकाएँ।

Insertion sort

व्यवहार में तीनों में सर्वश्रेष्ठ: लगभग-sorted डेटा पर O(n) और stable।

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]   # shift right
            j -= 1
        a[j + 1] = key        # drop key in place
    return a

जटिलता और स्थिरता

तीनों: O(n^2) औसत/worst, O(1) स्थान। Insertion सर्वोत्तम O(n)। Bubble और insertion stable (समान तत्वों का क्रम बनाए); selection नहीं। Selection सबसे कम swap (O(n)) करता है।

वास्तविकता जाँच

Production में आप library sort बुलाते हैं। ये इंटरव्यू के लिए और तेज़ sort के अंदर base case के रूप में मायने रखते हैं (जैसे Timsort छोटे run पर insertion sort उपयोग करता है)।