تبلیغات


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

اشتراک گذاری
Share on FacebookTweet about this on TwitterShare on Google+Share on LinkedInPin on PinterestPrint this pageEmail this to someone

 

در این مطلب می خواهیم به شما آموزش بدهیم که چگونه برای بهینه سازی الگوریتم 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


تبلیغات:

۱۰ دیدگاه

  • سلام، مرجسورت اصلی پیچیدگی زمانی و فضایی n logn داره. میخواستم بپرسم ایا میشه تابع مرج رو جوری تغییر داد که نیازی به ارایه کمکی نداشته باشه؟ (مرتبه زمانی یا تغییر نکنه یا خیلی کم تغییر کنه)من کلی اینترنت و گشتم عملا ۳ تا راه حل رسیدم:
    ۱. راه اول همینی که تو این پست توضیح دادین هست که بازم حافظه کمکی داریم اما کمتر از قبل اونم به خاطر اینکه سطح آستانه برای تقسیمات در نظر گرفتیم که پیچیدگی فضایی کم میشه. از طرفی مرتبه زمانی به n^2 نزدیک میشه.
    ۲.استفاده از لیست پیوندیه که قطعا به خاطر عدم دسترسی مستقیم به گره ها باید پیمایش کنیم و مرتبه زمانی خیلی تغییر میکنه ولی خب چون با اشاره گر کار میکنیم مقدار حافظه کمکی کم میشه (اما تعداد فرق نمیکنه چون دقیقا برای هر خونه یه پوینتر لازم داریم).
    ۳. و اما راه آخر که درکش برای من خیلی سختهInplace MergeSort هست. تو کتاب هورویتز فصل ۷ این و توضیح داده (خیلی پیچیدس) که با (۱)o فضایی عمل مرج رو انجام میده. اگه امکانش هست این روش و یک توضیح مختصر بدین یا اینکه یک لینک که کمکم کنه.
    با سپاس فراوان.

    • حامد آهنگری

      سلام
      لازم است ابتدا نکاتی رو درباره In-place Merge-Sort بدونید:
      نکته اول:
      In-place Merge-Sort یه الگوریتم پیچیده ست و در اکثر رفرنس های آموزش الگوریتم (چه چاپی و چه آنلاین)، به عنوان موضوع تحقیق و تمرین به عهده خوانده مشتاق گذاشته شده.
      نکته دوم:
      با توجه به رشد صنعت حافظه ها و در اختیار بودن حافظه های با ظرفیت بیشتر و قیمت کمتر، و همچنین با توجه به وجود الگوریتم های بهینه تری مثل Quick Sort و Optimized Merge-Sort، پیاده سازی In-place Merge-Sort منفعت و ضرورت چندانی نداره (از لحاظ زمانی این الگوریتم از Quick Sort و نسخه بهینه Merge-Sort کندتر هستش)

      در نهایت اگر بر یادگیری In-place Merge-Sort یا استفاده آموزشی اون اصرار داری، لینک های زیر بهت کمک می کنن:
      توضیح مختصر الگوریتم در استک اورفلو : https://stackoverflow.com/a/15657134
      شرح در فصل ۱۳ این کتاب : Elementary Algorithms by Larry LIU Xinyu
      سورس کد به زبان سی : https://github.com/liuxinyu95/AlgoXY/blob/algoxy/sorting/merge-sort/src/mergesort.c

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

    • حامد آهنگری

      سلام
      تنها کافی است تابع mergeSort را تغییر دهید.
      گام های تغییر برای تابع mergeSort به این شکل خواهد بود که :
      ۱) در صورتی که اندازه محدوده فعلی آرایه (در هر بار فراخوانی بازگشتی)، بزرگتر مساوی ۳ است، آن را به سه قسمت تقسیم کنید و سه بار تابع mergeSort را با آن سه قسمت فراخوانی کنید.
      ۲) پس از فراخوانی های بازگشتی، نوبت به merge می رسد. این تابع باید دوبار پشت سر هم فراخوانی شود. بار اول، بخش اول و دوم از سه بخش ایجاد شده در مرحله قبل را به آن می دهیم و برای بار دوم هم، دو بخش قبلی (که حالا ادغام و مرتب شده اند) را به عنوان یک بخش و بخش سوم را هم به عنوان یک بخش دیگر از آرایه به تابع merge می دهیم تا در نهایت عمل ادغام روی هر سه بخش انجام شود.

      توجه: گام دوم را به شکل دیگری هم می توان نوشت که برنامه مرتب سازی، حافظه کمتری مصرف کند. اما در این صورت تابع merge هم باید تغییر کند و همزمان بتواند سه تکه آرایه را بگیرد و در هم ادغام و مرتب کند (اما روشی که من برای شما توضیح دادم بدون نیاز به تغییر تابع merge است و تغییرات مذکور mergeSort کافی است).

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

    • خواهش می کنم
      در کل وقتی صحبت از درجه زمانی می شود، منظور حالت میانگین است مگر این که گفته بشود «در بدترین حالت…». در مورد عناصری که قرار است مرتب بشود بدون در نظرگرفتن وضعیت قبلی، اگر بخواهیم بر اساس تعداد الگوریتم مناسب انتخاب کنیم، برای آرایه ای حداکتر تا بیست عنصر 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

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

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