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

آخر این فصل میتوانی:
- افرازِ یک فهرست حولِ یک
pivotرا با دست انجام بدهی quicksortراin-placeبنویسی و درستیاش را ثابت کنی- بدترین حالتش را بسازی و با شمارش نشانش بدهی
- بگویی
pivotتصادفی دقیقاً چه چیزی را عوض میکند و چه چیزی را نه
قبل از شروع#
از فصلِ ۱: بازنویسیِ یک recursion به حلقه — بخشِ ۴ این فصل واقعاً به آن احتیاج پیدا میکند.
از ترمِ ۳ فصلِ ۴: ورودیِ خصمانه، و اینکه بدترین حالتِ یک ساختار وقتی خطرناک است که کسِ دیگری ورودی را انتخاب کند. quicksort نمونهٔ کلاسیکِ همین حرف است.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. افراز، با دست#
ایدهٔ quicksort از طرفِ دیگرِ «تقسیم و حل» میآید. merge sort کورکورانه از وسط میشکست و کارِ سخت را در ادغام انجام میداد. quicksort برعکس است: کارِ سخت را در خودِ شکستن انجام میدهد، و بعد هیچ ادغامی لازم نیست.
یک عضو را pivot میگیریم و فهرست را طوری میچینیم که هر چیزِ کوچکترش سمتِ چپش باشد و هر چیزِ بزرگترش سمتِ راستش. آنوقت pivot سرِ جای نهاییاش است و دو طرفش دو مسئلهٔ مستقلاند.
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:]))
ورودی : [29, 10, 14, 37, 13, 25, 11, 18]
pivot : 29
بعد از افراز : [18, 10, 14, 13, 25, 11, 29, 37]
جای نهاییِ pivot: 6 · مقایسه: 7
سمتِ چپ همه کوچکترند؟ True
سمتِ راست همه بزرگترند؟ True
هشت عضو، هفت مقایسه، و هیچ فهرستِ تازهای ساخته نشد — فقط عضوها داخلِ همان list جابهجا شدند. اسمِ این کار in-place است.
ولی به خروجی خوب نگاه کن: دو طرفِ pivot مرتب نیستند، فقط تفکیک شدهاند. و همین کافی است، چون هر طرف را میشود با همان روش حل کرد.
و یک چیزِ دیگر هم در همین خروجی هست که بعداً به کارمان میآید: pivot عددِ 29 بود و در جای ششم نشست، یعنی شش عضو کوچکترش بودند و یکی بزرگتر. تقسیم عادلانه نشد. اینکه چقدر عادلانه شود، تماماً به این بستگی دارد که pivot چه عددی باشد.
۲. quicksort روی ورودیِ تصادفی#
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"])
با sorted یکی است؟ True
مقایسه: 10150 · عمق: 20
🤔 اول حدس بزن: ستونِ نسبتِ مقایسهها چه عددی میدهد؟ و عمق چطور؟ دو عدد بنویس، بعد جدول را ببین.
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")
— ورودیِ تصادفی: مقایسه
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
نسبتها حولِ 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 میگیرد، پس کافی است فهرست از قبل مرتب باشد.
climbing = sorted(shuffled[2_000])
print("ورودی از پیش مرتب است؟", climbing == sorted(climbing))
try:
quicksort(climbing)
except RecursionError as err:
print(f"{type(err).__name__}: {err}")
ورودی از پیش مرتب است؟ True
RecursionError: maximum recursion depth exceeded
🔧 اگر کار نکرد: این خطا اینجا یک علامت است، نه یک باگ. عمقِ
recursionبرابرِnشده و از سقفِ پایتون رد کرده. وسوسهٔ اول این است که سقف را بالا ببری — و آن دقیقاً کارِ غلط است، چون مسئله عمق نیست، مسئله این است که تقسیم اصلاً انجام نمیشود. سقف را که بالا ببری، برنامه بهجای یک استثنای تمیز، ساعتها کار میکند یا نشست را میکشد.راهِ درست، برداشتنِ
recursionاست. فصلِ ۱ گفت هرrecursionرا میشود به حلقه برگرداند؛ اینجا جایی است که واقعاً باید این کار را بکنی.
۴. همان الگوریتم، با یک stack صریح#
پایتون فراخوانیهای تمامنشده را روی call stack نگه میداشت. ما همان کار را با یک list انجام میدهیم — همان stackی که ترمِ ۲ فصلِ ۷ ساخت، با همان انضباطِ LIFO. بهجای فراخوانی، بازههای کارنکرده را در آن میریزیم.
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)
دو نسخه یک جواب میدهند؟ True
و یک تعداد مقایسه؟ True · 10150
روی ورودیِ از پیش مرتب هم کار میکند؟ True
همان جواب، همان تعدادِ مقایسه، و این بار روی ورودیِ مرتب هم تمام میشود. حالا میشود بدترین حالت را واقعاً اندازه گرفت.
🤔 اول حدس بزن: روی ورودیِ از پیش مرتب، ستونِ نسبتِ مقایسهها چه عددی میدهد؟ بنویسش، بعد جدول را ببین.
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")
— ورودیِ از پیش مرتب، pivot = عضوِ اول
n مقایسه نسبت به سطر قبل
250 31,125 —
500 124,750 4.01
1,000 499,500 4.00
2,000 1,999,000 4.00
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به چند میرسند؟ مرتبه و عدد دو حدسِ متفاوتاند و هر دو را میخواهیم.
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")
— همان ورودیِ مرتب، pivot تصادفی
n مقایسه نسبت به سطر قبل
250 2,653 —
500 4,571 1.72
1,000 10,032 2.19
2,000 23,938 2.39
1,999,000 به 23,938 رسید — روی همان ورودی، با همان کدِ افراز. و ستونِ نسبت از 4.00 به حدودِ 2.2 برگشت: O(n log n).
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")
— ورودیِ مرتبِ بزرگتر، pivot تصادفی
n مقایسه نسبت به سطر قبل
1,000 11,951 —
2,000 24,661 2.06
4,000 55,531 2.25
8,000 115,750 2.08
⚠️ مواظب باش:
pivotتصادفی بدترین حالت را حذف نمیکند؛ فقط کاری میکند که کسی نتواند آن را سفارش بدهد. با بدشانسیِ محض هنوز ممکن است هر بار بدترینpivotانتخاب شود — احتمالش فقط آنقدر کوچک است که به آن فکر نمیکنیم.و این دقیقاً همان پادزهری است که ترمِ ۳ فصلِ ۴ برای
hash tableدید: آنجا هم مسئله این بود که مهاجم قاعدهٔ ثابت را میداند، و راهِ حل تصادفی کردنِ همان قاعده بود. دو ساختارِ کاملاً متفاوت، یک الگوی دفاعیِ واحد.
۶. in-place رایگان نیست#
quicksort هیچ فهرستِ تازهای برای داده نمیسازد. ولی بازههای کارنکرده جایی باید بمانند — روی call stack یا در todo. و آن جا هم حافظه است.
🤔 اول حدس بزن: بیشترین اندازهٔ
todoرا برای سه حالت حدس بزن: ورودیِ مرتب باpivotاول، همان ورودی باpivotتصادفی، و ورودیِ تصادفی. برای هر سه بنویس با هشت برابر شدنِnچند برابر میشوند — و مخصوصاً بنویس آیا انتظار داری هر سه یک شکل باشند.
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,}")
— بیشترین اندازهٔ 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
ستونِ اول دقیقاً n است و دو ستونِ دیگر با هشت برابر شدنِ n فقط از 14 به 20 و از 12 به 18 میروند. یعنی حافظهٔ کمکیِ quicksort بینِ O(log n) و O(n) است و همان چیزی تعیینش میکند که مرتبهٔ زمانش را تعیین میکرد: کیفیتِ pivot.
(دلیلِ عددِ n در ستونِ اول این است که هر افراز یک بازهٔ خالی هم تولید میکند و کدِ ما آن را هم روی todo میگذارد. کنار گذاشتنِ بازههای خالی، تمرینِ اجباریِ همین فصل است.)
مقایسهاش با فصلِ ۴ را صریح بنویس: merge sort در n = 8,000 روی هم 103,808 عضو کپی میکرد و در هر لحظه به اندازهٔ n حافظهٔ اضافه داشت. quicksort روی ورودیِ تصادفی هجده جفت عدد نگه میدارد. این معاملهٔ اصلیِ بینِ این دو الگوریتم است.
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}")
— ورودیِ تصادفی (زمان)
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
روی این ماشین، یک خط تغییر در انتخابِ 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تصادفی بدترین حالت را از بین میبرد یا نه؟» — جوابِ درست باید بگوید نه، فقط دیگر کسی نمیتواند سفارشش بدهد. اگر دستیارت گفت «بدترین حالت دیگر ممکن نیست»، از او بخواه احتمالش را برایت حساب کند.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
quicksort |
کوییکسورت | مرتبسازی با افرازِ پیاپی حولِ یک عضوِ انتخابشده |
pivot |
پیوت | عضوی که فهرست حولِ آن به کوچکتر و بزرگتر تقسیم میشود |
| partition | پارتیشن | خودِ عملِ تقسیم کردن حولِ pivot |
in-place |
اینپلیس | الگوریتمی که داده را در جای خودش جابهجا میکند |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
سه الگوریتم نوشتیم و هیچکدام از n log n بهتر نشد. این یک تصادف نیست و فصلِ بعد ثابتش میکند — نه با اندازهگیری، با شمردن: تعدادِ ترتیبهای ممکنِ n عضو n! است و هر مقایسه حداکثر آن را نصف میکند.
بعد عددش را میگیریم: در n = 8,000 کمترین تعدادِ مقایسهٔ ممکن 92,193 است و merge sort ما 93,704 میکند — نسبتِ 1.02. و آخرش الگوریتمی میآوریم که این مرز را میشکند، چون اصلاً مقایسه نمیکند — و همانجا اندازه میگیریم که کجا برنده است و کجا ۱۹۷ برابر بازنده.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.