مرتب‌سازی مسابقه‌ای

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
مرتب‌سازی مسابقه‌ای
کلاس الگوریتم مرتب‌سازی
ساختمان داده‌ها آرایه
عملکرد بدترین حالت O(n\log n)
عملکرد حالت متوسط O(n\log n)

مرتب‌سازی مسابقه‌ای (به انگلیسی: Tournament sort) یک الگوریتم مرتب‌سازی است. این الگوریتم مرتب‌سازی انتخابی ساده را با استفاده از یک صف اولویت‌دار برای پیدا کردن عنصر بعدی در مرتب‌سازی بهبود می‌بخشد. در مرتب‌سازی انتخابی ساده، O(n) عمل صورت می‌گیرد تا عنصر بعدی از n عنصر را انتخاب کند؛ در یک مرتب‌سازی مسابقه‌ای، O(\log n) عمل صورت می‌گیرد (پس از ساختن مسابقه ابتدایی در O(n)). مرتب‌سازی مسابقه‌ای یک تنوع از مرتب‌سازی هرمی می‌باشد.

پانویس[ویرایش]