# فصل ۰۵ — `quicksort` و انتخابِ `pivot`

<div dir="rtl">

# فصل ۰۵ — `quicksort` و انتخابِ `pivot`

## در این فصل چه یاد می‌گیری

`merge sort` سریع بود ولی برای هر ادغام یک `list` تازه می‌ساخت. این فصل الگوریتمی می‌سازد که **همان مرتبه را در جای خودِ داده می‌گیرد** — بدونِ ساختنِ حتی یک فهرستِ کمکی.

و بعد خرابش می‌کنیم. **روی فهرستی که از قبل مرتب است، همین کد به `RecursionError` می‌خورد.** وقتی آن را با یک `stack` صریح درست می‌کنیم، عددِ واقعی بیرون می‌آید: **در `n = 2,000` تعدادِ مقایسه `1,999,000` است و ستونِ نسبت `4.00`** — یعنی دقیقاً همان `selection sort` فصلِ ۳. بعد **با یک خط تغییر**، همان عدد روی همان ورودی به حدودِ `24,000` برمی‌گردد.

![میله‌ای که یک دستهٔ کارت را حولِ یک کارتِ نشانه‌گذاری‌شده به دو گروهِ کوچک‌تر و بزرگ‌تر می‌راند](/lesson-assets/t4-s05-quicksort/prompt/01-image-partition.png)

آخر این فصل می‌توانی:

- افرازِ یک فهرست حولِ یک `pivot` را با دست انجام بدهی
- `quicksort` را `in-place` بنویسی و درستی‌اش را ثابت کنی
- بدترین حالتش را **بسازی** و با شمارش نشانش بدهی
- بگویی `pivot` تصادفی دقیقاً چه چیزی را عوض می‌کند و چه چیزی را نه

## قبل از شروع

**از فصلِ ۱:** بازنویسیِ یک `recursion` به حلقه — بخشِ ۴ این فصل واقعاً به آن احتیاج پیدا می‌کند.

**از ترمِ ۳ فصلِ ۴:** ورودیِ خصمانه، و اینکه بدترین حالتِ یک ساختار وقتی خطرناک است که **کسِ دیگری ورودی را انتخاب کند**. `quicksort` نمونهٔ کلاسیکِ همین حرف است.

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | کمتر از یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-4-recursion-sorting-searching/session-05-quicksort.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. افراز، با دست

ایدهٔ `quicksort` از طرفِ دیگرِ «تقسیم و حل» می‌آید. `merge sort` کورکورانه از وسط می‌شکست و کارِ سخت را در **ادغام** انجام می‌داد. `quicksort` برعکس است: **کارِ سخت را در خودِ شکستن انجام می‌دهد، و بعد هیچ ادغامی لازم نیست.**

یک عضو را `pivot` می‌گیریم و فهرست را طوری می‌چینیم که هر چیزِ کوچک‌ترش سمتِ چپش باشد و هر چیزِ بزرگ‌ترش سمتِ راستش. **آن‌وقت `pivot` سرِ جای نهایی‌اش است** و دو طرفش دو مسئلهٔ مستقل‌اند.

</div>

```python
def partition(a, lo, hi, stats):
    """همهٔ عضوهای کوچک‌تر از a[lo] را سمتِ چپ می‌برد و جای نهاییِ pivot را برمی‌گرداند."""
    pivot = a[lo]
    i = lo + 1
    for j in range(lo + 1, hi + 1):
        stats["comparisons"] += 1
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[lo], a[i - 1] = a[i - 1], a[lo]    # pivot به جای نهایی‌اش می‌رود
    return i - 1


demo = [29, 10, 14, 37, 13, 25, 11, 18]
box = {"comparisons": 0}
work = list(demo)
place = partition(work, 0, len(work) - 1, box)
print("ورودی        :", demo)
print("pivot        :", demo[0])
print("بعد از افراز :", work)
print("جای نهاییِ pivot:", place, "· مقایسه:", box["comparisons"])
print("سمتِ چپ همه کوچک‌ترند؟", all(x < demo[0] for x in work[:place]))
print("سمتِ راست همه بزرگ‌ترند؟", all(x >= demo[0] for x in work[place + 1:]))
```

```text
ورودی        : [29, 10, 14, 37, 13, 25, 11, 18]
pivot        : 29
بعد از افراز : [18, 10, 14, 13, 25, 11, 29, 37]
جای نهاییِ pivot: 6 · مقایسه: 7
سمتِ چپ همه کوچک‌ترند؟ True
سمتِ راست همه بزرگ‌ترند؟ True
```

<div dir="rtl">

**هشت عضو، هفت مقایسه، و هیچ فهرستِ تازه‌ای ساخته نشد** — فقط عضوها داخلِ همان `list` جابه‌جا شدند. **اسمِ این کار `in-place` است.**

**ولی به خروجی خوب نگاه کن: دو طرفِ `pivot` مرتب نیستند، فقط تفکیک شده‌اند.** و همین کافی است، چون هر طرف را می‌شود با همان روش حل کرد.

**و یک چیزِ دیگر هم در همین خروجی هست که بعداً به کارمان می‌آید:** `pivot` عددِ `29` بود و در جای ششم نشست، یعنی شش عضو کوچک‌ترش بودند و یکی بزرگ‌تر. **تقسیم عادلانه نشد.** اینکه چقدر عادلانه شود، تماماً به این بستگی دارد که `pivot` چه عددی باشد.

## ۲. `quicksort` روی ورودیِ تصادفی

</div>

```python
def quicksort(values):
    """نسخه‌ای با recursion، in-place روی یک کپی."""
    a = list(values)
    stats = {"comparisons": 0, "depth": 0}

    def go(lo, hi, depth):
        stats["depth"] = max(stats["depth"], depth)
        if lo >= hi:                     # حالتِ پایه: صفر یا یک عضو
            return
        p = partition(a, lo, hi, stats)
        go(lo, p - 1, depth + 1)
        go(p + 1, hi, depth + 1)

    go(0, len(a) - 1, 1)
    return a, stats


rng = random.Random(SEED)
BIG = [1_000, 2_000, 4_000, 8_000]
shuffled = {n: rng.sample(range(10 * n), n) for n in BIG}
out, stats = quicksort(shuffled[1_000])
print("با sorted یکی است؟", out == sorted(shuffled[1_000]))
print("مقایسه:", stats["comparisons"], "· عمق:", stats["depth"])
```

```text
با sorted یکی است؟ True
مقایسه: 10150 · عمق: 20
```

<div dir="rtl">

> 🤔 **اول حدس بزن:** ستونِ نسبتِ مقایسه‌ها چه عددی می‌دهد؟ و عمق چطور؟ **دو عدد بنویس**، بعد جدول را ببین.

</div>

```python
print("— ورودیِ تصادفی: مقایسه")
table([(n, quicksort(shuffled[n])[1]["comparisons"]) for n in BIG], "مقایسه", ",d")
print("\n— ورودیِ تصادفی: عمقِ recursion")
table([(n, quicksort(shuffled[n])[1]["depth"]) for n in BIG], "عمق", ",d")
```

```text
— ورودیِ تصادفی: مقایسه
         n            مقایسه     نسبت به سطر قبل
     1,000            10,150                   —
     2,000            26,066                2.57
     4,000            55,429                2.13
     8,000           124,001                2.24

— ورودیِ تصادفی: عمقِ recursion
         n               عمق     نسبت به سطر قبل
     1,000                20                   —
     2,000                25                1.25
     4,000                26                1.04
     8,000                31                1.19
```

<div dir="rtl">

**نسبت‌ها حولِ `2.2` — همان امضای `O(n log n)` فصلِ ۴.** عددِ مطلقشان هم نزدیکِ `merge sort` است: در `n = 8,000` عددِ `124,001` در برابرِ `93,704`.

**ولی ستونِ عمق فرقِ مهمی با فصلِ ۴ دارد.** آن‌جا عمق دقیقاً `log₂ n` بود و از `11` به `14` رفت. این‌جا از `20` به `31` می‌رود — **حدودِ دو برابرِ `log₂ n`، و لرزان.** دلیلش همان چیزی است که در بخشِ ۱ دیدیم: `merge sort` همیشه دقیقاً از وسط می‌شکند و `quicksort` هر جا که `pivot` بیفتد.

**و همین «هر جا که بیفتد» جای زخم است.**

## ۳. بدترین حالت را بساز

بدترین `pivot` ممکن، **کوچک‌ترین عضوِ بازه** است: آن‌وقت سمتِ چپ خالی می‌ماند و سمتِ راست فقط یک عضو کوچک‌تر می‌شود. یعنی به‌جای نصف شدن، هر بار یکی کم می‌شود.

**و ساختنِ این حالت هیچ زحمتی ندارد:** کد ما همیشه عضوِ اول را `pivot` می‌گیرد، پس کافی است فهرست از قبل مرتب باشد.

</div>

```python
climbing = sorted(shuffled[2_000])
print("ورودی از پیش مرتب است؟", climbing == sorted(climbing))
try:
    quicksort(climbing)
except RecursionError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
ورودی از پیش مرتب است؟ True
RecursionError: maximum recursion depth exceeded
```

<div dir="rtl">

> 🔧 **اگر کار نکرد:** این خطا این‌جا یک **علامت** است، نه یک باگ. عمقِ `recursion` برابرِ `n` شده و از سقفِ پایتون رد کرده. **وسوسهٔ اول این است که سقف را بالا ببری — و آن دقیقاً کارِ غلط است**، چون مسئله عمق نیست، مسئله این است که تقسیم اصلاً انجام نمی‌شود. سقف را که بالا ببری، برنامه به‌جای یک استثنای تمیز، **ساعت‌ها کار می‌کند یا نشست را می‌کشد**.
>
> **راهِ درست، برداشتنِ `recursion` است.** فصلِ ۱ گفت هر `recursion` را می‌شود به حلقه برگرداند؛ این‌جا جایی است که واقعاً باید این کار را بکنی.

## ۴. همان الگوریتم، با یک `stack` صریح

پایتون فراخوانی‌های تمام‌نشده را روی `call stack` نگه می‌داشت. **ما همان کار را با یک `list` انجام می‌دهیم** — همان `stack`ی که ترمِ ۲ فصلِ ۷ ساخت، با همان انضباطِ `LIFO`. به‌جای فراخوانی، بازه‌های کارنکرده را در آن می‌ریزیم.

</div>

```python
def quicksort_stack(values, pick=None):
    """همان الگوریتم، با یک stack صریح به‌جای call stack."""
    a = list(values)
    stats = {"comparisons": 0, "max_todo": 0}
    todo = [(0, len(a) - 1)]
    while todo:
        stats["max_todo"] = max(stats["max_todo"], len(todo))
        lo, hi = todo.pop()
        if lo >= hi:
            continue
        if pick is not None:                 # pivot را عوض کن
            k = pick(lo, hi)
            a[lo], a[k] = a[k], a[lo]
        p = partition(a, lo, hi, stats)
        todo.append((lo, p - 1))
        todo.append((p + 1, hi))
    return a, stats


check = shuffled[1_000]
one = quicksort(check)
two = quicksort_stack(check)
print("دو نسخه یک جواب می‌دهند؟", one[0] == two[0] == sorted(check))
print("و یک تعداد مقایسه؟",
      one[1]["comparisons"] == two[1]["comparisons"], "·",
      two[1]["comparisons"])
print("روی ورودیِ از پیش مرتب هم کار می‌کند؟",
      quicksort_stack(climbing)[0] == climbing)
```

```text
دو نسخه یک جواب می‌دهند؟ True
و یک تعداد مقایسه؟ True · 10150
روی ورودیِ از پیش مرتب هم کار می‌کند؟ True
```

<div dir="rtl">

**همان جواب، همان تعدادِ مقایسه، و این بار روی ورودیِ مرتب هم تمام می‌شود.** حالا می‌شود بدترین حالت را واقعاً اندازه گرفت.

> 🤔 **اول حدس بزن:** روی ورودیِ از پیش مرتب، ستونِ نسبتِ مقایسه‌ها چه عددی می‌دهد؟ **بنویسش**، بعد جدول را ببین.

</div>

```python
SORTED_LADDER = [250, 500, 1_000, 2_000]
climb = {n: list(range(n)) for n in SORTED_LADDER}
print("— ورودیِ از پیش مرتب، pivot = عضوِ اول")
table([(n, quicksort_stack(climb[n])[1]["comparisons"]) for n in SORTED_LADDER],
      "مقایسه", ",d")
```

```text
— ورودیِ از پیش مرتب، pivot = عضوِ اول
         n            مقایسه     نسبت به سطر قبل
       250            31,125                   —
       500           124,750                4.01
     1,000           499,500                4.00
     2,000         1,999,000                4.00
```

<div dir="rtl">

**`4.00` — یعنی `O(n²)`.** و عددهایش سطر به سطر **دقیقاً همان عددهای `selection sort` فصلِ ۳** هستند: `31,125`، `124,750`، `499,500`، `1,999,000`.

**این تصادف نیست.** وقتی هر افراز فقط یک عضو را جدا می‌کند، مجموعِ مقایسه‌ها `(n-1) + (n-2) + … + 1` می‌شود — همان جمعی که `selection sort` هم می‌سازد. **الگوریتمی که اسمش `quick` است، روی مرتب‌ترین ورودیِ ممکن، به سادگی‌ترین الگوریتمِ ممکن تبدیل شد.**

## ۵. یک خط تغییر

اشکال در الگوریتم نیست، در **قاعدهٔ انتخابِ `pivot`** است. «همیشه عضوِ اول» یک قاعدهٔ ثابت است و هر قاعدهٔ ثابتی یک ورودیِ بد دارد. پس `pivot` را تصادفی برمی‌داریم.

> 🤔 **اول حدس بزن:** همان ورودیِ **از پیش مرتب**، فقط با `pivot` تصادفی. **ستونِ نسبت را بنویس** — و یک عددِ دوم هم بنویس: در `n = 2,000` مقایسه‌ها از `1,999,000` به چند می‌رسند؟ **مرتبه و عدد دو حدسِ متفاوت‌اند و هر دو را می‌خواهیم.**

</div>

```python
print("— همان ورودیِ مرتب، pivot تصادفی")
picker = random.Random(SEED)
table([(n, quicksort_stack(climb[n], lambda lo, hi: picker.randrange(lo, hi + 1))[1]["comparisons"])
       for n in SORTED_LADDER], "مقایسه", ",d")
```

```text
— همان ورودیِ مرتب، pivot تصادفی
         n            مقایسه     نسبت به سطر قبل
       250             2,653                   —
       500             4,571                1.72
     1,000            10,032                2.19
     2,000            23,938                2.39
```

<div dir="rtl">

**`1,999,000` به `23,938` رسید — روی همان ورودی، با همان کدِ افراز.** و ستونِ نسبت از `4.00` به حدودِ `2.2` برگشت: `O(n log n)`.

</div>

```python
picker2 = random.Random(SEED)
print("— ورودیِ مرتبِ بزرگ‌تر، pivot تصادفی")
table([(n, quicksort_stack(list(range(n)), lambda lo, hi: picker2.randrange(lo, hi + 1))[1]["comparisons"])
       for n in BIG], "مقایسه", ",d")
```

```text
— ورودیِ مرتبِ بزرگ‌تر، pivot تصادفی
         n            مقایسه     نسبت به سطر قبل
     1,000            11,951                   —
     2,000            24,661                2.06
     4,000            55,531                2.25
     8,000           115,750                2.08
```

<div dir="rtl">

> ⚠️ **مواظب باش:** `pivot` تصادفی بدترین حالت را **حذف نمی‌کند**؛ فقط کاری می‌کند که کسی نتواند آن را **سفارش بدهد**. با بدشانسیِ محض هنوز ممکن است هر بار بدترین `pivot` انتخاب شود — احتمالش فقط آن‌قدر کوچک است که به آن فکر نمی‌کنیم.
>
> **و این دقیقاً همان پادزهری است که ترمِ ۳ فصلِ ۴ برای `hash table` دید:** آن‌جا هم مسئله این بود که مهاجم قاعدهٔ ثابت را می‌داند، و راهِ حل تصادفی کردنِ همان قاعده بود. **دو ساختارِ کاملاً متفاوت، یک الگوی دفاعیِ واحد.**

## ۶. `in-place` رایگان نیست

`quicksort` هیچ فهرستِ تازه‌ای برای داده نمی‌سازد. ولی بازه‌های کارنکرده جایی باید بمانند — روی `call stack` یا در `todo`. **و آن جا هم حافظه است.**

> 🤔 **اول حدس بزن:** بیشترین اندازهٔ `todo` را برای سه حالت حدس بزن: ورودیِ مرتب با `pivot` اول، همان ورودی با `pivot` تصادفی، و ورودیِ تصادفی. **برای هر سه بنویس با هشت برابر شدنِ `n` چند برابر می‌شوند** — و مخصوصاً بنویس آیا انتظار داری هر سه یک شکل باشند.

</div>

```python
picker3 = random.Random(SEED)
print("— بیشترین اندازهٔ stackِ صریح (حافظهٔ کمکی)")
print(f"{'n':>8}{'مرتب، pivot اول':>20}{'مرتب، pivot تصادفی':>22}{'تصادفی':>12}")
for n in BIG:
    first = quicksort_stack(list(range(n)))[1]["max_todo"]
    rand = quicksort_stack(list(range(n)), lambda lo, hi: picker3.randrange(lo, hi + 1))[1]["max_todo"]
    mixed = quicksort_stack(shuffled[n])[1]["max_todo"]
    print(f"{n:>8,}{first:>20,}{rand:>22,}{mixed:>12,}")
```

```text
— بیشترین اندازهٔ stackِ صریح (حافظهٔ کمکی)
       n     مرتب، pivot اول    مرتب، pivot تصادفی      تصادفی
   1,000               1,000                    14          12
   2,000               2,000                    16          18
   4,000               4,000                    18          17
   8,000               8,000                    20          18
```

<div dir="rtl">

**ستونِ اول دقیقاً `n` است و دو ستونِ دیگر با هشت برابر شدنِ `n` فقط از `14` به `20` و از `12` به `18` می‌روند.** یعنی حافظهٔ کمکیِ `quicksort` بینِ `O(log n)` و `O(n)` است و **همان چیزی تعیینش می‌کند که مرتبهٔ زمانش را تعیین می‌کرد: کیفیتِ `pivot`.**

(دلیلِ عددِ `n` در ستونِ اول این است که هر افراز یک بازهٔ **خالی** هم تولید می‌کند و کدِ ما آن را هم روی `todo` می‌گذارد. کنار گذاشتنِ بازه‌های خالی، تمرینِ اجباریِ همین فصل است.)

**مقایسه‌اش با فصلِ ۴ را صریح بنویس:** `merge sort` در `n = 8,000` روی هم `103,808` عضو کپی می‌کرد و در هر لحظه به اندازهٔ `n` حافظهٔ اضافه داشت. `quicksort` روی ورودیِ تصادفی **هجده جفت عدد** نگه می‌دارد. **این معاملهٔ اصلیِ بینِ این دو الگوریتم است.**

</div>

```python
print("— ورودیِ تصادفی (زمان)")
table([(n, 1000 * clock(lambda v=shuffled[n]: quicksort_stack(v), repeat=2))
       for n in BIG], "زمان (ms)", ",.1f")
same = climb[2_000]
slow = clock(lambda: quicksort_stack(same), repeat=2)
picker4 = random.Random(SEED)
fast = clock(lambda: quicksort_stack(same, lambda lo, hi: picker4.randrange(lo, hi + 1)), repeat=2)
print(f"\nورودیِ مرتب، n = 2,000  ·  pivot اول: {1000 * slow:,.1f} ms"
      f"  ·  pivot تصادفی: {1000 * fast:,.1f} ms  ·  نسبت: {slow / fast:,.0f}")
```

```text-approx
— ورودیِ تصادفی (زمان)
         n         زمان (ms)     نسبت به سطر قبل
     1,000               1.7                   —
     2,000               4.3                2.54
     4,000               8.6                1.98
     8,000              24.5                2.86

ورودیِ مرتب، n = 2,000  ·  pivot اول: 206.4 ms  ·  pivot تصادفی: 4.5 ms  ·  نسبت: 46
```

<div dir="rtl">

**روی این ماشین، یک خط تغییر در انتخابِ `pivot` چهل‌وشش برابر شد.** ولی به شمارشِ بخشِ ۴ و ۵ برگرد: آن‌ها روی همین `n` نسبتِ `1,999,000` به `23,938`، یعنی حدودِ **۸۳** برابر می‌دادند. **فاصلهٔ این دو عدد خودش یک درس است:** نسخهٔ `pivot` تصادفی به‌ازای هر افراز یک عددِ تصادفی هم می‌سازد و یک جابه‌جاییِ اضافه می‌کند، پس هر مقایسه‌اش گران‌تر تمام می‌شود. **چیزی که ماشین‌به‌ماشین کم‌تر تکان می‌خورد نسبتِ شمارش است؛ نسبتِ زمان همیشه از آن کم‌تر درمی‌آید.**

> ✅ **چک کن:** به‌جای `pivot` تصادفی، **میانهٔ سه عضو** را بردار: اولین، وسطی و آخرینِ بازه را ببین و عضوِ میانی‌شان را با `a[lo]` جابه‌جا کن. حالا جدولِ بخشِ ۵ را دوباره بگیر. **روی ورودیِ از پیش مرتب باید عددی نزدیکِ `pivot` تصادفی بدهد و ستونِ نسبتش حولِ `2` بماند.** اگر باز `4.00` گرفتی، احتمالاً میانه را درست حساب نکرده‌ای و همچنان کوچک‌ترین را برمی‌داری.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** یک الگوریتمِ واحد با سه قاعدهٔ `pivot` و دو نوع ورودی، با جوابِ تأییدشدهٔ برابر با `sorted` — و نسخهٔ `recursion`دار و نسخهٔ `stack`دار که تعدادِ مقایسه‌شان هم برابر تأیید شد. **در کدام بازهٔ `n`؟** ۱٬۰۰۰ تا ۸٬۰۰۰ برای حالت‌های `n log n` و ۲۵۰ تا ۲٬۰۰۰ برای بدترین حالت — **چون در بدترین حالت، `n = 8,000` سی‌ودو میلیون مقایسه می‌شود.** **با چند تکرار، و کمینه یا میانگین؟** جدول‌های شمارش یک اجرا و قطعی (تصادفی‌بودنِ `pivot` هم با `SEED` مهار شده)؛ جدولِ زمان دو تکرار به‌علاوهٔ گرم‌کننده، کمینه.

> 🤖 **از دستیارت بپرس:** «چرا `quicksort` روی ورودیِ از پیش مرتب بدترین حالتش را نشان می‌دهد؟» بعد این را هم بپرس: **«`pivot` تصادفی بدترین حالت را از بین می‌برد یا نه؟»** — جوابِ درست باید بگوید نه، فقط دیگر کسی نمی‌تواند سفارشش بدهد. اگر دستیارت گفت «بدترین حالت دیگر ممکن نیست»، **از او بخواه احتمالش را برایت حساب کند.**

## واژه‌های تازهٔ این فصل

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| `quicksort` | کوییک‌سورت | مرتب‌سازی با افرازِ پیاپی حولِ یک عضوِ انتخاب‌شده |
| `pivot` | پیوت | عضوی که فهرست حولِ آن به کوچک‌تر و بزرگ‌تر تقسیم می‌شود |
| partition | پارتیشن | خودِ عملِ تقسیم کردن حولِ `pivot` |
| `in-place` | این‌پلیس | الگوریتمی که داده را در جای خودش جابه‌جا می‌کند |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا ورودیِ از پیش مرتب برای این نسخه از `quicksort` بدترین ورودی است؟

**تمرینِ اجباری:** `quicksort_stack` را طوری تغییر بده که بازه‌های خالی را اصلاً روی `todo` نگذارد. **جدولِ بیشترین اندازهٔ `stack` بخشِ ۶ را دوباره بگیر.** سؤالِ اصلی: **ستونِ «مرتب، `pivot` اول» چه می‌شود، و آیا تعدادِ مقایسه‌ها هم عوض شد؟** جوابت باید صریح بگوید کدام هزینه درست شد و کدام دست‌نخورده ماند.

**تمرینِ ستاره‌دار ⭐:** ورودی‌ای بساز که `pivot` = عضوِ **آخر** را به بدترین حالت ببرد، و ورودی‌ای دیگر که `pivot` = **میانهٔ سه عضو** را. **قبل از اجرا پیش‌بینی کن** هرکدام در `n = 1,000` چند مقایسه می‌خورد، بعد اجرا کن و **خطای پیش‌بینی‌ات را بنویس**. سؤالِ آخر: **برای `pivot` تصادفی چنین ورودی‌ای می‌شود ساخت یا نه؟** جوابت باید بگوید مهاجم دقیقاً چه چیزی را باید بداند.

## در فصل بعد

سه الگوریتم نوشتیم و هیچ‌کدام از `n log n` بهتر نشد. **این یک تصادف نیست و فصلِ بعد ثابتش می‌کند** — نه با اندازه‌گیری، با شمردن: تعدادِ ترتیب‌های ممکنِ `n` عضو `n!` است و هر مقایسه حداکثر آن را نصف می‌کند.

بعد عددش را می‌گیریم: **در `n = 8,000` کمترین تعدادِ مقایسهٔ ممکن `92,193` است و `merge sort` ما `93,704` می‌کند — نسبتِ `1.02`.** و آخرش الگوریتمی می‌آوریم که این مرز را می‌شکند، چون **اصلاً مقایسه نمی‌کند** — و همان‌جا اندازه می‌گیریم که کجا برنده است و کجا **۱۹۷ برابر** بازنده.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t4/s05-quicksort (یادستان, Yaadestan)
