Insertion sort — கிட்டத்தட்ட sorted

Insertion sort ஒவ்வொரு புதிய உறுப்பையும் இதுவரை sorted பகுதியில் சரியான இடத்தில் செருகுகிறது — கையில் வரும் சீட்டுகளைப் போல. சிறிய n அல்லது கிட்டத்தட்ட sorted தரவில் சிறப்பு.

உண்மை உலகில் இது ஏன் முக்கியம்?

கிட்டத்தட்ட காலவரிசை பரிவர்த்தனைகள் — சில jitter-க்கு சில செருகும்கள் போதும். Android சிறிய அணிகளில் insertion, பெரியதில் quicksort. B-tree சிறிய fan-out பக்கங்களில் குறைந்த மறுசீரமைப்பு — கருத்து ஒத்தது.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

ஒவ்வொரு i-க்கும், இடது பக்கம் பெரியது என்றால் வலதுக்கு நகர்த்தி இடையில் செருகு. <= இல் நிறுத்தினால் stable. ஏற்கனவே sorted எனில் O(n); முழு தலைகீழ் O(n²). Timsort போன்ற hybrid இல் இது உதவுகிறது.

Pythonில் முயற்சி செய்வோம்

def insertion_sort(a: list[int]) -> list[int]:
    a = 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]
            j -= 1
        a[j + 1] = key
    return a


print(insertion_sort([5, 2, 4, 6, 1, 3]))

அடிக்கடி நேரும் தவறுகள்

• தற்காலிகம் இல்லாமல் நகர்த்தல் — மதிப்பு அழிவு.
• 0 எல்லை சோதனை தவறு — முடிவில்லா வளையம்.
• பெரிய சீரற்ற தரவில் சிந்தனையின்றிப் பயன்பாடு.

முக்கியச் சுருக்கக் குறிப்புகள்

• தகவமைப்பு: கிட்டத்தட்ட sorted இல் வேகம்.
• பொதுவாக stable.
• hybrid இல் n < ~50 வாசல்.