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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
مرتب‌سازی تیم
کلاس الگوریتم مرتب‌سازی
ساختمان داده‌ها آرایه
عملکرد بدترین حالت O(n\log n)[۱]
عملکرد بهترین حالت O(n)
عملکرد حالت متوسط O(n\log n)
پیچیدگی فضایی بدترین حالت O(n)
Timsort algorithm searches for such ordered sequences, minruns, to perform its sort

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

الگوریتم چگونه کار می‌کند؟[ویرایش]

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

مرتب‌سازی درجی[ویرایش]

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

مرتب‌سازی ادغامی[ویرایش]

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

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

  1. X> Y + Z
  2. Y> Z

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

رویهٔ ادغام‌کردن[ویرایش]

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

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

کارایی الگوریتم[ویرایش]

طبق نظریه اطلاعات هیچ الگوریتم مرتب‌سازی مقایسه‌ای نمی‌تواند کارایی بهتر از \Theta(n \log n) در حالت میانگین داشته باشد. در داده‌های واقعی الگوریتم تیم معمولاً با تعداد مقایسه‌های کمتر از \Theta(n \log n) مرتب‌سازی را انجام می‌دهد زیرا از این مزیت که زیر مجموعه‌ای از داده‌ها مرتب هستند .[۴] در مواردی که هیچ زیر مجموعه‌ای از داده‌ها مرتب‌شده نیستند الگوریتم نمی‌تواند از این مزیت استفاده کند و با کارایی \Theta(n \log n) کار می‌کند.[۳] در جدول زیر کارایی الگوریتم با دیگر الگوریتم‌های مقایسه‌ای مقایسه شده است.

Timsort Merge Sort Quick Sort Insertion Sort Selection Sort
Best Case \Omega(n) \Omega(n log n) \Omega(n log n) \Omega(n) \Omega(n^2)
Average Case \Theta(n log n) \Theta(n log n) \Theta(n log n) \Theta(n^2) \Theta(n^2)
Worst Case O(n log n) O(n log n) O(n^2) O(n^2) O(n^2)

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

منابع[ویرایش]

  1. Peters, Tim. "[Python-Dev] Sorting". Python Developers Mailinglist. Retrieved 24 Feb 2011. "[Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g. , if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g. , refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N-1 compares is best)." 
  2. Peters, Tim. "[Python-Dev] Sorting". Python Developers Mailinglist. Retrieved 24 Feb 2011. "[Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g. , if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g. , refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N-1 compares is best)." 
  3. ۳٫۰ ۳٫۱ ۳٫۲ timsort, python. "python_timsort". 
  4. Martelli, Alex (2006). Python in a Nutshell (In a Nutshell (O'Reilly)). O'Reilly Media, Inc. p. 57. ISBN 0596100469. 

پیوند به بیرون[ویرایش]