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

مرتب‌سازی تیم به دنبال دنباله مرتب با کمترین اندازه، minrun، می‌باشد تا با استفاده از آن مرتب‌سازی را انجام دهد.
الگوریتم مرتب‌سازی تیم ترکیبی از دو الگوریتم مرتب‌سازی است به نام‌های مرتب‌سازی ادغامی و مرتب‌سازی درجی. این طراحی بر روی بسیاری از انواع داده‌ها در جهان واقعی بسیار خوب عمل می‌کند. این الگوریتم اولین بار توسط Tim Peters در سال ۲۰۰۲ برای استفاده در پایتون بیان شد. الگوریتم برای پیدا کردن زیر مجموعه‌ای از داده‌ها که جستجو را بهینه‌تر کنند طراحی شد. به‌وسیله مرتب‌سازی ادغامی زیر مجموعه مشخص می‌شود. این زیر مجموعه یک run نامیده می‌شود. از این runها به تعدادی پیدا می‌شود که معیارهای لازم برآورده شود. مرتب‌سازی تیم، مرتب‌سازی استاندارد پایتون از مدل ۲٫۳ است. هم اکنون در جاوا ۷ و همچنین در اندروید برای مرتب‌سازی آرایه‌ها از این مرتب‌سازی استفاده می‌شود.
الگوریتم چگونه کار می‌کند؟
الگوریتم برای استفاده از این مزیت که داده‌ها به‌طور جزئی مرتب شده‌اند طراحی شده است. جستجوی تبم کار خود را با پیداکردن runها در داده ادامه می‌دهد. یک run یک زیرآرایه از آرایه اصلی داده‌ها می‌باشد که حداقل دارای دو عنصر می‌باشد که غیر نزولی یا نزولی اکید باشد. اگر زیر مجموعه نزولی باشد باید نزولی اکید باشد زیرا این run می‌تواند با جابجایی ساده عناصر از دو طرف که به وسط همگرا می‌شوند معکوس شود.
این الگوریتم اگر عناصر آن اکیدا نزولی باشد پایدار است. بعد از به دست آوردن یک run در آرایه داده شده، عملیات خود را روی آن انجام می‌دهد و بعد از آن کار خود را با run بعدی ادامه می‌دهد
یک run به طور طبیعی یک زیرآرایه است که مرتب شده‌است. runهای طبیعی در داده‌های واقعی می‌توانند در اندازه‌های مختلفی وجود داشته باشند. این الگوریتم به صورت بهینه نوع خاصی از مرتب‌سازی که به طول run بستگی دارد (به طور مثال اگر اندازه آن از مقدار خاصی کمتر باشد از مرتب‌سازی درجی استفاده می‌کند) بنابراین این مرنب‌سازی انطباقی نامیده می‌شود.
اندازه run با اندازه کوچکترین run مقایسه می‌شود. اندازه کوچکترین run که (minrun)نامیده می‌شود که به اندازه آرایه بستگی دارد. برای آرایه‌هایی که اندازه آن از ۶۴ کمتر باشد. اندازه (minrun) به اندازه خود آرایه می‌باشد و اساسا به مرتب‌سازی درجی تبدیل می‌گردد. برای آرایه‌های بزرگتر اندازه (minrun) بین بازه ۳۲تا ۶۵ انتخاب می‌شود. الگوریتم نهایی برای انتخاب (minrun) شش بیت قابل توجه اندازه آرایه را در نظر می‌گیرد. اگر هر کدام از بیت‌های باقی‌مانده یک بودند یک اضافه می‌کندو از آن به‌عنوان (minrun)استفاده می‌کند. این روش برای همه آرایه‌های که سایز آنها از ۶۴ کمتر است و شامل یک هستند درست عمل می‌کند.
مرتب‌سازی درجی
هنگامی که یک آرایه به صورت رندم باشد، با احتمال زیادی یک run طبیعی تعداد عناصر کمتری از minrun دارد. دراین موارد تعداد مناسبی از عناصر در نظرگرفته می‌شوند و از مرتب‌سازی درجی برای مرتب کردن آن‌ها استفاده می‌شود. سپس اندازه آن افزایش می‌یابد تا به اندازه minrun بشود.
مرتب‌سازی ادغامی
در این قسمت minrunها در پشته(stack) ذخیره می‌شوند. اگر X
Y + Z
Y> Z
این دو قانون باعث می‌شود که طول runها نزدیک به هم نگه داشته شوند و بازدهی الگوریتم بالاتر باشد.
رویه ادغام‌کردن
حافظه موقت به اندازه آرایه کوچکتر ایجاد می‌شود.
ادغام کردن دو run همسایه به کمک یک حافظه کمکی انجام می‌شود. اندازه این حافظه به اندازه run کوچکتر می‌باشد. الگوریتم آرایه کوچکتر را در حافظه کپی می‌کند و سپس برای ذخیره run نهایی از حافظه اصلی و حافظه run بزرگتر استفاده می‌کند.
کارایی الگوریتم
طبق نظریه اطلاعات هیچ الگوریتم مرتب‌سازی مقایسه‌ای نمی‌تواند کارایی بهتر از در حالت میانگین داشته باشد. در داده‌های واقعی الگوریتم تیم معمولا با تعداد مقایسه‌های کمتر از مرتب‌سازی را انجام می‌دهد زیرا از این مزیت که زیر مجموعه‌ای از داده‌ها مرتب هستند.
در مواردی که هیچ زیر مجموعه‌ای از داده‌ها مرتب‌شده نیستند الگوریتم نمی‌تواند از این مزیت استفاده کند و با کارایی کار می‌کند.
در جدول زیر کارایی الگوریتم با دیگر الگوریتم‌های مقایسه‌ای مقایسه شده است.
مرتب‌سازی تیم
مرتب‌سازی ادغامی
مرتب‌سازی سریع
مرتب‌سازی درجی
مرتب‌سازی ادغامی
بهترین حالت
حالت متوسط
بدترین حالت
در جدول زیر انواع مختلف الگوریتم‌ها بر اساس پیچیدگی مقایسه شده‌اند.
مرتب‌سازی تیم
مرتب‌سازی ادغامی
مرتب‌سازی سریع
مرتب‌سازی درجی
مرتب‌سازی انتخابی
پیچیدگی حافظه
n
n
log n
1
1