مرتب‌سازی؛ نخستین الگوریتم‌های کلاسیک

مرتب‌سازی (Sorting) یعنی چیدن عناصر یک مجموعه بر اساس قاعده‌ای مشخص — معمولاً از کوچک به بزرگ. شاید ساده به نظر برسد، اما مرتب‌سازی یکی از قدیمی‌ترین مسائل علوم کامپیوتر است: تقریباً هر برنامهٔ جدی جایی به دادهٔ مرتب‌شده نیاز دارد، از فهرست تماس‌ها تا نتایج جستجو. به همین دلیل صدها الگوریتم مرتب‌سازی ساخته شده و مقایسهٔ آن‌ها بهترین تمرین برای درک مفهوم «کارایی» است.

در این درس دو الگوریتم کلاسیک را خودتان پیاده‌سازی می‌کنید و بعد با ابزار درس قبل (نماد O بزرگ) هزینهٔ آن‌ها را می‌سنجید.

مرتب‌سازی حبابی (Bubble Sort)

ایدهٔ حبابی ساده‌ترین توصیف ممکن را دارد: یک‌به‌یک روی آرایه راه بروید؛ اگر دو همسایه جای‌به‌جایند، جابه‌جایشان کنید. با هر دورِ کامل، بزرگ‌ترین عنصرِ باقی‌مانده مثل حباب به انتهای آرایه می‌رود.

def bubble_sort(numbers):
    data = list(numbers)
    n = len(data)
    for i in range(n):
        for j in range(n - 1 - i):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
    return data

print(bubble_sort([5, 2, 8, 1, 9, 3]))

خط‌به‌خط:

1. data = list(numbers) یک کپی می‌سازد تا آرایهٔ اصلی صاحب تابع تغییر نکند؛ این ادب حرفه‌ای است.
2. حلقهٔ بیرونی n دور کامل می‌زند؛ حلقهٔ درونی با n - 1 - i هر بار کوتاه‌تر می‌شود، چون انتهای آرایه بعد از هر دور مرتب است.
3. data[j], data[j + 1] = data[j + 1], data[j] جابه‌جایی هم‌زمان پایتونی است؛ نیازی به متغیر کمکی نیست.
4. اگر دو عنصر برابر باشند شرط > برقرار نمی‌شود، پس ترتیب عناصر برابر حفظ می‌شود (پایداری در این پیاده‌سازی).

مرتب‌سازی انتخابی (Selection Sort)

ایدهٔ انتخابی: در هر گام، کوچک‌ترین عنصرِ بخشِ مرتب‌نشده را «انتخاب» کنید و به ابتدای همان بخش ببرید.

def selection_sort(numbers):
    data = list(numbers)
    for i in range(len(data)):
        min_index = i
        for j in range(i + 1, len(data)):
            if data[j] < data[min_index]:
                min_index = j
        data[i], data[min_index] = data[min_index], data[i]
    return data

print(selection_sort([64, 25, 12, 22, 11]))

نکتهٔ جالب: برای آرایهٔ خالی هم درست کار می‌کند — selection_sort([]) خروجی [] می‌دهد، چون حلقه‌ها اصلاً اجرا نمی‌شوند. آزمودن «حالت مرزی» مثل ورودی خالی عادت مهمی است.

کدام بهتر است؟

هر دو در بدترین حالت O(n²) مقایسه انجام می‌دهند، اما تفاوت مهمی دارند:

انتخابی جابه‌جایی کمتری دارد و وقتی «نوشتن» گران باشد (مثلاً حافظهٔ فلش) بهتر است؛ حبابی بهینه‌شده روی دادهٔ تقریباً مرتب سریع‌تر تمام می‌شود.

تمرین‌ها

# Write your code here

def bubble_sort_count(numbers):
    data = list(numbers)
    n = len(data)
    swaps = 0
    for i in range(n):
        for j in range(n - 1 - i):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
                swaps += 1
    return data, swaps

result, count = bubble_sort_count([5, 1, 4, 2, 8])
print(result, count)

::: :::

خلاصه

• مرتب‌سازی چیدن داده‌ها بر اساس قاعده‌ای مشخص است و پایهٔ بی‌شمار کاربرد واقعی.
• حبابی با جابه‌جایی همسایه‌ها کار می‌کند؛ انتخابی کوچک‌ترین عنصر باقی‌مانده را برمی‌دارد.
• هر دو در بدترین حالت O(n²) هستند، اما تعداد جابه‌جایی و رفتار روی دادهٔ مرتب تفاوت‌های عملی مهمی ایجاد می‌کند.
• در پایتون واقعی از sorted() با پیچیدگی O(n log n) استفاده کنید.

با این درس، مثلث «الگوریتم، پیچیدگی، پیاده‌سازی» کامل شد؛ حالا می‌توانید سراغ ساختارهای دادهٔ واقعی‌تر بروید.