جلسهی 20: مرتبسازی و مقایسه Sorting and Comparing
مرتب کردن با جابهجاییِ همسایهها و «جفتهای نامرتب»، پیدا کردنِ بزرگترین با کمترین مقایسه، جدولِ حذفی، و برگرداندنِ پنکیکها.
در این جلسه یاد میگیری
- کمترین تعدادِ جابهجاییِ همسایهها برای مرتب کردن را با شمردنِ جفتهای نامرتب پیدا میکنی.
- میدانی پیدا کردنِ بزرگترین بین n چیز دقیقاً n − ۱ مقایسه لازم دارد.
- در جدولِ حذفی تعداد بازیها و دومین بهترین را حساب میکنی.
درس
عددها را با جابهجا کردنِ دو همسایه مرتب کن. بعد «از اول» را بزن و سعی کن با جابهجاییهای کمتری انجامش دهی. کمترین تعداد چند است؟
جفتِ نامرتب: دو عدد که عددِ بزرگتر جلوتر از کوچکتر آمده. در ۳، ۱، ۴، ۵، ۲ جفتهای نامرتب: (۳،۱)، (۳،۲)، (۴،۲)، (۵،۲): ۴ تا. هر جابهجاییِ دو همسایه دقیقاً یک جفت را عوض میکند: اگر نامرتب بودند مرتب میشوند (یکی کم) و برعکس. پس کمترین تعداد جابهجایی = تعداد جفتهای نامرتب. بیشترینِ آن برای n عدد وقتی است که کاملاً برعکس باشند: C(n، ۲).
پیدا کردنِ بزرگترین: با هر مقایسه یکی «میبازد». هر عددی جز بزرگترین باید دستکم یک بار ببازد (وگرنه ممکن است بزرگترین باشد). پس دستکم n − ۱ مقایسه لازم است، و n − ۱ هم کافی است (قهرمانِ فعلی را با بعدی مقایسه کن).
جدول حذفی: هر بازی دقیقاً یک تیم را حذف میکند و همه جز قهرمان باید حذف شوند: n تیم ← n − ۱ بازی.
دومین بهترین: در جدول حذفیِ ۱۶ نفره، دومی حتماً فقط به قهرمان باخته. قهرمان ۴ بار بازی کرده، پس ۴ نفر نامزدِ دومیاند و ۳ بازیِ دیگر بینشان کافی است: ۱۵ + ۳ = ۱۸ مقایسه.
پنکیک: دستهای پنکیک با اندازههای مختلف؛ تنها کار مجاز این است که چند تای بالا را با کفگیر برگردانی. برای مرتب کردنِ هر دستهی ۴تایی، ۴ برگرداندن همیشه کافی است.
چالشها
- A Knockout Cup (آسان)
- Count the Swaps (آسان)
- The Worst Row (متوسط)
- The Heaviest Box (متوسط)
- The Runner-Up (سخت)
- Flipping Pancakes (سخت)
← جلسهی 19: ترازو و وزن کردن جلسهی 21: آزمونک بازی و الگوریتم →