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

 

در این مطلب می خواهیم به شما آموزش بدهیم که چگونه برای بهینه سازی الگوریتم Merge-sort از Insertion-sort کمک بگیرید!

سوال: چطور می توان برای بهینه سازی الگوریتمی که ((O(nlg(n  است از الگوریتم دیگری که (O(n^2  است استفاده کرد؟
جواب: الگوریتم (اصلی) Merge-sort حافظه سربار زیادی دارد (استفاده از آرایه کمکی). و بازگشتی بودن الگوریتم آن هم کمی هزینه زمانی اضافه روی دست ما می گذارد! اما Insertion-sort بدون استفاده از حافظه های کمکی و فقط با ایجاد حلقه روی آرایه و مقایسه ها کار می کند. ولی به هر حال الگوریتم آن از درجه (O(n^2 است. پس بیایید هر کدام را برای تعدادی از ورودی های مختلف اجرا کنیم و ببینیم کدام مزیت و کدام عیب برای چه تعداد ورودی برگ برنده میشوند؟!

زمان اجرا برای آرایه مرتب شده:

algo_table_2

زمان اجرا برای آرایه مرتب شده به صورت معکوس:

algo_table_3

 

زمان اجرا برای آرایه ای که ترتیب عتاصر آن به صورت تصادفی است:

algo_table_4

 

ما در مورد آرایه ای که قرار است مرتب کتیم نه خوش بین هستیم نه بدبین! پس به جدول سوم توجه می کنیم. می بینید که برای آرایه ای با ۱۰۰ عنصر که ترتیب آن ها به نسبت یکدیگر تصادفی است، Insertion-sort در زمان کمنری آرایه را مرتب می کند. در حقیقت درجه های زمانی، نمایش هزینه الگوریتم برای تعداد بسیار زیاد ورودی (میل به سوی بی شمار) هستند. اما این که Insertion-sort برای چه تعداد ورودی از Merge-sort سریعتر است به مشخصه های مختلفی بسنگی دارد؛ به طور مثال به نحوه پیاده سازی الگوریتم ها، حافظه کش پردازنده و توزیع نامرتبی عناصر. اما اندازه گیری ها ثابت کرده است که حداقل برای ۲۰ عنصر، Insertion-sort سریعتر عمل می کند. خبر خوب این است که در چند روز آینده آموزش اندازه گیری دقیق زمان اجرای یک تابع در قالب یک مطلب روی وبسایت می آید! (منتشر شد!)

خیلی خوب! امیدوارم قانع شده باشید! روش کار به این صورت است که در الگوریتم Merge-sort هنگامی که طول تکه های آرایه در هر فراخوانی کمتر از مقدار مشخصی شد به جای ریز ریز کردن دوباره آن تکه، از Insertion-sort بهره می گیریم و مرتب کردن آن بخش را به این الگوریتم می سپاریم. مقدار مشخص را شما و به نسبت طول آرایه ای که برای مرتب سازی به Merge-sort می فرستید مشخص می کنید.

برویم سراغ کد نویسی!

 

ابتدا الگوریتم Insertion-sort با کمی تغییر؛ تغییرات هم به این صورت که این الگوریتم فقط بخشی از آرایه را که محدوده آن با min و max مشخص شده را مرتب می کند.

 

سپس الگوریتم Merge-sort با کمی تغییر؛ تغییرات هم به این صورت که شرط خاتمه طوری نوشته می شود که وقتی اندازه تکه ای که در مرحله تقسیم و در آن عمق باید مرتب شود، به اندازه مشخصی که توضیح داده شد رسید، مرتب سازی آن به عهده Insertion-sort باشد.

در ضمن آن مقدار (طول) مشخص هم به الگوریتم فرستاده می شود.

 

و در آخر هم تابع main برای تست برنامه!

مثالی از خروجی برنامه:

result

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)

۸ دیدگاه

  • سلام خسته نباشید
    ببخشید من الگورتیم مرج سورت رو به روشی میخوام به صورت تقسیم غلبه به طوری که برای مرتب سازی از هیچ ارایه اضافه ای استفاده نکنه کمکم کنید خیلی ممنون

  • سلام
    ممنون از مطلب خوبتون.
    خب، حالا سوال اینجاست که اگه یه آرایه داشتیم که وضعیت اولیه‌ش معلوم نبود و نمیدونیم قبلاً سورت شده یا نه بهتره از کدوم الگوریتم استفاده بشه؟

    • خواهش می کنم
      در کل وقتی صحبت از درجه زمانی میشود، منظور حالت میانگین است مگر این که گفته بشود «در بدترین حالت…». در مورد عناصری که قرار است مرتب بشود بدون در نظرگرفتن وضعیت قبلی، اگر بخواهیم بر اساس تعداد الگوریتم مناسب انتخاب کنیم، برای آرایه ای حداکتر تا بیست عنصر Insertion-sort سریع تر است، اما برای اندازه های بیشتر از ۲۰، Quick-sort با روش پیاده سازی میانه سه، سریع ترین الگوریتم مرتب سازی با درجه زمانی غیر خطی است.
      در کتاب ساختمان های داده نوشته Horowitz and Sahni چاپ سال ۱۹۹۵ در صفحات ۴۴۰ و ۴۴۱ جدول و نموداری ارائه شد که زمان اجرای چند الگوریتم مرتب سازی را روی یک کامپیوتر IBM نشان می داد؛ در ویرایش های جدید هم همان جدول مقایسه در انتهای فصل هفت کتاب وجود دارد و منبع خوبی برای استدلال های من است.
      اما سریع ترین برای هر اندازه دلخواه کدام است؟
      جواب: ترکیب Insertion-sort برای اندازه مشخص و heap-sort برای عمق مشخص با Quick-sort with median-of-three که با نام Introsort شناخته می شود.
      Introsort در ویکی پدیا: http://en.wikipedia.org/wiki/Introsort

نظر خود را بنویسید.

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