பப்பிள் சார்ट், இன்செர்শன் சார்ट் மற்றும் செலக்ஷன் சார்ட் ஆகியவற்றை விளக்குங்கள்.

இவை மூன்று எளிய O(n²) ஒப்பீட்டு வரிசைப்படுத்தல் முறைகள். பெரிய உள்ளீடுகளுக்கு அவை மெதுவாக இருக்கும் ஆனால் புரிந்துகொள்ள எளிதாகவும் வரிசைப்படுத்தலின் இயலாண்மையை பயிற்றுவிப்பதற்கு பயனுள்ளதாகவும் இருக்கும்.

ஒவ்வொன்றும் எவ்வாறு வேலை செய்கிறது

• பப்பிள் சார்ட்: அருகிலுள்ள ஆர்டர் செய்யாத ஜோடிகளை மீண்டும் மீண்டும் பரிமாற்றம் செய்யுங்கள்; பெரிய மதிப்புகள் ஒவ்வொரு பாஸிலும் இறுதிக்கு "பப்பிள்" செய்கின்றன.
• செலக்ஷன் சார்ட்: வரிசைப்படுத்தப்படாத பகுதியின் குறைந்தபட்சத்தைக் கண்டுபிடித்து அதை இடத்தில் பரிமாற்றம் செய்யுங்கள்.
• இன்செர்ஷன் சார்ட்: ஒரு வரிசைப்படுத்தப்பட்ட முன்னொட்டை பெரிதாக்குங்கள் ஒவ்வொரு புதிய உறுப்பையும் அதன் சரியான இடத்தில் செருகுவதன் மூலம்.

உதாரணம் (insertion sort)

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]                  # element to place
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]       # shift bigger elements right
            j -= 1
        arr[j + 1] = key              # drop key into the gap
    return arr

insertion_sort([5, 2, 4, 1])          # -> [1, 2, 4, 5]

ஒப்பீடு

எப்போது பயன்படுத்த வேண்டும் / சிக்கல்கள்

இன்செர்ஷன் சார்ட் சிறிய அல்லது கிட்டத்தட்ட வரிசைப்படுத்தப்பட்ட வரிசைகளுக்கு உண்மையில் வேகமாக இருக்கிறது மற்றும் ஹைப்பிரிட் வரிசைப்படுத்தல் முறைகளுக்குள் பயன்படுத்தப்படுகிறது. பெரிய வரிசைப்படுத்தப்படாத தரவுகளைக் குறிக்கும் மூன்றையும் தவிர்க்கவும் — இதற்கு பதிலாக O(n log n) வரிசைப்படுத்தல் முறைகளைப் பயன்படுத்தவும்.

இது ஏன் முக்கியமானது

இந்த வரிசைப்படுத்তல் முறைகள் மாறிலிகள், பரிமாற்றங்கள் மற்றும் நிலைத்தன்மைக்கான உள்ளுணர்வை உருவாக்குகின்றன உங்கள் முன்னேறிய வழிமுறைகளை கையாளும் முன்.

இன்செர்ஷன் சார்ட் குறிப்பாக உற்பத்தி வரிசைப்படுத்தல் முறைகளுக்குள் (Timsort போன்றவை) சிறிய சப்வாரிக்கு தோன்றுகிறது.

அவை ஏன் O(n²) என்பதை அறிந்துகொள்வது O(n log n) வரிசைப்படுத்தல் முறைகளுக்கு தாவுவதை அর்థপூর்ணமாக்குகிறது.