Quick Sort

Pivot के चारों ओर partition

Pivot चुनें। पुनर्व्यवस्थित करें ताकि सब छोटा उसके बाएँ और सब बड़ा दाएँ — अब pivot अपनी अंतिम जगह पर। दोनों ओर recurse करें। औसत O(n log n); worst O(n^2) यदि pivot हमेशा min/max हो।

Lomuto partition

i "pivot से छोटा" क्षेत्र की सीमा को ट्रैक करता है।

def quick_sort(a, lo=0, hi=None):
    if hi is None: hi = len(a) - 1
    if lo >= hi: return a
    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]   # pivot to its place
    quick_sort(a, lo, i - 1)
    quick_sort(a, i + 1, hi)
    return a

यह डिफ़ॉल्ट क्यों है

In place (O(log n) stack), cache-अनुकूल, और छोटे स्थिरांक इसे व्यवहार में merge sort से तेज़ बनाते हैं। Pivot को random या median-of-three चुनने से O(n^2) मामला अत्यंत दुर्लभ। Stable नहीं।

संबंधित तरकीब

Quickselect partition का पुनःउपयोग कर k-वाँ सबसे छोटा तत्व औसत O(n) में बिना पूरी तरह sort किए खोजता है।