جلسهی 33: مرتبسازی Sorting
مرتبسازی درجی (insertion sort) و ادغامی (merge sort) را خودمان پیاده میکنیم، پایداری (stability) را میفهمیم و با sorted(key=...) و tuple مرتبسازی چندکلیدی مینویسیم.
در این جلسه یاد میگیری
- مرتبسازی درجی
O(n²)را پیاده کنید و بدانید چرا روی دادهی تقریباً مرتب سریع است. - مرتبسازی ادغامی
O(n log n)را با تقسیم و حل (divide and conquer) بنویسید. - مفهوم پایداری را بفهمید و از آن در مرتبسازی چندمرحلهای استفاده کنید.
- با
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) برای اعداد صحیح در بازهی کوچک).
مثالهای این جلسه
- مثال تابع در پایتون: def insertion_sort(a):
- مثال تابع در پایتون: def merge(left, right):
- مثال لیست در پایتون: rows = [("ops", "Parsa"), ("dev", "Nima"), …
- مثال حلقه for در پایتون: for name, dept, salary in sorted(staff, key…
چالشها
- Length Then Alphabet (آسان)
- Scoreboard (آسان)
- Insertion Sort (آسان)
- Counting Shifts (متوسط)
- Merge Step (متوسط)
- Merge Sort (متوسط)
- Stable by Priority (متوسط)
- Counting Inversions (سخت)
- Department Report (سخت)
- Stable Sort with Key (سخت)
- Version Sort (متوسط)
- Counting Sort (سخت)