# فصل ۰۶ — چرا هیچ مرتب‌سازیِ مقایسه‌ای بهتر از `n log n` نیست — و کِی این حرف باطل است

<div dir="rtl">

# فصل ۰۶ — چرا هیچ مرتب‌سازیِ مقایسه‌ای بهتر از `n log n` نیست — و کِی این حرف باطل است

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

سه فصل الگوریتم نوشتیم و هیچ‌کدام از `n log n` جلوتر نرفت. این فصل نشان می‌دهد **چرا هیچ‌وقت نمی‌رود** — و استدلالش هیچ ربطی به الگوریتم ندارد؛ فقط **شمردن** است.

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

و آخرش الگوریتمی می‌آوریم که از این مرز رد می‌شود، چون **اصلاً مقایسه نمی‌کند**. اندازه می‌گیریم که کجا برنده است — **۷۱ برابر سریع‌تر از `merge sort` ما** — و کجا **۱۹۷ برابر** بازنده.

![ترازویی که در هر توزین یک دستهٔ ممکن را نصف می‌کند، کنارِ قفسه‌ای از خانه‌های شماره‌دار](/lesson-assets/t4-s06-sorting-lower-bound/prompt/01-image-lower-bound.png)

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

- بگویی چرا `n!` ترتیبِ ممکن، مرزی برای تعدادِ مقایسه‌ها می‌سازد
- فاصلهٔ الگوریتمِ خودت با آن مرز را حساب کنی
- `counting sort` را بنویسی و بگویی چه شرطی دارد
- **با عدد** بگویی آن شرط کِی به‌صرفه است و کِی فاجعه

## قبل از شروع

**از فصلِ ۴:** `merge sort` و شمارشِ مقایسه‌هایش — کدش این‌جا دوباره، فشرده، می‌آید تا فصل خودبسنده باشد.

**از ترمِ ۱ فصلِ ۶:** خانوادهٔ منحنی‌های رشد، و مخصوصاً اینکه `log n` چقدر کند بالا می‌رود.

</div>

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

<div dir="rtl">

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

## ۱. چند جوابِ ممکن وجود دارد؟

مرتب کردن یعنی **پیدا کردنِ یک ترتیبِ خاص از بینِ همهٔ ترتیب‌های ممکن**. پس اولین سؤال این است: چند ترتیب ممکن است؟

</div>

```python
import math
from itertools import permutations

for n in (3, 4, 5, 10, 20):
    print(f"n = {n:>2}   ترتیب‌های ممکن = {math.factorial(n):,}")

print("\nهمهٔ ترتیب‌های سه عضو:")
for p in permutations("abc"):
    print("  ", "".join(p))
```

```text
n =  3   ترتیب‌های ممکن = 6
n =  4   ترتیب‌های ممکن = 24
n =  5   ترتیب‌های ممکن = 120
n = 10   ترتیب‌های ممکن = 3,628,800
n = 20   ترتیب‌های ممکن = 2,432,902,008,176,640,000

همهٔ ترتیب‌های سه عضو:
   abc
   acb
   bac
   bca
   cab
   cba
```

<div dir="rtl">

**برای سه عضو شش ترتیب، و برای بیست عضو عددی با نوزده رقم.** الگوریتمِ مرتب‌سازی باید بتواند بگوید ورودی کدام‌یک از این‌ها بوده.

> 🌱 **ریشه‌اش کجاست:** «چند جور می‌شود `n` چیز را پشتِ سرِ هم چید» همان **جایگشت** است و در [ریشه ترمِ ۶ فصل ۱](/courses/risheh/lessons/term-6-probability-statistics/session-01-counting) با اصلِ ضرب ساخته می‌شود: برای جای اول `n` انتخاب داری، برای جای دوم `n-1` تا، و همین‌طور تا آخر. **حاصل‌ضربشان می‌شود `n!`** — و همان فصل نشان می‌دهد این عدد چقدر زود از هر عددِ آشنایی بزرگ‌تر می‌شود.

## ۲. هر مقایسه چه چیزی به تو می‌دهد

حالا سؤالِ دوم: یک مقایسه چقدر از این ابهام را کم می‌کند؟

**جوابش «کمی» نیست، یک عددِ دقیق است.** هر مقایسه دو جوابِ ممکن دارد — بله یا نه. پس بعد از `k` مقایسه، حداکثر `2^k` مسیرِ متفاوت طی کرده‌ای، و هر مسیر فقط می‌تواند به **یک** ترتیب ختم شود.

**پس برای اینکه الگوریتم بتواند هر `n!` ترتیب را از هم تشخیص بدهد، باید `2^k` دستِ‌کم به `n!` برسد.**

</div>

```python
print(f"{'مقایسه':>8}{'حالتِ قابلِ تفکیک (2^k)':>26}{'برای ۳ عضو کافی است؟':>24}")
for k in range(1, 4):
    print(f"{k:>8}{2 ** k:>26,}{str(2 ** k >= math.factorial(3)):>24}")
```

```text
  مقایسه   حالتِ قابلِ تفکیک (2^k)    برای ۳ عضو کافی است؟
       1                         2                   False
       2                         4                   False
       3                         8                    True
```

<div dir="rtl">

**با دو مقایسه فقط چهار حالت را می‌شود از هم جدا کرد و ما شش حالت داریم.** پس هیچ الگوریتمِ مقایسه‌ای — هیچ‌کدام، هرچقدر هم زیرک — نمی‌تواند سه عضو را همیشه با دو مقایسه مرتب کند. **این حرف دربارهٔ یک الگوریتمِ خاص نیست؛ دربارهٔ همهٔ الگوریتم‌های ممکن است، حتی آن‌هایی که هنوز نوشته نشده‌اند.**

همین شرط را برای `n` بزرگ می‌نویسیم: از `2^k ≥ n!` نتیجه می‌شود که `k` دستِ‌کم `log₂(n!)` است.

</div>

```python
def log2_factorial(n):
    """log2(n!) بدونِ ساختنِ خودِ n! — جمعِ لگاریتم‌ها."""
    return sum(math.log2(i) for i in range(2, n + 1))


for n in (10, 100, 1_000):
    print(f"n = {n:>5}   مرزِ پایین = {math.ceil(log2_factorial(n)):>7,} مقایسه"
          f"   ·   n × log2(n) = {n * math.log2(n):>9,.0f}")
```

```text
n =    10   مرزِ پایین =      22 مقایسه   ·   n × log2(n) =        33
n =   100   مرزِ پایین =     525 مقایسه   ·   n × log2(n) =       664
n =  1000   مرزِ پایین =   8,530 مقایسه   ·   n × log2(n) =     9,966
```

<div dir="rtl">

**ستونِ دوم و سوم همیشه در همان حدودِ هم می‌مانند** — نسبتشان از `0.66` به `0.86` می‌رود و به یک نزدیک‌تر می‌شود. یعنی `log₂(n!)` و `n log₂ n` **از یک خانواده‌اند** و همان `O(n log n)` را می‌گویند. **پس مرزِ پایینِ مرتب‌سازیِ مقایسه‌ای از مرتبهٔ `n log n` است، و این را با شمردن ثابت کردیم، نه با اندازه‌گیری.**

## ۳. الگوریتمِ ما چقدر با مرز فاصله دارد؟

مرزِ پایین می‌گوید «کمتر از این ممکن نیست». **ولی نمی‌گوید کسی به آن می‌رسد.** حالا اندازه می‌گیریم.

> 🤔 **اول حدس بزن:** به‌نظرت `merge sort` چند برابرِ مرزِ پایین مقایسه می‌کند؟ **یک عدد بنویس** — دو برابر؟ ده برابر؟ — بعد جدول را ببین.

</div>

```python
def merge_sort(values):
    """merge sort فصلِ ۴، فشرده، با شمارشِ مقایسه."""
    comparisons = 0

    def go(vals):
        nonlocal comparisons
        if len(vals) <= 1:
            return vals
        mid = len(vals) // 2
        left, right = go(vals[:mid]), go(vals[mid:])
        out = []
        i = j = 0
        while i < len(left) and j < len(right):
            comparisons += 1
            if left[i] <= right[j]:
                out.append(left[i])
                i += 1
            else:
                out.append(right[j])
                j += 1
        out.extend(left[i:])
        out.extend(right[j:])
        return out

    return go(list(values)), comparisons


rng = random.Random(SEED)
LADDER = [1_000, 2_000, 4_000, 8_000]
shuffled = {n: rng.sample(range(10 * n), n) for n in LADDER}
print("merge sort درست کار می‌کند؟",
      merge_sort(shuffled[1_000])[0] == sorted(shuffled[1_000]))
print()
print(f"{'n':>8}{'مرزِ پایین':>14}{'merge sort':>14}{'نسبت':>10}")
for n in LADDER:
    floor_ = math.ceil(log2_factorial(n))
    got = merge_sort(shuffled[n])[1]
    print(f"{n:>8,}{floor_:>14,}{got:>14,}{got / floor_:>10.2f}")
```

```text
merge sort درست کار می‌کند؟ True

       n    مرزِ پایین    merge sort      نسبت
   1,000         8,530         8,709      1.02
   2,000        19,053        19,415      1.02
   4,000        42,100        42,781      1.02
   8,000        92,193        93,704      1.02
```

<div dir="rtl">

**`1.02` در هر چهار سطر.** یعنی `merge sort` — الگوریتمی که خودمان در یک فصل نوشتیم — **دو درصد با بهترین چیزی که نظریه اجازه می‌دهد فاصله دارد**، و این فاصله با بزرگ‌تر شدنِ `n` باز نمی‌شود.

**این جدول دو خبر دارد.** خبرِ خوب اینکه `merge sort` تقریباً بهینه است. **خبرِ مهم‌تر اینکه دنبالِ الگوریتمِ مقایسه‌ایِ بهتر گشتن، اتلافِ وقت است** — حتی یک الگوریتمِ کامل و بی‌نقص هم فقط دو درصد بهتر می‌شود.

**و همین‌جا یک بدهیِ ترمِ ۱ پرداخت می‌شود.** فصلِ ۷ آن ترم `Θ` و `Ω` را در چند خط تعریف کرد و از آن به بعد هیچ‌جا به‌کار نرفتند — چون تا امروز فقط **سقف** داشتیم. **این تنها جای کلِ دوره است که هر دو نصفه را با هم در دست داری:** فصلِ ۴ سقفِ `merge sort` را داد (`O(n log n)`، با جدول) و بخشِ ۲ کفِ **هر** الگوریتمِ مقایسه‌ای را (`Ω(n log n)`، با شمردن). **وقتی سقف و کف یکی باشند، دیگر می‌شود `Θ` نوشت:** مرتب‌سازیِ مقایسه‌ای `Θ(n log n)` است، و ستونِ `1.02` نشان می‌دهد که این فقط یک ادعای نمادین نیست — فاصلهٔ سقف و کف روی داده‌های واقعیِ ما دو درصد است.

**پس اگر می‌خواهی واقعاً سریع‌تر شوی، باید از بازیِ مقایسه بیرون بروی.**

## ۴. الگوریتمی که هیچ دو عضوی را با هم مقایسه نمی‌کند

فرض کن می‌دانی همهٔ عضوها عددِ صحیحِ بینِ `0` و `k-1` هستند. آن‌وقت لازم نیست بپرسی کدام بزرگ‌تر است؛ **فقط باید بشماری هر عدد چند بار آمده.**

</div>

```python
def counting_sort(values, k):
    """بدونِ حتی یک مقایسه بینِ دو عضو. شرط: هر عضو عددِ صحیحِ ۰ تا k-1."""
    counts = [0] * k
    for v in values:
        counts[v] += 1                   # فقط شمردن، نه مقایسه
    out = []
    for value in range(k):
        out.extend([value] * counts[value])
    return out


small = [5, 2, 9, 2, 0, 5, 5]
print("ورودی :", small)
print("خروجی :", counting_sort(small, 10))
print("با sorted یکی است؟", counting_sort(small, 10) == sorted(small))
```

```text
ورودی : [5, 2, 9, 2, 0, 5, 5]
خروجی : [0, 2, 2, 5, 5, 5, 9]
با sorted یکی است؟ True
```

<div dir="rtl">

**در این کد هیچ‌جا دو عضوِ ورودی با هم مقایسه نمی‌شوند.** ترتیب از **آدرس** درمی‌آید، نه از مقایسه — دقیقاً همان ایده‌ای که ترمِ ۲ فصلِ ۱ برای دسترسیِ آرایه ساخت.

**پس مرزِ پایینِ بخشِ ۲ به این الگوریتم اصلاً مربوط نیست.** آن استدلال دربارهٔ الگوریتم‌هایی بود که تنها ابزارشان مقایسه است. **مرز باطل نشد؛ این الگوریتم از قلمروش بیرون است.**

هزینه‌اش را می‌شماریم: `n` بار شمردن، `k` بار پیمودنِ خانه‌ها، و `n` بار نوشتن.

> 🤔 **اول حدس بزن:** با ثابت ماندنِ `k` و دو برابر شدنِ `n`، ستونِ نسبت چه می‌شود؟ و با ثابت ماندنِ `n` و دو برابر شدنِ `k` چه؟ **دو عدد بنویس.**

</div>

```python
def counting_steps(values, k):
    """گام‌های واقعیِ counting sort — شمرده، نه حساب‌شده."""
    counts = [0] * k
    steps = 0
    for v in values:
        counts[v] += 1
        steps += 1
    for value in range(k):
        steps += 1 + counts[value]
    return steps


K_SMALL = 256
COUNT_LADDER = [25_000, 50_000, 100_000, 200_000]
bytes_ = {n: [rng.randrange(K_SMALL) for _ in range(n)] for n in COUNT_LADDER}
print("جواب با sorted یکی است؟",
      counting_sort(bytes_[25_000], K_SMALL) == sorted(bytes_[25_000]))
print("\n— گام‌ها، با k ثابت روی ۲۵۶")
table([(n, counting_steps(bytes_[n], K_SMALL)) for n in COUNT_LADDER], "گام", ",d")
```

```text
جواب با sorted یکی است؟ True

— گام‌ها، با k ثابت روی ۲۵۶
         n               گام     نسبت به سطر قبل
    25,000            50,256                   —
    50,000           100,256                1.99
   100,000           200,256                2.00
   200,000           400,256                2.00
```

```python
FIXED = bytes_[100_000]
print("— گام‌ها، با n ثابت روی ۱۰۰٬۰۰۰ و k دو برابر شونده")
print(f"{'k':>12}{'گام':>14}{'نسبت به سطر قبل':>20}")
previous = None
for k in (200_000, 400_000, 800_000, 1_600_000):
    steps = counting_steps(FIXED, k)
    ratio = "—" if not previous else f"{steps / previous:.2f}"
    print(f"{k:>12,}{steps:>14,}{ratio:>20}")
    previous = steps
```

```text
— گام‌ها، با n ثابت روی ۱۰۰٬۰۰۰ و k دو برابر شونده
           k           گام     نسبت به سطر قبل
     200,000       400,000                   —
     400,000       600,000                1.50
     800,000     1,000,000                1.67
   1,600,000     1,800,000                1.80
```

<div dir="rtl">

**جدولِ اول `2.00` می‌دهد — با `k` ثابت، `counting sort` خطی است.** هیچ `log`ی در کار نیست.

**جدولِ دوم چیزِ مهم‌تری می‌گوید:** با ثابت ماندنِ `n`، بالا بردنِ `k` هم کار را زیاد می‌کند، و نسبتش رفته‌رفته به `2` نزدیک‌تر می‌شود — یعنی هرچه `k` بزرگ‌تر شود، **`k` بخشِ غالبِ هزینه می‌شود** و `n` دیگر تعیین‌کننده نیست. **هزینه `O(n + k)` است و هیچ‌کدام از این دو حرف را نمی‌شود انداخت.**

## ۵. حالا هر دو طرفِ معامله را اندازه بگیر

</div>

```python
big = [rng.randrange(K_SMALL) for _ in range(100_000)]
print("هر سه یک جواب می‌دهند؟",
      counting_sort(big, K_SMALL) == sorted(big) == merge_sort(big)[0])
mine = clock(lambda: merge_sort(big), repeat=2)
counting = clock(lambda: counting_sort(big, K_SMALL), repeat=3)
builtin = clock(lambda: sorted(big), repeat=3)
print(f"\nn = 100,000 · k = 256")
print(f"  merge sortِ ما (پایتونِ خالص): {1000 * mine:>8,.1f} ms")
print(f"  counting sort (پایتونِ خالص) : {1000 * counting:>8,.1f} ms")
print(f"  sorted (نوشته‌شده به C)       : {1000 * builtin:>8,.1f} ms")
print(f"\n  counting در برابرِ merge sortِ ما: {mine / counting:>5,.1f} برابر سریع‌تر")
print(f"  counting در برابرِ sorted        : {builtin / counting:>5,.1f} برابر سریع‌تر")
```

```text-approx
هر سه یک جواب می‌دهند؟ True

n = 100,000 · k = 256
  merge sortِ ما (پایتونِ خالص):    281.0 ms
  counting sort (پایتونِ خالص) :      3.9 ms
  sorted (نوشته‌شده به C)       :      8.9 ms

  counting در برابرِ merge sortِ ما:  71.6 برابر سریع‌تر
  counting در برابرِ sorted        :   2.3 برابر سریع‌تر
```

<div dir="rtl">

**در مقایسهٔ منصفانه — دو الگوریتم، هر دو در پایتونِ خالص — `counting sort` حدودِ هفتاد برابر جلوتر است.** این نتیجهٔ عوض شدنِ مرتبه است: `O(n + k)` در برابرِ `O(n log n)`.

**ولی نسبتِ دومی فقط `2.3` است**، و همین عدد صادقانه‌ترین سطرِ این فصل است: الگوریتمی با مرتبهٔ **بهتر**، در برابرِ `sorted` که مرتبه‌اش بدتر است، فقط دو برابر جلو می‌افتد — **چون `sorted` به زبانِ C نوشته شده و ثابتش ده‌ها برابر کوچک‌تر است.** این همان ثابتِ پنهانِ ترمِ ۱ فصلِ ۹ است و فصلِ ۸ کاملاً بازش می‌کند.

حالا شرط را بشکن: همان `n`، ولی بازهٔ مقادیر خیلی بازتر.

</div>

```python
K_WIDE = 5_000_000
wide = [rng.randrange(K_WIDE) for _ in range(20_000)]
print("جواب با sorted یکی است؟", counting_sort(wide, K_WIDE) == sorted(wide))
slow = clock(lambda: counting_sort(wide, K_WIDE), repeat=2)
ref = clock(lambda: sorted(wide), repeat=3)
print(f"\nn = 20,000 · k = 5,000,000")
print(f"  counting sort: {1000 * slow:>8,.1f} ms")
print(f"  sorted       : {1000 * ref:>8,.1f} ms")
print(f"  نسبت         : {slow / ref:>8,.0f} برابر به‌نفعِ sorted")
print(f"  حافظهٔ آرایهٔ شمارش: {sys.getsizeof([0] * K_WIDE) / 1024 / 1024:,.1f} مگابایت")
```

```text-approx
جواب با sorted یکی است؟ True

n = 20,000 · k = 5,000,000
  counting sort:    516.4 ms
  sorted       :      2.6 ms
  نسبت         :      197 برابر به‌نفعِ sorted
  حافظهٔ آرایهٔ شمارش: 38.1 مگابایت
```

<div dir="rtl">

**همان الگوریتم، همان جوابِ درست، و این بار ۱۹۷ برابر بازنده** — چون برای بیست هزار عدد، پنج میلیون خانه ساخت و همه‌شان را پیمود. **و حافظه‌اش هم از داده‌ای که مرتب می‌کند خیلی بزرگ‌تر شد.**

> ⚠️ **مواظب باش:** بزرگ کردنِ `k` در Colab خطرِ واقعی دارد. اگر `K_WIDE` را چند برابر کنی، ممکن است به‌جای `MemoryError`، **نشست بدونِ هیچ پیامی ری‌استارت شود** و هر چیزی که در حافظه داشتی از دست برود. **قبل از ساختنِ آرایهٔ شمارش، حجمش را با یک ضرب حساب کن** — همان عددی که سطرِ آخرِ خروجیِ بالا چاپ می‌کند.

## ۶. وقتی شرط برقرار نیست

</div>

```python
try:
    counting_sort([3, 1, 2], 2)
except IndexError as err:
    print(f"{type(err).__name__}: {err}")

try:
    counting_sort([1.5, 0.5], 3)
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
IndexError: list index out of range
TypeError: list indices must be integers or slices, not float
```

<div dir="rtl">

> 🔧 **اگر کار نکرد:** دو پیام، دو شکستِ شرط. `IndexError` یعنی عضوی بزرگ‌تر یا مساویِ `k` در داده بوده — **`k` را از خودِ داده حساب کن (`max(values) + 1`)، نه از حدس.** `TypeError` یعنی عضوها عددِ صحیح نیستند؛ `counting sort` روی اعشار **اصلاً معنا ندارد**، چون بینِ هر دو عددِ اعشاری بی‌نهایت عددِ دیگر هست و «خانهٔ شماره‌دار» بی‌معنا می‌شود.
>
> **هر دو خطا خبرِ خوبی‌اند.** بدترین حالت این بود که کد بی‌صدا جوابِ غلط بدهد.

> ✅ **چک کن:** `k` را از داده حساب کن — `counting_sort(values, max(values) + 1)` — و روی `[5, 2, 9, 2, 0, 5, 5]` امتحانش کن. **باید همان `[0, 2, 2, 5, 5, 5, 9]` را بدهد.** حالا عددِ `9` را به `900000` تغییر بده و **قبل از اجرا حساب کن** آرایهٔ شمارش چند خانه می‌شود. اگر جوابت را نوشتی، فهمیده‌ای چرا `k` بخشی از صورتِ مسئله است، نه یک جزئیاتِ پیاده‌سازی.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** مرزِ پایینِ شمارشی با مقایسه‌های واقعیِ `merge sort`؛ و بعد `counting sort` با `merge sort` و با `sorted`، هر سه با جوابِ تأییدشدهٔ برابر. **در کدام بازهٔ `n`؟** ۱٬۰۰۰ تا ۸٬۰۰۰ برای جدولِ مرز، ۲۵٬۰۰۰ تا ۲۰۰٬۰۰۰ برای گام‌های `counting sort`، و دو مقایسهٔ زمانی در `n = 100,000` با `k = 256` و در `n = 20,000` با `k = 5,000,000`. **با چند تکرار، و کمینه یا میانگین؟** جدول‌های شمارش یک اجرا و قطعی؛ مقایسه‌های زمانی دو تا سه تکرار به‌علاوهٔ گرم‌کننده، کمینه، و هر سه روی همان داده.

> 🤖 **از دستیارت بپرس:** «چرا `counting sort` مرزِ پایینِ `n log n` را نقض نمی‌کند؟» بعد این را هم بپرس: **«اگر بخواهم یک میلیون عددِ صحیحِ بینِ صفر و یک میلیارد را مرتب کنم، `counting sort` انتخابِ خوبی است؟»** — جوابِ درست باید حافظهٔ آرایهٔ شمارش را حساب کند و بگوید نه. اگر دستیارت فقط گفت «`counting sort` خطی است پس بهتر است»، **خروجیِ آخرِ بخشِ ۵ را جلویش بگذار.**

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| lower bound | لوئر باوند | کمترین کاری که هیچ الگوریتمی از آن پایین‌تر نمی‌رود |
| comparison sort | کامپریزن سورت | مرتب‌سازی‌ای که تنها ابزارش پرسیدنِ «کدام بزرگ‌تر است؟» است |
| `counting sort` | کانتینگ سورت | مرتب‌سازی با شمردنِ تکرارِ هر مقدار، بدونِ هیچ مقایسه‌ای |
| permutation | پرمیوتیشن | یکی از ترتیب‌های ممکنِ یک مجموعه |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا استدلالِ بخشِ ۲ دربارهٔ **همهٔ** الگوریتم‌های مقایسه‌ای است و نه فقط آن‌هایی که نوشته‌ایم؟

**تمرینِ اجباری:** `counting sort` را طوری بنویس که `k` را خودش از داده حساب کند و برای عددهای **منفی** هم کار کند (راهنمایی: با `min(values)` جابه‌جا کن). حالا جدولِ گامش را برای داده‌ای بگیر که `k` را از داده می‌گیرد. **سؤالِ اصلی: برای چه داده‌ای این نسخه از `sorted` بدتر می‌شود؟** جوابت باید یک نمونهٔ مشخص بسازد و عددش را چاپ کند.

**تمرینِ ستاره‌دار ⭐:** مقایسه‌های `quicksort` فصلِ ۵ را با مرزِ پایین بسنج و ستونِ نسبتش را دربیاور. **قبل از اجرا پیش‌بینی کن** این نسبت از `1.02` بزرگ‌تر است یا کوچک‌تر، و بنویس چرا. بعد اجرا کن و خطای پیش‌بینی‌ات را بنویس. **سؤالِ آخر: می‌شود نسبت کمتر از `1` بشود؟** جوابت باید به معنیِ «مرزِ پایین» برگردد، نه به عددها.

## در فصل بعد

این فصل گفت مرتب کردن گران است — `n log n`، و کمتر از آن ممکن نیست. **پس ارزشش را دارد؟**

فصلِ بعد نشان می‌دهد داشتنِ یک فهرستِ مرتب چه چیزی می‌خرد: پرسشِ «هست یا نه؟» که با جست‌وجوی خطی در `n = 8,000` حدودِ **۴٬۰۰۰ گام** می‌خواست، با **۱۳ گام** جواب می‌گیرد. و بعد نقطهٔ سربه‌سرش را حساب می‌کنیم: **از `q = 24` پرسش به بعد، مرتب کردن به‌صرفه است.**

**و همان‌جا بدترین ردهٔ خطا را هم می‌بینیم:** نسخه‌ای از `binary search` که هیچ خطایی نمی‌دهد و برای ۴۸۹ عضو از ۱٬۰۰۰ عضوِ موجود می‌گوید «پیدا نشد».

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t4/s06-sorting-lower-bound (یادستان, Yaadestan)
