تبلیغات


quick_sort_time

الگوریتم های مرتب سازی : بهینه سازی Quick-sort با میانه سه

 

در این مطلب از وب سایت اوپن مایند می خواهیم کمی بیشتر از Quick-sort صحبت کنیم. اگر از Quick-sort چیزی نمی دانید ابتدا این مطلب را بخوانید.

 

در الگوریتم Quick-sort، بدترین حالت (با درجه زمانی (O(n^2 ) برای ما دردسرساز می شود و بهترین حالت (با درجه زمانی ((O(n*lg(n )، بهترین زمان اجرا را دارد! در شکل زیر بدترین حالت نشان داده شده است و آن به این صورت است که راست ترین عنصر به عنوان عنصر شاخص انتخاب می شود و همچنین آرایه از قبل به صورت صعودی مرتب شده است. به صورت کلی اگر عنصر شاخص چپ ترین یا راست ترین عنصر انتخاب شود و آرایه از قبل مرتب (چه صعودی چه نزولی) باشد، الگوریتم Quick-sort بدترین زمان اجرای خود را تقدیم شما خواهد کرد! البته منظور من Quick-sort به روش پیاده سازی استاندارد و متداول است.

quick_sort_time

 

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

این کار در میل کردن به بهترین حالت هم مفید است چرا که امکان دارد اندیس نهایی میانه ای که به عنوان شاخص انتخاب می شود، کمی (یا خیلی!) نزدیک به وسط آرایه باشد و همین موجب می شود در فراخوانی بعدی Quick-sort آرایه تقریباً به دو نیم تقسیم شود که این یعنی نزدیک شدن به بهترین حالت الگوریتم.

به سراغ کد برویم؛ با فرض این که  الگوریتم متداول Quicksort به چشمتان آشناست، بیشتر توضیحات داخل کد به صورت نام گذاری های واضح و کامنت گذاری ارائه شده است.

تابع  (...) GetMedian برای انتخاب عنصر میانه است.

و پیاده سازی تابع  (...)Partition

و اما تابع
(...)QuickSort_MedianOfThree
:

اگر در مشاهده کدها در این صفحه مشکلی داشتید، روی github (در اینجا) در اختیارتان هستند!


تبلیغات:

۴ نظر

  • سلام میشه خواهش کنم سورس کد زمان اجرای برنامه رو برای اعداد تصادفی بزارین؟

  • البته اگر بخوایم صورت‌مساله رو دور بزنیم، باید بگم معمولاً بعد از ثبت رکورد جدید هست که نیاز به سورت کردن پیدا میشه. بهترین کار اینه که یک بار سورت کنیم و بعد از اون برای ثبت هر رکورد، اون رو با توجه به معیارهامون در محل مناسب از آرایه قرار بدیم و دوباره سورت نکنیم 😛

نظرتان را برای ما بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *