رایانش و هوش مصنوعی · آزمایش
مرتبسازی بدون مقایسهٔ همه چیز
نامزدها، معرفها، گرافی از مقایسههای مجاز، و کرانی که از 2011 پابرجا ماند. چهار پرسش، از مبتدی تا پیشرفته، دربارهٔ اینکه چگونه مرتب کنیم وقتی برخی جفتها را نمیتوان مقایسه کرد.
1 · قاعده2 · مرحلهها3 · QuickSort4 · هنوز باز
1 · ببین چه چیزی تغییر میکند
مبتدی
چه چیزی مرتبسازی تعمیمیافته را با مرتبسازی معمولی متفاوت میکند؟
2 · مرحلهها را بشمار
هر مرحلهٔ الگوریتم برای دستکم نیمی از پیوندهای هنوز معلق یک پیشبینی تعیین میکند و بقیه را به بعد موکول میکند. گرافی حدود یک میلیون پیوند دارد، تقریباً 2²⁰.
متوسط
حداکثر تقریباً چند مرحله لازم است تا هر پیوند یک پیشبینی داشته باشد؟
3 · پیدا کن چه چیزی QuickSort را از کار میاندازد
پیشرفته
چرا نمیتوان روشی به سبک QuickSort را بهسادگی برای مرتبسازی تعمیمیافته به کار برد؟
4 · ببین مقاله چه چیزی را به دست نمیدهد
پیشرفته
مقاله کدامیک از اینها را به دست نمیدهد؟
ترتیب بازیابی شد
—