Dutch flag — மூன்று வகுப்புகள்

Dutch National Flag முறை, 0, 1, 2 போன்ற சிறிய மதிப்புகளை மூன்று தொடர்ச்சியான பகுதிகளாக ஒரே கடவுடன் (single pass) மாற்றுகிறது; கூடுதல் நினைவகம் O(1). இது மூன்று-வழி partition கருத்துக்கு அடிப்படை.

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

தரக் கட்டுப்பாடு வரிசையில் ஒவ்வொன்றும் “நீக்கு / மீண்டும் செய் / அனுப்பு” என மூன்று நிலைகள் மட்டுமே என்று கற்பனை செய்யுங்கள்; மூன்று பாதைகளுக்கு ஒரே முறையில் நகர்த்த வேண்டும். வீடியோ குறியீடு சில macroblock-களை சில வகுப்புகளாகப் பிரித்து ஒரே கடவில் குழும வேண்டும். மூன்று மட்ட enum + O(n) இடம் — இங்கு இந்த முறை.

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

மூன்று சுட்டிகள்: low — 0 பகுதி முடிவு, mid — அறியப்படாதவை நடத்தல், high — 2 பகுதி தொடக்கம். a[mid]==1 எனில் mid ஒரு படி. 0 எனில் low உடன் பரிமாற்றம்; low மற்றும் mid இரண்டும் முன்னேறும். 2 எனில் high உடன் பரிமாற்றம்; mid-ஐ உடனே அதிகரிக்காதீர்கள் — புதிய மதிப்பு மீண்டும் சோதிக்கப்பட வேண்டும்.

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

def sort012(nums: list[int]) -> None:
    lo = mid = 0
    hi = len(nums) - 1
    while mid <= hi:
        if nums[mid] == 0:
            nums[lo], nums[mid] = nums[mid], nums[lo]
            lo += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[hi] = nums[hi], nums[mid]
            hi -= 1


a = [2, 0, 2, 1, 1, 0]
sort012(a)
print(a)

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

• high பரிமாற்றத்திற்குப் பிறகு mid-ஐ தானாக +1 — தவறு.
• பல நிறங்களுக்கு தெளிவான உத்தி இல்லாமல் பொருந்த வைப்பது.
• high தொடக்க ஒற்றைப் பிழை.

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

• மூன்று மதிப்புகளுக்கு O(n) நேரம், O(1) இடம்.
• நகல் மிகுந்த quicksort இல் மூன்று-வழி partition அடிப்படை.
• நேர்காணல்: invariant முதலில் விளக்கவும்.