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

الگوریتم مرتب‌سازی تیم ، ترکیبی از دو الگوریتم مرتب‌سازی است به نام‌های مرتب‌سازی ادغامی و مرتب‌سازی درجی. این طراحی بر روی بسیاری از انواع داده‌ها در جهان واقعی بسیار خوب عمل می‌کند. این الگوریتم اولین بار توسط تیم پیترز  در سال ۲۰۰۲ برای استفاده در پایتون بیان شد. الگوریتم برای پیدا کردن زیر مجموعه‌ای از داده‌ها که جستجو را بهینه‌تر کنند، طراحی شد. به‌وسیلهٔ مرتب‌سازی ادغامی زیر مجموعه مشخص می‌شود. این زیر مجموعه یک run نامیده می‌شود. از این runها به تعدادی پیدا می‌شود که معیارهای لازم برآورده شود. مرتب‌سازی تیم، مرتب‌سازی استاندارد پایتون از مدل ۲٫۳ است. هم‌اکنون در جاوا ۷ و همچنین در اندروید برای مرتب‌سازی آرایه‌ها از این مرتب‌سازی استفاده می‌شود.

 الگوریتم چگونه کار می‌کند؟ 
الگوریتم برای استفاده از این مزیت که داده‌ها به‌طور جزئی مرتب شده‌اند، طراحی شده‌است. جستجوی تیم، کار خود را با پیداکردن runها در داده ادامه می‌دهد. یک run یک زیرآرایه از آرایهٔ اصلی داده‌ها می‌باشد که حداقل دارای دو عنصر می‌باشد که غیر نزولی یا نزولی اکید باشد. اگر زیر مجموعه نزولی باشد باید نزولی اکید باشد زیرا این run می‌تواند با جابجایی ساده عناصر از دو طرف که به وسط همگرا می‌شوند، معکوس شود.

این الگوریتم اگر عناصر آن اکیداً نزولی باشد پایدار است. بعد از به دست آوردن یک run در آرایهٔ داده شده، عملیات خود را روی آن انجام می‌دهد و بعد از آن کار خود را با run بعدی ادامه می‌دهد.

یک run به‌طور طبیعی یک زیرآرایه است که مرتب شده‌است. runهای طبیعی در داده‌های واقعی می‌توانند در اندازه‌های مختلفی وجود داشته باشند. این الگوریتم به صورت بهینه نوع خاصی از مرتب‌سازی که به طول run بستگی دارد (به‌طور مثال اگر اندازهٔ آن از مقدار خاصی کمتر باشد از مرتب‌سازی درجی استفاده می‌کند) بنابراین این مرنب‌سازی انطباقی نامیده می‌شود. 
اندازهٔ run با اندازهٔ کوچکترین run مقایسه می‌شود. اندازهٔ کوچکترین run که «minrun» نامیده می‌شود که به اندازهٔ آرایه بستگی دارد. برای آرایه‌هایی که اندازهٔ آن از ۶۴ کمتر باشد، اندازهٔ minrun به اندازهٔ خود آرایه می‌باشد و اساساً به مرتب‌سازی درجی تبدیل می‌گردد. برای آرایه‌های بزرگتر اندازهٔ minrun بین بازهٔ ۳۲ تا ۶۵ انتخاب می‌شود. الگوریتم نهایی برای انتخاب minrun، شش بیت قابل توجه اندازهٔ آرایه را در نظر می‌گیرد. اگر هر کدام از بیت‌های باقی‌مانده یک بودند، یک اضافه می‌کند و از آن به‌عنوان minrun استفاده می‌کند. این روش برای همهٔ آرایه‌هایی که سایز آن‌ها از ۶۴ کمتر است و شامل یک هستند، درست عمل می‌کند.

 مرتب‌سازی درجی 
هنگامی که یک آرایه به صورت رندم باشد، با احتمال زیادی یک run طبیعی تعداد عناصر کمتری از minrun دارد. در این موارد تعداد مناسبی از عناصر در نظر گرفته می‌شوند و از مرتب‌سازی درجی برای مرتب کردن آن‌ها استفاده می‌شود. سپس اندازهٔ آن افزایش می‌یابد تا به اندازهٔ minrun بشود.

 مرتب‌سازی ادغامی 
280px|بندانگشتی|در این قسمت minrunها در پشته (stack) ذخیره می‌شوند. اگر X < Y + Z باشد X و Y در هم ادغام می‌شوند و سپس به پشته اضافه می‌شوند.

عملیات ادغام معمولاً روی دو run پیاپی انجام می‌شود. برای این کار سه run بالای پشته را که مرتب نشده‌اند را در نظر می‌گیرد. اگر طول این سه run را x، y، z در نظر بگیریم، الگوریتم طوری آن‌ها را ادغام می‌کند که دو شرط زیر برقرار شود.

<li>X > Y + Z
<li>Y > Z

این دو قانون باعث می‌شود که طول runها نزدیک به هم نگه داشته شوند و بازدهی الگوریتم بالاتر باشد.

 رویهٔ ادغام‌کردن 
280px|بندانگشتی|حافظه موقت به اندازهٔ آرایهٔ کوچکتر ایجاد می‌شود.

ادغام کردن دو run همسایه به کمک یک حافظهٔ کمکی انجام می‌شود. اندازهٔ این حافظه به اندازهٔ run کوچکتر می‌باشد. الگوریتم آرایهٔ کوچکتر را در حافظه کپی می‌کند و سپس برای ذخیرهٔ run نهایی از حافظهٔ اصلی و حافظهٔ run بزرگتر استفاده می‌کند.

 کارایی الگوریتم 
طبق نظریه اطلاعات هیچ الگوریتم مرتب‌سازی مقایسه‌ای نمی‌تواند کارایی بهتر از  در حالت میانگین داشته باشد. در داده‌های واقعی الگوریتم تیم معمولاً با تعداد مقایسه‌های کمتر از  مرتب‌سازی را انجام می‌دهد زیرا از این مزیت که زیر مجموعه‌ای از داده‌ها مرتب هستند.
در مواردی که هیچ زیر مجموعه‌ای از داده‌ها مرتب‌شده نیستند الگوریتم نمی‌تواند از این مزیت استفاده کند و با کارایی  کار می‌کند.
در جدول زیر کارایی الگوریتم با دیگر الگوریتم‌های مقایسه‌ای مقایسه شده‌است.

 مرتب‌سازی تیم مرتب‌سازی ادغامی مرتب‌سازی سریع مرتب‌سازی درجی مرتب‌سازی انتخابی بهترین حالت      حالت متوسط      بدترین حالت     

در جدول زیر انواع مختلف الگوریتم‌ها بر اساس پیچیدگی مقایسه شده‌اند.

 مرتب‌سازی تیم مرتب‌سازی ادغامی مرتب‌سازی سریع مرتب‌سازی درجی مرتب‌سازی انتخابی پیچیدگی حافظه n n log n 1 1

 منابع 

رده:الگوریتم‌های مرتب‌سازی
رده:مرتب‌سازی‌های پایدار
رده:مرتب‌سازی‌های سنجشی
رده:مقاله‌های ایجادشده توسط ایجادگر
رده:ویکی‌سازی رباتیک