بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 33: مرتب‌سازی Sorting

مرتب‌سازی درجی (insertion sort) و ادغامی (merge sort) را خودمان پیاده می‌کنیم، پایداری (stability) را می‌فهمیم و با sorted(key=...) و tuple مرتب‌سازی چندکلیدی می‌نویسیم.

در این جلسه یاد می‌گیری

درس

مرتب‌سازی درجی هر عنصر را برمی‌دارد و آن را در بخش مرتب‌شده‌ی سمت چپ، با جابه‌جا کردن (shift) عناصر بزرگ‌تر، در جای درست می‌نشاند. بدترین حالت O(n²) و روی داده‌ی تقریباً مرتب نزدیک O(n) است؛ درجا (in-place) و پایدار است.

def insertion_sort(a):
    for i in range(1, len(a)):
        current = a[i]
        j = i - 1
        while j >= 0 and a[j] > current:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = current
    return a

print(insertion_sort([5, 2, 4, 1]))

مرتب‌سازی ادغامی لیست را نصف می‌کند، هر نیمه را بازگشتی مرتب می‌کند و دو نیمه‌ی مرتب را در O(n) ادغام (merge) می‌کند. log n سطح × O(n) در هر سطح = O(n log n) در همه‌ی حالت‌ها، به قیمت O(n) حافظه‌ی اضافه.

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

print(merge([1, 4, 9], [2, 3, 10]))

مرتب‌سازی پایدار (stable) ترتیب نسبی عناصر با کلید برابر را حفظ می‌کند. در merge شرط <= همین را تضمین می‌کند. sorted و list.sort پایتون (Timsort، O(n log n)) پایدارند؛ پس می‌توان چندمرحله‌ای مرتب کرد: اول با کلید فرعی، بعد با کلید اصلی.

rows = [("ops", "Parsa"), ("dev", "Nima"), ("ops", "Armin"), ("dev", "Mina")]
by_name = sorted(rows, key=lambda r: r[1])
print(sorted(by_name, key=lambda r: r[0]))

key تابعی است که برای هر عنصر یک بار صدا زده می‌شود و مقایسه روی خروجی آن انجام می‌شود. برگرداندن tuple یعنی ترتیب چندکلیدی: اول عضو اول، در تساوی عضو دوم و... برای نزولی کردن فقط یک کلید عددی، آن را منفی کنید.

staff = [("Parsa", "dev", 5200), ("Nima", "dev", 6100), ("Mina", "ops", 4800)]
for name, dept, salary in sorted(staff, key=lambda s: (s[1], -s[2], s[0])):
    print(dept, salary, name)

در عمل همیشه از sorted/sort استفاده کنید؛ پیاده‌سازی دستی برای فهم الگوریتم و برای مسائلی مثل شمردن جابه‌جایی‌ها است. مقایسه: insertion (O(n²)، ساده، پایدار)، merge (O(n log n)، پایدار، حافظه‌ی اضافه)، counting sort (O(n + k) برای اعداد صحیح در بازه‌ی کوچک).

مثال‌های این جلسه

چالش‌ها

  1. Length Then Alphabet (آسان)
  2. Scoreboard (آسان)
  3. Insertion Sort (آسان)
  4. Counting Shifts (متوسط)
  5. Merge Step (متوسط)
  6. Merge Sort (متوسط)
  7. Stable by Priority (متوسط)
  8. Counting Inversions (سخت)
  9. Department Report (سخت)
  10. Stable Sort with Key (سخت)
  11. Version Sort (متوسط)
  12. Counting Sort (سخت)

بیشتر بخوان

← جلسه‌ی 32: جست‌وجو جلسه‌ی 34: پشته و صف →