بنیاد — ساختمان داده و الگوریتم، با اندازه‌گیری واقعی

فصل ۳ از ۹

پیشرفت ترم
۰٪

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

دو الگوریتمِ مرتب‌سازی می‌نویسیم که هر دو ساده‌اند، هر دو درست کار می‌کنند، و هر دو 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 می‌افتد. و آن‌جا هم می‌شماریم که این سرعت با چه حافظه‌ای خریده شده.

به آخر این فصل رسیدی!

اگر ساختی و جواب داد، این دکمه مال توست.