در این فصل چه یاد میگیری#
سه الگوریتمِ مرتبسازی نوشتیم و در کارِ واقعی هیچکدامشان را نمینویسی. این فصل میگوید چرا — و جوابش آن چیزی نیست که فکر میکنی.
مقایسههای خودِ sorted را میشماریم: در n = 80,000 عددِ 1,201,201 درمیآید و merge sort ما 1,203,739. تقریباً یکی. یعنی الگوریتمش بهتر نیست؛ با این حال روی همان داده حدودِ سیزده برابر سریعتر است.
و یک کارِ دیگر هم میکند که ما بلد نبودیم: روی ورودیِ از پیش مرتب همان 1,201,201 مقایسه به 79,999 میافتد و ستونِ نسبت 2.00 میشود. روی ورودیِ کاملاً وارونه هم همانطور.

آخر این فصل میتوانی:
- با
key=بر اساسِ هر چیزی که بخواهی مرتب کنی - بگویی پایداری چیست و مرتبسازیِ چندکلیدی را با آن بنویسی
- مقایسههای خودِ
sortedرا بشماری و رفتارش را روی ورودیهای مختلف نشان بدهی - بگویی چرا در اندازههای کوچک، الگوریتمِ «بدتر» انتخابِ درست است
قبل از شروع#
از فصلِ ۳: insertion sort و اینکه روی ورودیِ از پیش مرتب خطی میشود.
از فصلِ ۴: merge sort و شمارشِ مقایسههایش — کدش اینجا فشرده تکرار میشود.
از ترمِ ۱ فصلِ ۹: الگوریتمِ بدتری که زیرِ یک اندازه برنده است، و نقطهٔ تقاطع. بخشِ ۶ همان آزمایش را روی مرتبسازی تکرار میکند.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. key=: بر اساسِ چه چیزی مرتب شود#
sorted بهطورِ پیشفرض خودِ عضوها را مقایسه میکند. با key= میگویی از هر عضو چه چیزی را برای مقایسه بردارد.
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)
بر اساسِ سالِ تولد:
('سارا', 1997, 'شیراز')
('نیما', 1997, 'رشت')
('دارا', 1997, 'کرمان')
('رضا', 2001, 'تبریز')
('کیان', 2001, 'اهواز')
('مینا', 2004, 'یزد')
بر اساسِ طولِ نام، بعد سالِ تولد:
('رضا', 2001, 'تبریز')
('سارا', 1997, 'شیراز')
('نیما', 1997, 'رشت')
('دارا', 1997, 'کرمان')
('کیان', 2001, 'اهواز')
('مینا', 2004, 'یزد')
key برای هر عضو دقیقاً یک بار صدا زده میشود، نه برای هر مقایسه. پس حتی اگر تابعِ key گران باشد، هزینهاش O(n) است و به n log n مقایسه اضافه نمیشود.
و وقتی key یک tuple برمیگرداند، مقایسه از چپ به راست انجام میشود: اول عضوِ اول، و فقط اگر برابر بودند، عضوِ دوم. این کلِ مرتبسازیِ چندکلیدی است.
۲. پایداری: چیزی که تعریفش کسلکننده است و کاربردش نه#
sorted پایدار است، یعنی عضوهایی که کلیدشان برابر است، ترتیبِ اولیهشان را نگه میدارند.
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)
ترتیبِ ورودیِ متولدانِ ۱۹۹۷: ['سارا', 'نیما', 'دارا']
ترتیبِ خروجیِ متولدانِ ۱۹۹۷: ['سارا', 'نیما', 'دارا']
دو پاس و کلیدِ مرکب یک جواب میدهند؟ True
('نیما', 1997, 'رشت')
('سارا', 1997, 'شیراز')
('دارا', 1997, 'کرمان')
('کیان', 2001, 'اهواز')
('رضا', 2001, 'تبریز')
('مینا', 2004, 'یزد')
سطرِ دوم همان سطرِ اول است — ترتیبِ سهتای برابر دست نخورد. و همین خاصیت است که کارِ سومی را ممکن میکند: مرتب کردن بر اساسِ کلیدِ کماهمیتتر، بعد بر اساسِ کلیدِ مهمتر. اگر مرتبسازی پایدار نبود، پاسِ دوم دستاوردِ پاسِ اول را به هم میریخت و این روش کار نمیکرد.
در فصلِ ۴ یک ✅ چک کن بود که گفت <= را به < تغییر بده و «هیچ چیزی عوض نمیشود». اینجا بدهیاش پرداخت میشود: آن یک نویسه دقیقاً همان چیزی است که merge sort را پایدار نگه میدارد. با <، وقتی دو عضو برابر باشند، عضوِ سمتِ راست اول برداشته میشود و ترتیبِ اولیه به هم میخورد. روی دادهای که عضوِ برابر ندارد هیچ اثری ندارد و برای همین موقعِ آزمون دیده نمیشود.
try:
sorted(people, lambda p: p[1])
except TypeError as err:
print(f"{type(err).__name__}: {err}")
TypeError: sorted expected 1 argument, got 2
🔧 اگر کار نکرد:
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 صدایش میزند، نه ما — پس هیچ راهی برای پس دادنِ شمارش از طریقِ خروجیاش نداریم.
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])))
مقایسههای sorted روی ۸ عددِ درهم: 20
مقایسههای sorted روی ۸ عددِ مرتب: 7
بیست در برابرِ هفت، روی همان هشت عدد. sorted فهمید که ورودیِ دوم از قبل مرتب است — با هفت مقایسه، یعنی n - 1، یعنی فقط یک بار پشتِ سرِ هم چک کردنِ همسایهها.
🤔 اول حدس بزن: برای هر سه حالتِ زیر ستونِ نسبت را بنویس: ورودیِ تصادفی، ورودیِ از پیش مرتب، و ورودیِ کاملاً وارونه. سه عدد، بعد جدول را ببین. (وارونه سختترینشان است.)
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")
— ورودیِ تصادفی
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
جدولِ اول 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— و آیا انتظار داری دقیقاً وسطشان بیفتد.
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,} مقایسه")
— نیمی مرتب، نیمی درهم
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 مقایسه
نیمی از داده که از قبل مرتب باشد، بیش از پانصد هزار مقایسه را حذف میکند — 680,675 در برابرِ 1,201,201. این هدیهای است که merge sort ما اصلاً نمیگیرد، چون کورکورانه همهچیز را از وسط میشکند، حتی تکهای که از قبل مرتب است.
✅ چک کن: فهرستی بساز که سهچهارمش مرتب باشد و بقیه درهم. تعدادِ مقایسهها باید بینِ عددِ «نیمی مرتب» و عددِ «کاملاً مرتب» بیفتد. اگر به عددِ «تصادفی» نزدیک شد، احتمالاً تکهٔ مرتب را در انتها گذاشتهای ولی مقادیرش با تکهٔ اول همپوشانی دارد — و آنوقت هیچ بخشِ مرتبِ پیوستهای در کل نیست.
۵. پس چرا سریعتر است؟#
حالا سؤالِ اصلیِ فصل. مقایسههای sorted و merge sort ما را روی همان داده کنارِ هم میگذاریم.
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,}")
جوابِ دو نسخه یکی است؟ True
مقایسهٔ merge sortِ ما : 1,203,739
مقایسهٔ sorted : 1,201,201
اختلافشان حدودِ دو در هزار است. روی ورودیِ تصادفی، sorted هیچ کارِ زیرکانهتری نمیکند؛ دقیقاً همان تعداد مقایسه را انجام میدهد.
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} برابر")
n = 80,000
merge sortِ ما: 212.9 ms
sorted : 16.2 ms
نسبت : 13 برابر
همان تعداد مقایسه، سیزده برابر زمان. پس تفاوت در الگوریتم نیست، در ثابت است: هر مقایسهٔ ما یک دورِ حلقهٔ پایتون است و هر مقایسهٔ sorted چند دستورِ ماشین در کدِ C.
این دقیقاً همان ثابتِ پنهانی است که ترمِ ۱ فصلِ ۹ ساخت و Big-O عمداً نمیبیندش. و نتیجهٔ عملیاش یک قاعده است: مرتبسازی را ننویس، sorted را صدا بزن — نه چون الگوریتمت بد است، چون حلقهات در پایتون میچرخد.
پس این چهار فصل بیفایده بود؟ برعکس: بدونِ آنها نمیتوانستی این جدول را بخوانی. جدولِ بالا فقط برای کسی معنا دارد که بداند «همان تعداد مقایسه» یعنی چه و چرا اهمیت دارد.
۶. و کجا sorted هم الگوریتم را عوض میکند#
sorted خودش هم یک درسِ ترمِ ۱ را رعایت میکند: در اندازههای کوچک، الگوریتمِ «بدتر» برنده است. بیایید نقطهٔ تقاطعِ خودمان را پیدا کنیم.
🤔 اول حدس بزن:
insertion sortکهO(n²)است در برابرِmerge sortکهO(n log n)است، درnهای ۸ تا ۲۵۶. یک عدد بنویس: نقطهٔ تقاطع کجاست؟ و اگر فکر میکنی تقاطعی در کار نیست، همان را بنویس — ترمِ ۱ فصلِ ۹ میگوید چرا حتماً هست.
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}")
هر دو یک جواب میدهند؟ 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
روی این ماشین، نقطهٔ تقاطع بینِ 64 و 128 افتاد. زیرِ آن، الگوریتمِ O(n²) — که فصلِ ۳ «کند» صدایش زدیم — از الگوریتمِ O(n log n) سریعتر است، چون سربارِ شکستن و ساختنِ list تازه در تکههای کوچک بر همهچیز غالب است. عددِ تو ممکن است جابهجا شود؛ آنچه جابهجا نمیشود وجودِ تقاطع است.
و همین قاعده در خودِ sorted هم پیاده شده: روی تکههای کوچک سراغِ شکستنِ بیشتر نمیرود و از insertion sort استفاده میکند. این تصمیم دقیقاً همان چیزی است که ترمِ ۱ فصلِ ۹ با نقطهٔ تقاطعش نشان داد — و حالا در کدی میبینیاش که هر روز صدایش میزنی.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟
sortedباmerge sortخودمان، هم در تعدادِ مقایسه و هم در زمان، روی همان داده و با جوابِ تأییدشدهٔ برابر؛ وsortedبا خودش روی چهار جنسِ ورودی. در کدام بازهٔn؟ ۱۰٬۰۰۰ تا ۸۰٬۰۰۰ برای جدولهای شمارش، و ۸ تا ۲۵۶ برای نقطهٔ تقاطع. با چند تکرار، و کمینه یا میانگین؟ جدولهای مقایسه یک اجرا و قطعی؛ جدولِ زمانِ بزرگ دو تا سه تکرار و جدولِ اندازههای کوچک ۲۰۰ تکرار — چون در مقیاسِ میکروثانیه، حدِ تفکیکِ ساعت خودش بزرگترین منبعِ خطاست (ترمِ ۱ فصلِ ۲).
🤖 از دستیارت بپرس: «چرا
sortedروی ورودیِ کاملاً وارونه هم فقطn - 1مقایسه میکند؟» بعد این را هم بپرس: «اگرsortedو کدِ من تعدادِ مقایسهٔ یکسانی داشته باشیم، تفاوتِ سرعتمان از کجا میآید؟» — جوابِ درست باید به زبانِ پیادهسازی برسد، نه به مرتبه. اگر دستیارت گفت «چون الگوریتمش بهتر است»، خروجیِ بخشِ ۵ را جلویش بگذار.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| stable sort | استیبل سورت | مرتبسازیای که ترتیبِ عضوهای همکلید را نگه میدارد |
key |
کی | تابعی که میگوید از هر عضو چه چیزی مقایسه شود |
| run | رَن | بخشی از داده که از قبل مرتب است |
| multi-key sort | مولتیکی سورت | مرتبسازی بر اساسِ چند کلید، به ترتیبِ اولویت |
global |
گلوبال | اعلامِ اینکه یک تابع میخواهد متغیرِ بالاترین سطح را عوض کند، نه فقط بخواند |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
ترمِ چهار تمام شد: recursion، سه الگوریتمِ مرتبسازی، یک مرزِ پایین، و binary search.
فصلِ آخر همهشان را روی یک مسئلهٔ واقعی میگذارد. یک انبارِ رکورد داریم و باید در آن دنبالِ کد بگردیم. سه راه میسازیم — جستوجوی خطی، مرتب کردن و bisect، و یک dict — و برای هر سه جدول میگیریم. در n = 16,000 میانگینِ گامِ روشِ اول 7,807.5 است و روشِ دوم 13.06.
ولی نتیجهٔ اصلی جای دیگری است: یک پرسشِ ساده پیدا میکنیم که سریعترین ساختار اصلاً نمیتواند جوابش را بدهد و باید ۱۶٬۰۰۰ گام بردارد، در حالی که ساختارِ «کندتر» با ۳۲۲ گام جواب میدهد.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.