# فصل ۰۸ — `sorted` واقعی: `key`، پایداری، و چرا از هر چیزی که بنویسی سریع‌تر است

<div dir="rtl">

# فصل ۰۸ — `sorted` واقعی: `key`، پایداری، و چرا از هر چیزی که بنویسی سریع‌تر است

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

سه الگوریتمِ مرتب‌سازی نوشتیم و در کارِ واقعی هیچ‌کدامشان را نمی‌نویسی. **این فصل می‌گوید چرا — و جوابش آن چیزی نیست که فکر می‌کنی.**

مقایسه‌های خودِ `sorted` را می‌شماریم: در `n = 80,000` عددِ **`1,201,201`** درمی‌آید و `merge sort` ما **`1,203,739`**. **تقریباً یکی.** یعنی الگوریتمش بهتر نیست؛ با این حال روی همان داده حدودِ **سیزده برابر** سریع‌تر است.

**و یک کارِ دیگر هم می‌کند که ما بلد نبودیم:** روی ورودیِ از پیش مرتب همان `1,201,201` مقایسه به **`79,999`** می‌افتد و ستونِ نسبت `2.00` می‌شود. روی ورودیِ کاملاً وارونه هم همان‌طور.

![دستگاهی که یک نوارِ درهم را مرتب می‌کند و بخش‌های از قبل مرتبِ نوار را دست‌نخورده رد می‌کند](/lesson-assets/t4-s08-sorting-in-practice/prompt/01-image-run-detection.png)

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

- با `key=` بر اساسِ هر چیزی که بخواهی مرتب کنی
- بگویی پایداری چیست و مرتب‌سازیِ چندکلیدی را با آن بنویسی
- مقایسه‌های خودِ `sorted` را بشماری و رفتارش را روی ورودی‌های مختلف نشان بدهی
- بگویی چرا در اندازه‌های کوچک، الگوریتمِ «بدتر» انتخابِ درست است

## قبل از شروع

**از فصلِ ۳:** `insertion sort` و اینکه روی ورودیِ از پیش مرتب خطی می‌شود.

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

**از ترمِ ۱ فصلِ ۹:** الگوریتمِ بدتری که زیرِ یک اندازه برنده است، و نقطهٔ تقاطع. **بخشِ ۶ همان آزمایش را روی مرتب‌سازی تکرار می‌کند.**

</div>

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

<div dir="rtl">

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

## ۱. `key=`: بر اساسِ چه چیزی مرتب شود

`sorted` به‌طورِ پیش‌فرض خودِ عضوها را مقایسه می‌کند. با `key=` می‌گویی **از هر عضو چه چیزی را برای مقایسه بردارد.**

</div>

```python
people = [("سارا", 1997, "شیراز"), ("رضا", 2001, "تبریز"), ("نیما", 1997, "رشت"),
          ("مینا", 2004, "یزد"), ("کیان", 2001, "اهواز"), ("دارا", 1997, "کرمان")]

print("بر اساسِ سالِ تولد:")
for row in sorted(people, key=lambda p: p[1]):
    print("  ", row)

print("\nبر اساسِ طولِ نام، بعد سالِ تولد:")
for row in sorted(people, key=lambda p: (len(p[0]), p[1])):
    print("  ", row)
```

```text
بر اساسِ سالِ تولد:
   ('سارا', 1997, 'شیراز')
   ('نیما', 1997, 'رشت')
   ('دارا', 1997, 'کرمان')
   ('رضا', 2001, 'تبریز')
   ('کیان', 2001, 'اهواز')
   ('مینا', 2004, 'یزد')

بر اساسِ طولِ نام، بعد سالِ تولد:
   ('رضا', 2001, 'تبریز')
   ('سارا', 1997, 'شیراز')
   ('نیما', 1997, 'رشت')
   ('دارا', 1997, 'کرمان')
   ('کیان', 2001, 'اهواز')
   ('مینا', 2004, 'یزد')
```

<div dir="rtl">

**`key` برای هر عضو دقیقاً یک بار صدا زده می‌شود، نه برای هر مقایسه.** پس حتی اگر تابعِ `key` گران باشد، هزینه‌اش `O(n)` است و به `n log n` مقایسه اضافه نمی‌شود.

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

## ۲. پایداری: چیزی که تعریفش کسل‌کننده است و کاربردش نه

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

</div>

```python
by_year = sorted(people, key=lambda p: p[1])
print("ترتیبِ ورودیِ متولدانِ ۱۹۹۷:", [p[0] for p in people if p[1] == 1997])
print("ترتیبِ خروجیِ متولدانِ ۱۹۹۷:", [p[0] for p in by_year if p[1] == 1997])

two_passes = sorted(sorted(people, key=lambda p: p[2]), key=lambda p: p[1])
one_key = sorted(people, key=lambda p: (p[1], p[2]))
print("\nدو پاس و کلیدِ مرکب یک جواب می‌دهند؟", two_passes == one_key)
for row in one_key:
    print("  ", row)
```

```text
ترتیبِ ورودیِ متولدانِ ۱۹۹۷: ['سارا', 'نیما', 'دارا']
ترتیبِ خروجیِ متولدانِ ۱۹۹۷: ['سارا', 'نیما', 'دارا']

دو پاس و کلیدِ مرکب یک جواب می‌دهند؟ True
   ('نیما', 1997, 'رشت')
   ('سارا', 1997, 'شیراز')
   ('دارا', 1997, 'کرمان')
   ('کیان', 2001, 'اهواز')
   ('رضا', 2001, 'تبریز')
   ('مینا', 2004, 'یزد')
```

<div dir="rtl">

**سطرِ دوم همان سطرِ اول است — ترتیبِ سه‌تای برابر دست نخورد.** و همین خاصیت است که کارِ سومی را ممکن می‌کند: **مرتب کردن بر اساسِ کلیدِ کم‌اهمیت‌تر، بعد بر اساسِ کلیدِ مهم‌تر.** اگر مرتب‌سازی پایدار نبود، پاسِ دوم دستاوردِ پاسِ اول را به هم می‌ریخت و این روش کار نمی‌کرد.

**در فصلِ ۴ یک ✅ چک کن بود که گفت `<=` را به `<` تغییر بده و «هیچ چیزی عوض نمی‌شود». این‌جا بدهی‌اش پرداخت می‌شود:** آن یک نویسه دقیقاً همان چیزی است که `merge sort` را پایدار نگه می‌دارد. با `<`، وقتی دو عضو برابر باشند، عضوِ سمتِ راست اول برداشته می‌شود و ترتیبِ اولیه به هم می‌خورد. **روی داده‌ای که عضوِ برابر ندارد هیچ اثری ندارد و برای همین موقعِ آزمون دیده نمی‌شود.**

</div>

```python
try:
    sorted(people, lambda p: p[1])
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
TypeError: sorted expected 1 argument, got 2
```

<div dir="rtl">

> 🔧 **اگر کار نکرد:** `key` **باید** با نام داده شود. پیام کمی گمراه‌کننده است — می‌گوید «یک آرگومان انتظار داشتم، دو تا گرفتم» — و دلیلش این است که `sorted` فقط یک آرگومانِ بی‌نام قبول می‌کند و بقیه اجباراً نام‌دارند. **`sorted(people, key=...)` درست است و `sorted(people, ...)` غلط.** همین قاعده برای `list.sort` و `min` و `max` هم برقرار است.

## ۳. مقایسه‌های خودِ `sorted` را بشمار

می‌خواهیم بدانیم `sorted` واقعاً چند مقایسه می‌کند. **راهش این است که عددی بسازیم که مقایسه‌شدنش را می‌شمارد** — آن‌وقت `sorted` بی‌آنکه بداند، خودش شمارنده را بالا می‌برد.

**و این تنها جای کلِ دوره است که یک `class` می‌نویسیم، فقط برای همین یک کار.** پایتون برای مقایسهٔ دو چیز با `<` سراغِ `__lt__`ِ آن‌ها می‌رود — همان قاعده‌ای که ترمِ ۳ فصلِ ۶ برای `__hash__` و `__eq__` گفت. پس اگر `__lt__` را خودمان بنویسیم، هر مقایسه‌ای که `sorted` انجام می‌دهد از دستِ ما رد می‌شود و می‌شود شمردش. `class` این‌جا فقط یک ظرف است، `__init__` مقدارِ اولیه را می‌گیرد، و `self` یعنی «همان چیزی که دارد مقایسه می‌شود». **فعلاً همین‌قدر بدان؛ این دوره جای دیگری `class` نمی‌سازد.**

**و یک کلمهٔ دیگر هم در همان کد هست: `global`.** خواهرِ `nonlocal`ِ فصلِ ۱ است و کارش همان است، یک پله بالاتر: `nonlocal` می‌گوید «متغیرِ تابعِ بیرونی را می‌خواهم عوض کنم» و **`global COMPARISONS` می‌گوید «متغیرِ بالاترین سطحِ نوت‌بوک را می‌خواهم عوض کنم».** بدونِ آن، `COMPARISONS += 1` یک متغیرِ محلیِ تازه می‌سازد و شمارنده هیچ‌وقت بالا نمی‌رود. **این‌جا لازمش داریم چون `__lt__` تابعی است که `sorted` صدایش می‌زند، نه ما — پس هیچ راهی برای پس دادنِ شمارش از طریقِ خروجی‌اش نداریم.**

</div>

```python
COMPARISONS = 0


class Counted:
    """عددی که هر بار مقایسه‌شدنش را می‌شمارد — هیچ کارِ دیگری نمی‌کند."""

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        global COMPARISONS
        COMPARISONS += 1
        return self.value < other.value


def sort_comparisons(values):
    """تعدادِ مقایسه‌ای که خودِ sorted روی این ورودی انجام می‌دهد."""
    global COMPARISONS
    boxed = [Counted(v) for v in values]   # ساختنشان هیچ مقایسه‌ای ندارد
    COMPARISONS = 0
    sorted(boxed)
    return COMPARISONS


print("مقایسه‌های sorted روی ۸ عددِ درهم:", sort_comparisons([29, 10, 14, 37, 13, 25, 11, 18]))
print("مقایسه‌های sorted روی ۸ عددِ مرتب:", sort_comparisons(sorted([29, 10, 14, 37, 13, 25, 11, 18])))
```

```text
مقایسه‌های sorted روی ۸ عددِ درهم: 20
مقایسه‌های sorted روی ۸ عددِ مرتب: 7
```

<div dir="rtl">

**بیست در برابرِ هفت، روی همان هشت عدد.** `sorted` فهمید که ورودیِ دوم از قبل مرتب است — با هفت مقایسه، یعنی `n - 1`، یعنی فقط یک بار پشتِ سرِ هم چک کردنِ همسایه‌ها.

> 🤔 **اول حدس بزن:** برای هر سه حالتِ زیر ستونِ نسبت را بنویس: ورودیِ تصادفی، ورودیِ از پیش مرتب، و ورودیِ **کاملاً وارونه**. **سه عدد**، بعد جدول را ببین. (وارونه سخت‌ترینشان است.)

</div>

```python
rng = random.Random(SEED)
LADDER = [10_000, 20_000, 40_000, 80_000]
shuffled = {n: rng.sample(range(10 * n), n) for n in LADDER}
climbing = {n: sorted(shuffled[n]) for n in LADDER}
falling = {n: sorted(shuffled[n], reverse=True) for n in LADDER}

print("— ورودیِ تصادفی")
table([(n, sort_comparisons(shuffled[n])) for n in LADDER], "مقایسه", ",d")
print("\n— ورودیِ از پیش مرتب")
table([(n, sort_comparisons(climbing[n])) for n in LADDER], "مقایسه", ",d")
print("\n— ورودیِ کاملاً وارونه")
table([(n, sort_comparisons(falling[n])) for n in LADDER], "مقایسه", ",d")
```

```text
— ورودیِ تصادفی
         n            مقایسه     نسبت به سطر قبل
    10,000           120,122                   —
    20,000           260,362                2.17
    40,000           560,631                2.15
    80,000         1,201,201                2.14

— ورودیِ از پیش مرتب
         n            مقایسه     نسبت به سطر قبل
    10,000             9,999                   —
    20,000            19,999                2.00
    40,000            39,999                2.00
    80,000            79,999                2.00

— ورودیِ کاملاً وارونه
         n            مقایسه     نسبت به سطر قبل
    10,000             9,999                   —
    20,000            19,999                2.00
    40,000            39,999                2.00
    80,000            79,999                2.00
```

<div dir="rtl">

**جدولِ اول `2.15` است — همان `O(n log n)` فصلِ ۴.** ولی دو جدولِ دیگر **`2.00`** می‌دهند و عددشان دقیقاً `n - 1` است: **`O(n)`.**

**و جدولِ سوم غافلگیرکننده‌تر از دومی است.** ورودیِ وارونه بدترین ورودیِ ممکن به‌نظر می‌رسد و در `insertion sort` فصلِ ۳ دقیقاً همان بود. ولی `sorted` **دنبالهٔ نزولی را هم به‌عنوان یک بخشِ مرتب می‌شناسد** — با `n - 1` مقایسه پیدایش می‌کند و بعد فقط وارونه‌اش می‌کند.

## ۴. و دادهٔ واقعی: نیمی مرتب

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

> 🤔 **اول حدس بزن:** نیمهٔ اول مرتب و نیمهٔ دوم درهم. **بنویس تعدادِ مقایسه در `n = 80,000` به کدام‌یک از دو عددِ بخشِ ۳ نزدیک‌تر می‌شود** — `1,201,201` یا `79,999` — و آیا انتظار داری دقیقاً وسطشان بیفتد.

</div>

```python
def half_sorted(n):
    """نیمهٔ اول مرتب، نیمهٔ دوم درهم — چیزی که در دادهٔ واقعی زیاد پیش می‌آید."""
    base = shuffled[n]
    return sorted(base[:n // 2]) + base[n // 2:]


print("— نیمی مرتب، نیمی درهم")
table([(n, sort_comparisons(half_sorted(n))) for n in LADDER], "مقایسه", ",d")
print()
n = 80_000
print(f"در n = {n:,}:")
print(f"  تصادفی    : {sort_comparisons(shuffled[n]):>9,} مقایسه")
print(f"  نیمی مرتب : {sort_comparisons(half_sorted(n)):>9,} مقایسه")
print(f"  کاملاً مرتب: {sort_comparisons(climbing[n]):>9,} مقایسه")
```

```text
— نیمی مرتب، نیمی درهم
         n            مقایسه     نسبت به سطر قبل
    10,000            70,039                   —
    20,000           150,234                2.15
    40,000           320,340                2.13
    80,000           680,675                2.12

در n = 80,000:
  تصادفی    : 1,201,201 مقایسه
  نیمی مرتب :   680,675 مقایسه
  کاملاً مرتب:    79,999 مقایسه
```

<div dir="rtl">

**نیمی از داده که از قبل مرتب باشد، بیش از پانصد هزار مقایسه را حذف می‌کند** — `680,675` در برابرِ `1,201,201`. **این هدیه‌ای است که `merge sort` ما اصلاً نمی‌گیرد**، چون کورکورانه همه‌چیز را از وسط می‌شکند، حتی تکه‌ای که از قبل مرتب است.

> ✅ **چک کن:** فهرستی بساز که **سه‌چهارمش** مرتب باشد و بقیه درهم. **تعدادِ مقایسه‌ها باید بینِ عددِ «نیمی مرتب» و عددِ «کاملاً مرتب» بیفتد.** اگر به عددِ «تصادفی» نزدیک شد، احتمالاً تکهٔ مرتب را در انتها گذاشته‌ای ولی مقادیرش با تکهٔ اول هم‌پوشانی دارد — و آن‌وقت هیچ بخشِ مرتبِ **پیوسته‌ای** در کل نیست.

## ۵. پس چرا سریع‌تر است؟

حالا سؤالِ اصلیِ فصل. مقایسه‌های `sorted` و `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


data = shuffled[80_000]
mine, mine_cmp = merge_sort(data)
print("جوابِ دو نسخه یکی است؟", mine == sorted(data))
print(f"مقایسهٔ merge sortِ ما : {mine_cmp:>9,}")
print(f"مقایسهٔ sorted        : {sort_comparisons(data):>9,}")
```

```text
جوابِ دو نسخه یکی است؟ True
مقایسهٔ merge sortِ ما : 1,203,739
مقایسهٔ sorted        : 1,201,201
```

<div dir="rtl">

**اختلافشان حدودِ دو در هزار است.** روی ورودیِ تصادفی، `sorted` هیچ کارِ زیرکانه‌تری نمی‌کند؛ **دقیقاً همان تعداد مقایسه را انجام می‌دهد.**

</div>

```python
ours = clock(lambda: merge_sort(data), repeat=2)
theirs = clock(lambda: sorted(data), repeat=3)
print(f"n = 80,000")
print(f"  merge sortِ ما: {1000 * ours:>8,.1f} ms")
print(f"  sorted        : {1000 * theirs:>8,.1f} ms")
print(f"  نسبت          : {ours / theirs:>8,.0f} برابر")
```

```text-approx
n = 80,000
  merge sortِ ما:    212.9 ms
  sorted        :     16.2 ms
  نسبت          :       13 برابر
```

<div dir="rtl">

**همان تعداد مقایسه، سیزده برابر زمان.** پس تفاوت در **الگوریتم** نیست، در **ثابت** است: هر مقایسهٔ ما یک دورِ حلقهٔ پایتون است و هر مقایسهٔ `sorted` چند دستورِ ماشین در کدِ C.

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

**پس این چهار فصل بی‌فایده بود؟** برعکس: **بدونِ آن‌ها نمی‌توانستی این جدول را بخوانی.** جدولِ بالا فقط برای کسی معنا دارد که بداند «همان تعداد مقایسه» یعنی چه و چرا اهمیت دارد.

## ۶. و کجا `sorted` هم الگوریتم را عوض می‌کند

`sorted` خودش هم یک درسِ ترمِ ۱ را رعایت می‌کند: **در اندازه‌های کوچک، الگوریتمِ «بدتر» برنده است.** بیایید نقطهٔ تقاطعِ خودمان را پیدا کنیم.

> 🤔 **اول حدس بزن:** `insertion sort` که `O(n²)` است در برابرِ `merge sort` که `O(n log n)` است، در `n`های ۸ تا ۲۵۶. **یک عدد بنویس: نقطهٔ تقاطع کجاست؟** و اگر فکر می‌کنی تقاطعی در کار نیست، همان را بنویس — ترمِ ۱ فصلِ ۹ می‌گوید چرا حتماً هست.

</div>

```python
def insertion_sort(values):
    a = list(values)
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a


SMALL = [8, 16, 32, 64, 128, 256]
tiny = {n: rng.sample(range(10 * n), n) for n in SMALL}
print("هر دو یک جواب می‌دهند؟",
      all(insertion_sort(tiny[n]) == merge_sort(tiny[n])[0] for n in SMALL))
print()
print(f"{'n':>6}{'insertion (µs)':>18}{'merge (µs)':>14}{'برنده':>14}")
for n in SMALL:
    a = 1e6 * clock(lambda v=tiny[n]: insertion_sort(v), repeat=200)
    b = 1e6 * clock(lambda v=tiny[n]: merge_sort(v), repeat=200)
    print(f"{n:>6}{a:>18,.1f}{b:>14,.1f}{('insertion' if a < b else 'merge'):>14}")
```

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

     n    insertion (µs)    merge (µs)         برنده
     8               1.5           5.7     insertion
    16               4.7          12.8     insertion
    32              17.9          29.5     insertion
    64              57.8          69.0     insertion
   128             242.1         161.2         merge
   256             762.1         315.1         merge
```

<div dir="rtl">

**روی این ماشین، نقطهٔ تقاطع بینِ `64` و `128` افتاد.** زیرِ آن، الگوریتمِ `O(n²)` — که فصلِ ۳ «کند» صدایش زدیم — از الگوریتمِ `O(n log n)` سریع‌تر است، چون سربارِ شکستن و ساختنِ `list` تازه در تکه‌های کوچک بر همه‌چیز غالب است. **عددِ تو ممکن است جابه‌جا شود؛ آنچه جابه‌جا نمی‌شود وجودِ تقاطع است.**

**و همین قاعده در خودِ `sorted` هم پیاده شده:** روی تکه‌های کوچک سراغِ شکستنِ بیشتر نمی‌رود و از `insertion sort` استفاده می‌کند. **این تصمیم دقیقاً همان چیزی است که ترمِ ۱ فصلِ ۹ با نقطهٔ تقاطعش نشان داد** — و حالا در کدی می‌بینی‌اش که هر روز صدایش می‌زنی.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** `sorted` با `merge sort` خودمان، هم در تعدادِ مقایسه و هم در زمان، روی همان داده و با جوابِ تأییدشدهٔ برابر؛ و `sorted` با خودش روی چهار جنسِ ورودی. **در کدام بازهٔ `n`؟** ۱۰٬۰۰۰ تا ۸۰٬۰۰۰ برای جدول‌های شمارش، و ۸ تا ۲۵۶ برای نقطهٔ تقاطع. **با چند تکرار، و کمینه یا میانگین؟** جدول‌های مقایسه یک اجرا و قطعی؛ جدولِ زمانِ بزرگ دو تا سه تکرار و جدولِ اندازه‌های کوچک ۲۰۰ تکرار — **چون در مقیاسِ میکروثانیه، حدِ تفکیکِ ساعت خودش بزرگ‌ترین منبعِ خطاست** (ترمِ ۱ فصلِ ۲).

> 🤖 **از دستیارت بپرس:** «چرا `sorted` روی ورودیِ کاملاً وارونه هم فقط `n - 1` مقایسه می‌کند؟» بعد این را هم بپرس: **«اگر `sorted` و کدِ من تعدادِ مقایسهٔ یکسانی داشته باشیم، تفاوتِ سرعتمان از کجا می‌آید؟»** — جوابِ درست باید به زبانِ پیاده‌سازی برسد، نه به مرتبه. اگر دستیارت گفت «چون الگوریتمش بهتر است»، **خروجیِ بخشِ ۵ را جلویش بگذار.**

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| stable sort | استیبل سورت | مرتب‌سازی‌ای که ترتیبِ عضوهای هم‌کلید را نگه می‌دارد |
| `key` | کی | تابعی که می‌گوید از هر عضو چه چیزی مقایسه شود |
| run | رَن | بخشی از داده که از قبل مرتب است |
| multi-key sort | مولتی‌کی سورت | مرتب‌سازی بر اساسِ چند کلید، به ترتیبِ اولویت |
| `global` | گلوبال | اعلامِ اینکه یک تابع می‌خواهد متغیرِ بالاترین سطح را عوض کند، نه فقط بخواند |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: اگر `sorted` پایدار نبود، کدام کارِ بخشِ ۲ ممکن نمی‌شد؟

**تمرینِ اجباری:** فهرستی از رکوردها بساز و آن را بر اساسِ یک کلید **صعودی** و کلیدِ دیگری **نزولی** مرتب کن. (راهنمایی: برای عددها می‌شود از علامتِ منفی استفاده کرد؛ برای رشته نمی‌شود — پس دو پاس لازم است.) **سؤالِ اصلی: چرا برای رشته نمی‌شود همان ترفند را زد، و راهِ درستش چیست؟** جوابت باید به پایداری برگردد.

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

## در فصل بعد

ترمِ چهار تمام شد: `recursion`، سه الگوریتمِ مرتب‌سازی، یک مرزِ پایین، و `binary search`.

**فصلِ آخر همه‌شان را روی یک مسئلهٔ واقعی می‌گذارد.** یک انبارِ رکورد داریم و باید در آن دنبالِ کد بگردیم. سه راه می‌سازیم — جست‌وجوی خطی، مرتب کردن و `bisect`، و یک `dict` — و برای هر سه جدول می‌گیریم. در `n = 16,000` میانگینِ گامِ روشِ اول **`7,807.5`** است و روشِ دوم **`13.06`**.

**ولی نتیجهٔ اصلی جای دیگری است:** یک پرسشِ ساده پیدا می‌کنیم که سریع‌ترین ساختار **اصلاً نمی‌تواند** جوابش را بدهد و باید ۱۶٬۰۰۰ گام بردارد، در حالی که ساختارِ «کندتر» با ۳۲۲ گام جواب می‌دهد.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t4/s08-sorting-in-practice (یادستان, Yaadestan)
