Quick sort அடிப்படை

quick sort அடிப்படை — ஒரு pivot pass: சிறியவை இடது, பெரியவை வலது; பின் மீண்டும். மேம்பாடு முன் partition வளையம்.

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

Bootcamp — Lomuto வெள்ளைப் பலகை. போட்டி — விரைவு partition snippet; முதலில் அடிப்படை.

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

Lomuto: pivot பெரும்பாலும் கடைசி. i — “சிறிய பகுதி” எல்லை; a[j]<=p எனில் a[i] உடன் பரிமாற்றம், i++. இறுதியில் pivot இடம். [lo,i-1], [i+1,hi] மீண்டும்.

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

def lomuto_partition(a, lo, hi):
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i


nums = [5, 1, 4, 2, 8]
print(lomuto_partition(nums, 0, len(nums) - 1), nums)

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

• pivot இடம் ஒற்றைப் பிழை.
• <= / < கொள்கை.
• அனைத்தும் சமம் — மூன்று-வழி தேவை.

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

• partition இதயம் — பயிற்சி.
• 6 உறுப்பு நிலை வரைபு.
• Lomuto vs Hoare.