quick_sort_time

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

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

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

quick_sort_time

 

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

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

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

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

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

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

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

 

برای مطالعه بیشتر می توانید به لینک های زیر مراجعه کنید.

StackOverFlow: median 3 quicksort implementation

Algorithms in C#: quick sort (part three)

Quick Sort Implementation with median-of-three partitioning and cutoff for small arrays

Algorithm of the Week: Quicksort – Three-way vs. Dual-pivot

Quicksort optimizations

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۴ دیدگاه

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

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

پاسخ دهید

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