# Quick Sort — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/quick-sort

> Pivot के चारों ओर partition करें, हर ओर recurse करें — in place तेज़, औसत O(n log n)।

## Pivot के चारों ओर partition

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

## Lomuto partition

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

```python
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 किए खोजता है।