در این فصل چه یاد میگیری#
دو الگوریتمِ مرتبسازی مینویسیم که هر دو سادهاند، هر دو درست کار میکنند، و هر دو O(n²) هستند. هدف این نیست که در کارِ واقعی بهکارشان ببری؛ هدف این است که یک بار با دست انجامشان بدهی — چون بدونِ این، فصلهای ۴ و ۵ فقط دو طلسمِ حفظی میشوند.
و همانجا اولین درسِ واقعیِ مرتبسازی درمیآید: در n = 2,000 یکی 1,999,000 مقایسه میکند و دیگری 1,022,176. ولی وقتی ورودی از پیش مرتب باشد، دومی همان عدد را به 1,999 میرساند و ستونِ نسبتش 2.00 میشود، و اولی مو نمیزند.

آخر این فصل میتوانی:
selection sortوinsertion sortرا از صفر بنویسی- ناوردای حلقهٔ هرکدام را بگویی و در خروجی نشانش بدهی
- تعدادِ مقایسه را از تعدادِ جابهجایی جدا کنی و بگویی چرا این تفکیک مهم است
- بگویی چرا «بدترین حالت» و «حالتی که واقعاً داری» برای این دو الگوریتم یکی نیستند
قبل از شروع#
از ترمِ ۱ فصلِ ۴: شمارندهٔ عملیات، و اینکه شمارش قطعی است و ثانیه نیست.
از ترمِ ۳ فصلِ ۴: سه پرسشِ متفاوت — بدترین حالت، حالتِ متوسط، و حالتی که واقعاً داری. این فصل همان سه پرسش را روی مرتبسازی تکرار میکند و میبینی جوابشان برای دو الگوریتمِ هممرتبه کاملاً فرق دارد.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. selection sort با دست#
ایدهاش همان کاری است که با یک دسته کارت میکنی: کوچکترین را پیدا کن، بگذارش اول؛ از بقیه کوچکترین را پیدا کن، بگذارش دوم؛ و همینطور تا آخر.
def selection_sort_traced(values):
"""در هر پاس، کوچکترینِ باقیمانده را به جای درستش میآورد."""
a = list(values)
for i in range(len(a) - 1):
smallest = i
for j in range(i + 1, len(a)):
if a[j] < a[smallest]:
smallest = j
a[i], a[smallest] = a[smallest], a[i]
print(f"پاس {i + 1}: {a} <- {i + 1} عضوِ اول برای همیشه سرِ جایشاناند")
return a
start = [29, 10, 14, 37, 13, 25, 11, 18]
print("ورودی :", start)
print()
print("خروجی :", selection_sort_traced(start))
ورودی : [29, 10, 14, 37, 13, 25, 11, 18]
پاس 1: [10, 29, 14, 37, 13, 25, 11, 18] <- 1 عضوِ اول برای همیشه سرِ جایشاناند
پاس 2: [10, 11, 14, 37, 13, 25, 29, 18] <- 2 عضوِ اول برای همیشه سرِ جایشاناند
پاس 3: [10, 11, 13, 37, 14, 25, 29, 18] <- 3 عضوِ اول برای همیشه سرِ جایشاناند
پاس 4: [10, 11, 13, 14, 37, 25, 29, 18] <- 4 عضوِ اول برای همیشه سرِ جایشاناند
پاس 5: [10, 11, 13, 14, 18, 25, 29, 37] <- 5 عضوِ اول برای همیشه سرِ جایشاناند
پاس 6: [10, 11, 13, 14, 18, 25, 29, 37] <- 6 عضوِ اول برای همیشه سرِ جایشاناند
پاس 7: [10, 11, 13, 14, 18, 25, 29, 37] <- 7 عضوِ اول برای همیشه سرِ جایشاناند
خروجی : [10, 11, 13, 14, 18, 25, 29, 37]
جملهٔ سمتِ راستِ هر سطر یک «ناوردای حلقه» است: چیزی که قبل از هر دورِ حلقه درست است و بعد از آن هم درست میماند. ناوردای selection sort این است: i عضوِ اول کوچکترینهای کلِ فهرستاند و دیگر هیچوقت تکان نمیخورند. وقتی حلقه تمام شود، i برابرِ طولِ فهرست است و همین جمله میشود «همهچیز مرتب است».
و دو سطرِ آخر را ببین: فهرست از پاسِ ۵ مرتب بود و الگوریتم دو پاسِ دیگر هم رفت. selection sort هیچ راهی ندارد که بفهمد کارش تمام شده — چون برای پیدا کردنِ کوچکترین، باید همه را ببیند. این جمله را نگه دار؛ در بخشِ ۴ به یک عدد تبدیل میشود.
۲. insertion sort با دست#
ایدهٔ دوم هم از کارتبازی میآید، ولی از طرفِ دیگر: کارتهای دستِ چپت مرتباند؛ کارتِ بعدی را بردار و در جای درستش بینشان بنشان.
def insertion_sort_traced(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
print(f"پاس {i}: {a} <- {i + 1} عضوِ اول نسبت به هم مرتباند")
return a
print("ورودی :", start)
print()
print("خروجی :", insertion_sort_traced(start))
ورودی : [29, 10, 14, 37, 13, 25, 11, 18]
پاس 1: [10, 29, 14, 37, 13, 25, 11, 18] <- 2 عضوِ اول نسبت به هم مرتباند
پاس 2: [10, 14, 29, 37, 13, 25, 11, 18] <- 3 عضوِ اول نسبت به هم مرتباند
پاس 3: [10, 14, 29, 37, 13, 25, 11, 18] <- 4 عضوِ اول نسبت به هم مرتباند
پاس 4: [10, 13, 14, 29, 37, 25, 11, 18] <- 5 عضوِ اول نسبت به هم مرتباند
پاس 5: [10, 13, 14, 25, 29, 37, 11, 18] <- 6 عضوِ اول نسبت به هم مرتباند
پاس 6: [10, 11, 13, 14, 25, 29, 37, 18] <- 7 عضوِ اول نسبت به هم مرتباند
پاس 7: [10, 11, 13, 14, 18, 25, 29, 37] <- 8 عضوِ اول نسبت به هم مرتباند
خروجی : [10, 11, 13, 14, 18, 25, 29, 37]
ناوردای این یکی ضعیفتر است و همین ضعف قدرتش است. insertion sort نمیگوید «اینها سرِ جای نهاییشاناند»؛ فقط میگوید «اینها نسبت به هم مرتباند». در پاسِ ۶ عددِ 11 از انتها آمد و همه را یک خانه هل داد — کاری که selection sort هرگز لازم ندارد.
و به پاسِ ۳ دقت کن: هیچ چیزی تکان نخورد. 37 از قبل بزرگتر از همسایهاش بود، پس حلقهٔ داخلی همان اول ایستاد. این تنها جایی است که یکی از این دو الگوریتم میتواند کارِ کمتری بکند — و بخشِ ۵ نشان میدهد چقدر کمتر.
۳. دو شمارنده، نه یکی#
هزینهٔ مرتبسازی دو جزء دارد و جمع کردنشان در یک عدد، اطلاعات را از بین میبرد: تعدادِ مقایسه (چند بار پرسیدیم «کدام بزرگتر است؟») و تعدادِ جابهجایی (چند بار داده را واقعاً حرکت دادیم).
def selection_sort(values):
"""مرتبشده، تعدادِ مقایسه، تعدادِ جابهجایی."""
a = list(values)
comparisons = swaps = 0
n = len(a)
for i in range(n - 1):
smallest = i
for j in range(i + 1, n):
comparisons += 1
if a[j] < a[smallest]:
smallest = j
if smallest != i:
a[i], a[smallest] = a[smallest], a[i]
swaps += 1
return a, comparisons, swaps
def insertion_sort(values):
"""مرتبشده، تعدادِ مقایسه، تعدادِ جابهجایی."""
a = list(values)
comparisons = moves = 0
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0:
comparisons += 1
if a[j] <= key:
break
a[j + 1] = a[j]
moves += 1
j -= 1
a[j + 1] = key
return a, comparisons, moves
rng = random.Random(SEED)
LADDER = [250, 500, 1_000, 2_000]
shuffled = {n: rng.sample(range(10 * n), n) for n in LADDER}
check = shuffled[250]
print("هر دو با sorted یکی درمیآیند؟",
selection_sort(check)[0] == insertion_sort(check)[0] == sorted(check))
print("مقایسهٔ selection در n=250:", selection_sort(check)[1])
print("مقایسهٔ insertion در n=250:", insertion_sort(check)[1])
هر دو با sorted یکی درمیآیند؟ True
مقایسهٔ selection در n=250: 31125
مقایسهٔ insertion در n=250: 14113
سطرِ اول قبل از هر جدولی میآید. دو الگوریتمی که جوابِ متفاوت بدهند، اصلاً قابلِ مقایسه نیستند.
🤔 اول حدس بزن: برای
selection sort، ستونِ نسبتِ مقایسه و ستونِ نسبتِ جابهجایی را جدا حدس بزن. دو عددِ متفاوت بنویس، بعد جدول را ببین.
۴. selection sort: مقایسهٔ زیاد، جابهجاییِ کم#
print("— selection sort: مقایسه")
table([(n, selection_sort(shuffled[n])[1]) for n in LADDER], "مقایسه", ",d")
print("\n— selection sort: جابهجایی")
table([(n, selection_sort(shuffled[n])[2]) for n in LADDER], "جابهجایی", ",d")
— selection sort: مقایسه
n مقایسه نسبت به سطر قبل
250 31,125 —
500 124,750 4.01
1,000 499,500 4.00
2,000 1,999,000 4.00
— selection sort: جابهجایی
n جابهجایی نسبت به سطر قبل
250 240 —
500 495 2.06
1,000 997 2.01
2,000 1,989 1.99
4.00 برای مقایسه و 2.00 برای جابهجایی — یک الگوریتم، دو مرتبهٔ متفاوت.
مقایسهها O(n²) هستند چون در هر پاس کلِ باقیمانده باید دیده شود. جابهجاییها O(n) هستند چون هر پاس حداکثر یک جابهجایی دارد — و اگر کوچکترین از قبل سرِ جایش باشد، هیچ. برای همین است که عددِ سطرِ آخر 1,989 است و نه 1,999: ده پاس اصلاً جابهجایی نخواستند.
و این تفکیک عملی است، نه تزئینی: اگر جابهجا کردنِ یک عضو خیلی گران باشد (مثلاً هر عضو یک رکوردِ بزرگ باشد)، selection sort با اینکه «کند» است، کمترین حرکتِ ممکن را انجام میدهد. مرتبهٔ کلی یک عدد است؛ تصمیم با دو عدد گرفته میشود.
۵. حالا ورودی را عوض کن#
اول همان ورودیِ تصادفیِ بخشِ ۴، این بار برای الگوریتمِ دوم.
🤔 اول حدس بزن:
insertion sortروی ورودیِ تصادفی. دو عدد بنویس — ستونِ نسبتِ مقایسه و ستونِ نسبتِ جابهجایی — و بعد یک حدسِ سوم که مهمتر از هر دو است: نسبتِ جابهجاییهای این الگوریتم به جابهجاییهایselection sortدرn = 2,000چقدر است؟
print("— insertion sort روی ورودیِ تصادفی: مقایسه")
table([(n, insertion_sort(shuffled[n])[1]) for n in LADDER], "مقایسه", ",d")
print("\n— insertion sort روی ورودیِ تصادفی: جابهجایی")
table([(n, insertion_sort(shuffled[n])[2]) for n in LADDER], "جابهجایی", ",d")
— insertion sort روی ورودیِ تصادفی: مقایسه
n مقایسه نسبت به سطر قبل
250 14,113 —
500 65,356 4.63
1,000 253,743 3.88
2,000 1,022,176 4.03
— insertion sort روی ورودیِ تصادفی: جابهجایی
n جابهجایی نسبت به سطر قبل
250 13,868 —
500 64,865 4.68
1,000 252,749 3.90
2,000 1,020,183 4.04
روی ورودیِ تصادفی، insertion sort هم 4 میدهد — O(n²). مقایسههایش حدودِ نصفِ selection sort است (1,022,176 در برابرِ 1,999,000)، ولی جابهجاییهایش بیش از پانصد برابر بیشتر است: 1,020,183 در برابرِ 1,989. دقیقاً معاملهٔ برعکس.
🤔 اول حدس بزن: حالا همان دو الگوریتم را روی فهرستی میبریم که از قبل مرتب است. برای هرکدام یک عدد در ستونِ نسبت بنویس.
already = {n: sorted(shuffled[n]) for n in LADDER}
reverse = {n: sorted(shuffled[n], reverse=True) for n in LADDER}
print("— insertion sort روی ورودیِ از پیش مرتب")
table([(n, insertion_sort(already[n])[1]) for n in LADDER], "مقایسه", ",d")
print("\n— insertion sort روی ورودیِ وارونه")
table([(n, insertion_sort(reverse[n])[1]) for n in LADDER], "مقایسه", ",d")
print("\n— selection sort روی همان ورودیِ از پیش مرتب")
table([(n, selection_sort(already[n])[1]) for n in LADDER], "مقایسه", ",d")
— insertion sort روی ورودیِ از پیش مرتب
n مقایسه نسبت به سطر قبل
250 249 —
500 499 2.00
1,000 999 2.00
2,000 1,999 2.00
— insertion sort روی ورودیِ وارونه
n مقایسه نسبت به سطر قبل
250 31,125 —
500 124,750 4.01
1,000 499,500 4.00
2,000 1,999,000 4.00
— selection sort روی همان ورودیِ از پیش مرتب
n مقایسه نسبت به سطر قبل
250 31,125 —
500 124,750 4.01
1,000 499,500 4.00
2,000 1,999,000 4.00
سه جدول، و کلِ حرفِ این فصل در فاصلهٔ سطرِ آخرشان است.
- روی ورودیِ مرتب،
insertion sortدرn = 2,000فقط1,999مقایسه میکند و ستونِ نسبتش2.00است. یعنیO(n)— چون برای هر عضو، همان مقایسهٔ اول جواب میدهد و حلقهٔ داخلی هرگز نمیچرخد. - روی ورودیِ وارونه، همان تابع به
1,999,000میرسد. هزار برابرِ حالتِ قبل، با همان کد و همان تعدادِ عضو. - و
selection sortروی ورودیِ مرتب هم دقیقاً1,999,000میکند — مو نمیزند.
پس «O(n²) بودن» دربارهٔ این دو الگوریتم دو چیزِ متفاوت میگوید. برای selection sort یک واقعیت است؛ برای insertion sort فقط بدترین حالت است، و حالتی که واقعاً داری میتواند خطی باشد. این همان تفکیکی است که ترمِ ۳ فصلِ ۴ برای hash table ساخت، و فصلِ ۸ نشان میدهد که sorted واقعی دقیقاً از همین خاصیت سوءاستفاده میکند.
✅ چک کن: فهرستی بساز که فقط دو عضوش جابهجا باشند — مثلاً
sorted(shuffled[1_000])را بگیر و دو عضوِ کنارِ هم را عوض کن. مقایسههایinsertion sortباید نزدیکِ1,000بماند، نه چیزی نزدیکِ نیممیلیون. اگر عددِ بزرگ گرفتی، احتمالاً بهجای دو همسایه، عضوِ اول و آخر را جابهجا کردهای — و آن یکی واقعاً گران است.
۶. مقایسهای که ممکن نیست#
هر دو الگوریتمِ این فصل روی یک فرض ایستادهاند: هر دو عضو را میشود با هم مقایسه کرد. وقتی این فرض نباشد، هیچکدام کار نمیکنند.
mixed = [3, "10", 7]
try:
insertion_sort(mixed)
except TypeError as err:
print(f"{type(err).__name__}: {err}")
TypeError: '<=' not supported between instances of 'int' and 'str'
🔧 اگر کار نکرد: پیام دقیقاً میگوید کجا گیر کرده: عملگرِ
<=بینِ یکintو یکstrتعریف نشده. این خطا معمولاً از داده میآید، نه از کد — یک فایل که بعضی سطرهایش عدد است و بعضی سطرهایش رشتهٔ عدد. راهِ حل این است که قبل از مرتبسازی نوع را یکدست کنی، نه اینکه سطرهای مشکلدار را دور بریزی. و اگر مطمئنی همه عددند ولی باز این خطا را میگیری، یعنی مطمئن نبودی.
۷. و حالا با ساعت#
print("— selection sort (زمان)")
table([(n, 1000 * clock(lambda v=shuffled[n]: selection_sort(v), repeat=2))
for n in LADDER], "زمان (ms)", ",.1f")
print("\n— insertion sort روی ورودیِ تصادفی (زمان)")
table([(n, 1000 * clock(lambda v=shuffled[n]: insertion_sort(v), repeat=2))
for n in LADDER], "زمان (ms)", ",.1f")
— selection sort (زمان)
n زمان (ms) نسبت به سطر قبل
250 1.4 —
500 6.2 4.53
1,000 26.9 4.35
2,000 108.8 4.05
— insertion sort روی ورودیِ تصادفی (زمان)
n زمان (ms) نسبت به سطر قبل
250 1.4 —
500 7.4 5.24
1,000 26.4 3.54
2,000 105.9 4.01
ساعت همان 4 را میگوید، با همان لهجهٔ لرزانی که ترمِ ۱ فصلِ ۵ نشان داد. و یک چیزِ دیگر هم میگوید: دو الگوریتمی که تعدادِ مقایسهشان دو برابر با هم فرق داشت، زمانشان تقریباً یکی درآمد — چون insertion sort آن مقایسهٔ کمتر را با جابهجاییِ خیلی بیشتر پس داد. دو ستونِ بخشِ ۳ تا ۵ دقیقاً همین را از قبل گفته بودند.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ دو الگوریتمِ مرتبسازی با جوابِ تأییدشدهٔ برابر، هرکدام روی سه نوع ورودی: تصادفی، از پیش مرتب، و وارونه. در کدام بازهٔ
n؟ ۲۵۰ تا ۲٬۰۰۰ — بازهای که در آن پایتونِ خالص با دو میلیون مقایسه در حدودِ یک دهمِ ثانیه تمام میکند. با چند تکرار، و کمینه یا میانگین؟ جدولهای شمارش یک اجرا و قطعی؛ جدولِ زمان دو تکرار بهعلاوهٔ گرمکننده، کمینه.
🤖 از دستیارت بپرس: «چرا
selection sortروی ورودیِ از پیش مرتب هیچ سریعتر نمیشود؟» بعد این را هم بپرس: «کدامیک از این دو الگوریتم برای مرتب کردنِ رکوردهای خیلی بزرگ بهتر است و چرا؟» — جوابِ درست باید به تعدادِ جابهجایی برسد، نه به تعدادِ مقایسه. اگر دستیارت فقط گفت «هر دوO(n²)هستند و فرقی نمیکنند»، جدولِ جابهجاییِ بخشِ ۴ و ۵ را جلویش بگذار.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
selection sort |
سلکشن سورت | در هر پاس کوچکترینِ باقیمانده را به جای درستش میبرد |
insertion sort |
اینسرشن سورت | هر عضو را در جای درستش بینِ عضوهای مرتبِ قبلی مینشاند |
| loop invariant | لوپ اینوَریِنت | جملهای که قبل و بعد از هر دورِ حلقه درست میماند |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
هر دو الگوریتمِ این فصل یک اشکالِ مشترک دارند: در هر پاس، فقط یک عضو را سرِ جایش میگذارند. برای n عضو یعنی n پاس، و هر پاس هم به n نگاه میکند — همانجا n² متولد میشود.
فصلِ بعد ایدهٔ کاملاً متفاوتی میآورد: فهرست را نصف کن، هر نصف را مرتب کن، دو نصفِ مرتب را به هم بچسبان. نتیجهاش این است که در n = 8,000 بهجای میلیونها مقایسه، فقط 93,704 مقایسه لازم میشود و ستونِ نسبت از 4.00 به 2.19 میافتد. و آنجا هم میشماریم که این سرعت با چه حافظهای خریده شده.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.