بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی آنلاین 20 Quera

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسأله‌ی انتخابات

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
مرتب‌سازی ادغامی - الگوریتمستان
الگوریتمستان
8214.305.00
  »  

       

آشنایی با روش مرتب‌سازی ادغامی با قطعه کدهایی به زبان برنامه‌نویسی ++C

http://www.aachp.ir آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «مرتب سازی ادغام» دی ماه 1385 از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان) منتشر شده بود.


روش مرتب‌سازی ادغامی (Merge Sort) یک روش مرتب‌سازی مبتنی بر مقایسه‌ی عناصر با استفاده از روش تقسیم و غلبه است. این روش از مراحل بازگشتی زیر تشکیل یافته است:

    1- آرایه را به دو زیرآرایه با اندازه‌ی تقریبا یکسان تقسیم کن.

    2- دو زیرآرایه را به روش مرتب‌سازی ادغامی مرتب کن.

    3- دو زیرآرایه‌ی مرتب‌شده را ادغام کن.

      

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

      

پیاده‌سازی مرتب‌سازی ادغامی

  [بازگشت به فهرست]

بر اساس توضیحات فوق قطعه کد زیر به زبان برنامه‌نویسی ++C الگوریتم مرتب‌سازی ادغامی را پیاده‌سازی می‌کند:

      

void merge_sort(int arr[], int low, int high){
  if(low >= high)
    return;
  int mid = (low + high) / 2;
  merge_sort(arr, low, mid);
  merge_sort(arr, mid + 1, high);
  merge(arr, low, mid, high);
}

  

    این قطعه کد بازه‌های low تا mid و mid + 1 تا high را به صورت بازگشتی مرتب کرده و سپس توسط تابع merge ادغام می‌کند. به این ترتیب آرایه‌ی arr از بازه‌ی low تا high مرتب می‌شود.

    تابع merge پیاده‌سازی‌های مختلفی دارد. یک روش ساده آن است که ادغام دو زیرآرایه در یک آرایه‌ی کمکی به طول مجموع طول‌های این دو زیرآرایه صورت بگیرد. در این حالت این مرتب‌سازی یک مرتب‌سازی درجا نخواهد بود. چرا که متناسب با طول آرایه نیاز به فضای اضافی جهت مرتب‌سازی وجود دارد.

    قطعه کد زیر یک پیاده‌سازی درجا برای تابع merge است:

      

void merge(int arr[], int low, int mid, int high){
  int i, j, k, t;
  j = low;
  for(i = mid + 1 ; i <= high ; i++){
    while(arr[j] <= arr[i] && j < i)
      j++;
    if(j == i)
      break;
    t = arr[i];
10     for(k = i ; k > j ; k --)
11       arr[k] = arr[k - 1];
12     arr[j] = t;
13   }
14 }

  

    این تابع محل مناسب عناصر زیرآرایه‌ی سمت راست را در زیرآرایه‌ی سمت چپ پیدا کرده و در آن درج می‌کند. با توجه به این که عناصر دو زیرآرایه‌ی مرتب هستند، ادغام آنها پیچیده‌گی کمتری خواهد داشت.

    به عنوان مثال اگر هدف ادغام کردن زیرآرایه‌های زیر باشد:

      

1 3 6 9    /    2 4 5 8

  

    ترتیب چینش عناصر پس از اتمام هر تکرار حلقه‌ی بیرونی قطعه کد فوق، به این ترتیب خواهد بود:


1)    1 3 6 9    /    2 4 5 8        1 2 3 6 9    /    4 5 8

2)    1 2 3 6 9    /    4 5 8        1 2 3 4 6 9    /    5 8

3)    1 2 3 4 6 9    /    5 8        1 2 3 4 5 6 9    /    8

4)    1 2 3 4 5 6 9    /    8    →    1 2 3 4 5 6 8 9    /  

  

پیچیده‌گی زمانی مرتب‌سازی ادغامی

  [بازگشت به فهرست]

تعداد عناصر آرایه را $n$ و تعداد مقایسه‌های مورد نیاز جهت مرتب‌سازی این عناصر را $T(n)$ در نظر می‌گیریم.

    بر اساس تعریف بازگشتی این الگوریتم، مرتب کردن $n$ عنصر نیاز به مرتب شدن دو زیر آرایه تقریبا $\frac{n}{2}$ عنصری دارد. پس از این مرحله، این دو زیرآرایه توسط تابع merge ادغام می‌شوند.

     جهت ادغام دو زیرآرایه با قطعه کد فوق - که در مجموع $n$ عنصر دارند - حداکثر $n$ مقایسه اتفاق خواهد افتاد. پس می‌توان نوشت:

      

\[T(n) = 2  T(\frac{n}{2}) + n \]

  

    حل این رابطه‌ی بازگشتی نشان از مرتبه‌ی اجرای $ \theta(n log n) $ دارد. اما درجا بودن کد باعث می‌شود در بدترین شرایط مرتبه‌ی جابجایی‌ها $ \theta (n^2) $ باشد (چرا؟). پیاده‌سازی غیردرجا این کمک را می‌کند که بتوان با $ \theta (n) $ جابجایی ادغام را انجام داد.

  

حافظه‌ی مصرفی مرتب‌سازی ادغامی

  [بازگشت به فهرست]

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

      

ویژگی‌های مرتب‌سازی ادغامی

  [بازگشت به فهرست]

مرتب‌سازی ادغامی ویژگی‌های زیر را دارد:

    1- پیچیده‌گی زمانی اجرای الگوریتم در تمامی حالات $\theta (n log n) $ است؛ چرا که این الگوریتم تحت هر شرایطی آرایه را به دو قسمت کرده و مرتب‌سازی را انجام می‌دهد.

    2- پیچیده‌گی حافظه‌ی مصرفی بستگی به روش پیاده‌سازی مرحله‌ی ادغام دارد که تا $ O(n) $ افزایش می‌یابد. پیاده‌سازی درجای این الگوریتم حافظه‌ی مصرفی مرتبه‌ی $ \theta (1) $ دارد؛ اما اجرای آن در بدترین حالت زمان‌بَر است.

    3- الگوربتم مرتب‌سازی ادغامی با پیاده‌سازی فوق یک روش پایدار است. چنین الگوریتمی ترتیب عناصر با مقدار یکسان را پس از مرتب‌سازی حفظ می‌کند.


این نوشته آخرین بار در تاریخ چهارشنبه، ۲ اردیبهشت ماه ۱۳۹۴ مورد بازنویسی نگارشی قرار گرفته است.

این نوشته آخرین بار در تاریخ مورد بازنویسی علمی قرار گرفته است.
نوشته‌های مرتبط
        ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
        آشنایی با روش مرتب‌سازی هرمی (Heap Sort)
        بررسی الگوریتم‌های محاسبه‌ی دنباله‌ی اعداد فیبوناچی و کارایی آنها
        آشنایی با روش مرتب‌سازی سریع، همراه با قطعه کدهای نمونه به زبان برنامه‌نویسی ++C
        بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه‌ی آن با روش تقسیم و حل و روش برنامه‌نویسی پویا
        آشنایی با دنباله‌ی عددی کاتالان، کاربردها و روش پیاده‌سازی آن به زبان برنامه‌نویسی ++C
        آشنایی با الگوریتم استراسن برای محاسبه‌‌ی حاصلضرب ماتریس‌ها
        آشنایی با روش مرتب‌سازی درجی، همراه با قطعه کد به زبان برنامه‌نویسی ++C
        بررسی روش‌های بسط لاپلاس، گاوس، فرمول تحویل و ساروس، برای محاسبه‌ی دترمینان ماتریس مربعی و پیچیده‌گی زمانی آنها
        بررسی روش‌های مختلف محاسبه‌ی ضرایب دوجمله‌ای نیوتن یا ترکیب دو عدد با قطعه کد به زبان برنامه‌نویسی ++C
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» ali

چهارشنبه، ۲۳ فروردین ماه ۱۳۹۶، ساعت ۲۰:۴۴
very goooooood06

» محمد

شنبه، ۱۳ دی ماه ۱۳۹۳، ساعت ۲۱:۳۵
مرسییییییییییییییییییی

» فرزاد

پنجشنبه، ۲۱ آذر ماه ۱۳۹۲، ساعت ۲۲:۰۴
داداش انگار وقتی اومدی درجا کنی اردرش رو حواست نبوده، خراب کردی. اون تیکه که شیفت میدی می تونه اردر رو بکنه n^2 مثلا وقتی تیکه دوم کلا کوچکتر از تیکه ی اول باشه.


جمعه، ۲۵ مهر ماه ۱۳۹۳، ساعت ۱۵:۴۵
مسعود:
درست می‌گید فرزاد خان. این مساله به خاطر درجا بودن کد الگوریتم ادغامی هست که اینجا استفاده شده و برای هر درجی در بدترین شرایط ممکنه لازم باشه کل قسمت اول جابجا بشه.
چند خط توضیح بیشتر به مطلب اضافه کردم که این ابهام برطرف شه.

» رضا رضائی

دوشنبه، ۶ آبان ماه ۱۳۹۲، ساعت ۱۹:۱۴
سلام تشکر از سایت خوبتون عالی بود کارم راه افتاد تشکر

» اسماعیل

سه‌شنبه، ۱۰ اردیبهشت ماه ۱۳۹۲، ساعت ۱۴:۴۳
n بار تشکر، خیلی کمکم کردین

» میلاد

سه‌شنبه، ۶ فروردین ماه ۱۳۹۲، ساعت ۱۱:۵۸
واقعا یه سایت الگوریتمی کامل دارید، به نظر من تو ایران تکه12

» آوات دانشجوی پیام نور

پنجشنبه، ۱۷ اسفند ماه ۱۳۹۱، ساعت ۲۳:۴۹
از راهنمایی هاتون برای دانشجویان و علاقه مندان به الگوریتم سپاسگزارم
در کتاب پیام نور تحلیل و طراحی الگوریتم صفحه ی 93 این الگوریتم به روش بازگشتی آمده که البته در تابع merge با الگوریتم ارائه شده شما متفاوت است بنده منطق و طرز کار الگوریتم و برنامه را خوب میدانم اما وقتی آرایه ی نامرتبی از اعداد را در نظر میگیرم و خط های برنامه را قدم به قدم  را با قلم و کاغذ اجرا میکنم هر چقدر سعی کردم متوجه نشدم برنامه چگونه این کار را انجام میده البته برای اکثر توابع بازگشتی که بصورت برنامه نوشته میشند همین مشکل را دارم یعنی وقتی خطوط برنامه را روی مثالی دنبال میکنم متوجه کار برنامه نمیشم اگه بشه این برنامه را برای آرایه ای مثلا بصورت [12  8  4  10  15  8  6  2  17  11 ] قدم به قدم با خطوط برنامه توضیح بدهید ممنون میشم.  

» samane

یکشنبه، ۲۶ آذر ماه ۱۳۹۱، ساعت ۱۲:۰۹
سلام من تو حل ابن مسله موندم کسی میتونه حلش کنه بهم بده ؟ خیلی واسم حیاتیه . تورو خدا یکی کمک کنه
یافتن بزرگترین و کوچکترین عنصر آرایه به روش تقسیم و غلبه



» fatemeh

سه‌شنبه، ۲۶ اردیبهشت ماه ۱۳۹۱، ساعت ۱۷:۵۱
خیلی عالی بود

» هیوا

جمعه، ۱ اردیبهشت ماه ۱۳۹۱، ساعت ۰۲:۱۲
خسته نباشید
میشه لطفا این الگوریتم رو به صورت درجا که حافظه کمتری مصرف میکنه پیاده کنید

» امید

دوشنبه، ۱۴ فروردین ماه ۱۳۹۱، ساعت ۰۹:۲۴
با سلام ممنون از سایت مفیدتون خیلی سودمنده

من از مدیر یا برنامه نویس سایت می خوام اگر ممکنه همین کد مرتب سازی ادغامی رو با زبان php پیاده سازی کنید من هر کاری می کنم چاپ نمی کنه ممنون میشم با ایمیل بهم جواب بدین

طی همین 1-2 روز

» شاهین

دوشنبه، ۲۴ بهمن ماه ۱۳۹۰، ساعت ۱۸:۱۷
لطفا بگویید چگونه می توان این را اجرا کرد

» مسعود

جمعه، ۲۵ آذر ماه ۱۳۹۰، ساعت ۱۳:۰۳
<span style="color:#FF5555">ممنون از لطف تمامی دوستان که با حرفاتون دلگرمم می‌کنید.

فرزاد عزیز
تابع merge بالا با حداکثر n مقایسه دو آرایه رو ادغام می‌کنه. روش‌های دیگه‌ای برای ادغام وجود دارن که با حداکثر n - 1 مقایسه عمل ادغام رو انجام می‌دن. اگه دقت کنید داخل پرانتز عبارت "چرا؟" رو نوشتم که یعنی باید در این مورد توجه بشه. اینطور نیست که حتما حداکثر n مقایسه لازم داریم. قطعه کد بالا رو هم با کمی تغییر جزئی می‌شه تبدیل به حالتی کرد که حداکثر n - 1 مقایسه بین عناصر لازم داشته باشه.
یادآوری  آخر اینکه در حالت کلی وجود یا عدم وجود منهای یک در رابطه بازگشتی، تاثیری روی مرتبه اجرایی الگوریتم نداره.</span>

» فرزاد

جمعه، ۲۵ آذر ماه ۱۳۹۰، ساعت ۰۰:۳۲
سلام
اول خسته نباشید، واقعا ای ول داره کاری که انجام میدید. ممنون
سئوال من راجع به پیچیدگی زمانی این الگوریتم است. هم استاد من و هم کتابی که مطالعه می‌کنم پیچیدگی زمانی این الگوریتم را
T(n)=2T(n/2)+n-1  گفته‌اند که دقیقا مانند پیچیدگی زمانی مرتب سازی سریع است. بنظر من دلیلی برای وجود منفی یک وجود ندارد و من فکر میکنم پیچیدگی زمانی که شما بیان کردید درست است. فقط دچار شک شده‌ام، اگر امکان دارد خیال مرا از تالیف خود راحت کنید.
متشکرم

» elmira

شنبه، ۵ آذر ماه ۱۳۹۰، ساعت ۱۵:۰۳
عالیه خیلی منون 0114

» ثریا

دوشنبه، ۱۸ مهر ماه ۱۳۹۰، ساعت ۱۳:۲۴
سلام...خسته نباشید.... من دو تا سوال از برنامه نویسی داشتم ..... ما برنامه های الگوریتمی رو کار میکنیم  و من تازه کارم و تو این سوالا موندم لطفا هرچه زودتر کمکم کنید....ممنون ......برنامه ای میخوام که عددی را خوانده ارقام ان را یکی یکی چاپ کند.....و سوال دومم اینه که الگوریتم برنامه ای را بنویسید که مشخص کند یک عدد چند رقم دارد با توجه به این که ممکنه عدد منفی باشه

» خورشید

شنبه، ۱۶ مهر ماه ۱۳۹۰، ساعت ۱۹:۰۰
سلام خیلی عالی بود
من این ترم طراحی الگوریتم دارم خیلی کمکم کرد.
1 2 نیا ممنون01

» ملیحه

دوشنبه، ۴ مهر ماه ۱۳۹۰، ساعت ۰۸:۵۱
بسیار عالی بود .به من که خیلی کمک کردین . بی نهایت ممنونم12