Selection sort

Selection sort — எஞ்சியவற்றில் சிறியதைத் தேர்ந்து முன்னே பரிமாற்றம். எழுதுதல் குறைவு; ஒப்பீடுகள் O(n²).

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

Flash எழுதுதல் சுழற்சி — சில சூழல்களில் எழுது குறைப்பு. சிறிய காட்சி மூன்று அளவுகோல் — சிறிய n மட்டும்.

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

வெளி i — நிரப்ப இடம்; உள் வளையம் i..n-1 இல் குறைந்த m; a[i], a[m] பரிமாற்றம். அண்டை அல்லாத பரிமாற்றம் — stable அல்ல. ஒப்பீடுகள் Θ(n²); பரிமாற்றங்கள் O(n).

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

def selection_sort(a):
    a = a[:]
    for i in range(len(a)):
        m = min(range(i, len(a)), key=lambda k: a[k])
        a[i], a[m] = a[m], a[i]
    return a


print(selection_sort([4, 5, 1, 3, 2]))

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

• இடம் இல்லாமல் stable — கடினம்.
• உள் scan எல்லை.
• production பெரிய அணி.

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

• O(n) பரிமாற்றம், O(n²) ஒப்பீடு.
• பாடப்புத்தக வடிவம் stable அல்ல.
• heap (மீண்டும் மீண்டும் min) க்கு படி.