Quick sort — pivot

Quick sort — pivot தேர்ந்து <, =, > பகுதிகளாகப் பிரித்து மீண்டும். சராசரி O(n log n); மோசமான pivot O(n²) — எனவே சீரற்ற pivot அல்லது introsort.

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

C++ std::sort — introsort. Java primitives sort — dual-pivot quicksort குடும்பம். நூலகம் random தரவில் in-place வேகம். pivot தவறானால் ஏற்கனவே sorted மீது மோசமான சூழல்.

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

pivot தேர்வு (முதல், நடு, median-of-three, சீரற்ற). partition நேரியல்; pivot இறுதி index. இடது/வலது மீண்டும். சீரற்ற pivot — எதிர்பார்ப்பு O(n log n). மூன்று-வழி partition — நகல் நிறைந்த அணிகள்.

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

import random


def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = random.choice(a)
    lows = [x for x in a if x < pivot]
    mids = [x for x in a if x == pivot]
    highs = [x for x in a if x > pivot]
    return quicksort(lows) + mids + quicksort(highs)


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

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

• சாய்வு recursion — stack வெடிப்பு.
• சம உறுப்புகள் ஒரு பக்கம் — O(n²).
• partition index ஒற்றைப் பிழை.

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

• சராசரியில் in-place வேகம்.
• சீரற்ற pivot / introsort பாதுகாப்பு.
• Lomuto / Hoare கற்றல்.