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

تحلیل عملکرد و پیاده‌سازی با زبان‌های ++C و Python
جستجو:  

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

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

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

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

  

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

  

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

  [برگرد بالا]

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

  

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);

}

  

def merge_sort(arr, low, high):

  if low >= high:

    return

  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];

    for(k = i ; k > j ; k --)

      arr[k] = arr[k - 1];

    arr[j] = t;

  }

}

  

def merge(arr, low, mid, high):

    j = low

    for i in range(mid + 1, high + 1):

        while arr[j] <= arr[i] and j < i:

            j +=1

        if j == i:

            break

        t = arr[i]

        for k in range(i, j, -1):

            arr[k] = arr[k - 1]

        arr[j] = t

  

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

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

  

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- الگوربتم مرتب‌سازی ادغامی با پیاده‌سازی فوق یک روش پایدار است. چنین الگوریتمی ترتیب عناصر با مقدار یکسان را پس از مرتب‌سازی حفظ می‌کند.


تا کنون ۱۰۷ امتیاز ثبت شده
نوشته لایک نداشت؟
 
به اشتراک گذاری نوشته

algs.ir/splyuq1

اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram


نام: *  

پست الکترونیک (محرمانه):

پیام: *  

01 02 06 07 08 09 10 11 12 13 14

• حسین
۲۵ آذر ۱۳۸۵، ساعت ۱۲:۵۱

زکات دانش آموختن آن است .

امیدوارم همچنان به کارتان ادامه دهید

و من محمد حسین صادقی را به عنوان یکی از دوستان خود بپذیرید

البته دوست مبتدی .

خدا نگهدار شما .

• saeidssa
۲۷ آذر ۱۳۸۵، ساعت ۱۳:۱۶

خیلی خیلی استفاده کردیم

• saeid
۳۰ آذر ۱۳۸۵، ساعت ۰۴:۵۶

آقا خیای خیلی ممنون

با تشکــــــــــــر

• قناری
۲ دی ۱۳۸۵، ساعت ۲۳:۱۷

یکی از بچه ها اگه کدنویسی ضرب ماتریسهارو داره به من بده خیلی خیلی حیاطیی منطظرم ها

• لبخند ریاضی
۲ دی ۱۳۸۵، ساعت ۲۳:۲۴

سلام

چه خبر؟ کم پیدا شدی؟

منتظر باقی مطالب آنالیز عددیت هستم.

• majid
۹ خرداد ۱۳۸۶، ساعت ۲۳:۱۷

با سلام

اینجانب برنامه مرتب سازی با ادغام را از سایت شما گرفته ام و آن را اجرا کرده ام

برنامه درست کار میکند اما نحوه کارکرد آن بخصوص تابع دوم را نفهمیدم

اگر امکان دارد توضیحات بیشتری برای اینجانب در مورد این تابع بفرستید

هر چه زودتر بهتر

با تشکر

مسعود اقدسی فام
۱۲ خرداد ۱۳۸۶، ساعت ۱۱:۱۴

مجیدجان شما با کدوم قسمت تابع رو متوجه نشدید؟

اولی برای مرتب سازی و دومی برای ادغام به کار می ره.

دقیقا بگید کجا رو خوب متوجه نشدید.

• ندا
۷ آبان ۱۳۸۶، ساعت ۱۹:۲۴

سلا م

خیلی ممنون

من میخواستم ببینم میتونین این برنامه رو با استفاده از کلاس ها بنویسین؟

لطف میکنین

• جواد
۱۸ دی ۱۳۸۶، ساعت ۱۶:۰۰

اگه می شه درباره الگوریتم مرتب سازی exchange sort (مرتب سازی مبادله ای ) در زبان c کمکم کنید

• سعید کاظمی
۱۹ فروردین ۱۳۸۸، ساعت ۱۱:۳۹

مطالب بسیار مورد استفاده قرار گرفت خداوند کمکتون کنه

• ملیحه
۴ مهر ۱۳۹۰، ساعت ۰۸:۵۱

بسیار عالی بود .به من که خیلی کمک کردین . بی نهایت ممنونم12

• خورشید
۱۶ مهر ۱۳۹۰، ساعت ۱۹:۰۰

سلام خیلی عالی بود

من این ترم طراحی الگوریتم دارم خیلی کمکم کرد.

1 2 نیا ممنون01

• ثریا
۱۸ مهر ۱۳۹۰، ساعت ۱۳:۲۴

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

• elmira
۵ آذر ۱۳۹۰، ساعت ۱۵:۰۳

عالیه خیلی منون 0114

• فرزاد
۲۵ آذر ۱۳۹۰، ساعت ۰۰:۳۲

سلام

اول خسته نباشید، واقعا ای ول داره کاری که انجام میدید. ممنون

سئوال من راجع به پیچیدگی زمانی این الگوریتم است. هم استاد من و هم کتابی که مطالعه می‌کنم پیچیدگی زمانی این الگوریتم را

T(n)=2T(n/2)+n-1  گفته‌اند که دقیقا مانند پیچیدگی زمانی مرتب سازی سریع است. بنظر من دلیلی برای وجود منفی یک وجود ندارد و من فکر میکنم پیچیدگی زمانی که شما بیان کردید درست است. فقط دچار شک شده‌ام، اگر امکان دارد خیال مرا از تالیف خود راحت کنید.

متشکرم

مسعود اقدسی فام
۲۵ آذر ۱۳۹۰، ساعت ۱۳:۰۳

ممنون از لطف تمامی دوستان که با حرفاتون دلگرمم می‌کنید.

فرزاد عزیز

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

یادآوری  آخر اینکه در حالت کلی وجود یا عدم وجود منهای یک در رابطه بازگشتی، تاثیری روی مرتبه اجرایی الگوریتم نداره.

• شاهین
۲۴ بهمن ۱۳۹۰، ساعت ۱۸:۱۷

لطفا بگویید چگونه می توان این را اجرا کرد

• امید
۱۴ فروردین ۱۳۹۱، ساعت ۰۹:۲۴

با سلام ممنون از سایت مفیدتون خیلی سودمنده

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

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

• هیوا
۱ اردیبهشت ۱۳۹۱، ساعت ۰۲:۱۲

خسته نباشید

میشه لطفا این الگوریتم رو به صورت درجا که حافظه کمتری مصرف میکنه پیاده کنید

• fatemeh
۲۶ اردیبهشت ۱۳۹۱، ساعت ۱۷:۵۱

خیلی عالی بود

• samane
۲۶ آذر ۱۳۹۱، ساعت ۱۲:۰۹

سلام من تو حل ابن مسله موندم کسی میتونه حلش کنه بهم بده ؟ خیلی واسم حیاتیه . تورو خدا یکی کمک کنه

یافتن بزرگترین و کوچکترین عنصر آرایه به روش تقسیم و غلبه

• آوات دانشجوی پیام نور
۱۷ اسفند ۱۳۹۱، ساعت ۲۳:۴۹

از راهنمایی هاتون برای دانشجویان و علاقه مندان به الگوریتم سپاسگزارم

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

• میلاد
۶ فروردین ۱۳۹۲، ساعت ۱۱:۵۸

واقعا یه سایت الگوریتمی کامل دارید، به نظر من تو ایران تکه12

• اسماعیل
۱۰ اردیبهشت ۱۳۹۲، ساعت ۱۴:۴۳

n بار تشکر، خیلی کمکم کردین

• رضا رضائی
۶ آبان ۱۳۹۲، ساعت ۱۹:۱۴

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

• فرزاد
۲۱ آذر ۱۳۹۲، ساعت ۲۲:۰۴

داداش انگار وقتی اومدی درجا کنی اردرش رو حواست نبوده، خراب کردی. اون تیکه که شیفت میدی می تونه اردر رو بکنه n^2 مثلا وقتی تیکه دوم کلا کوچکتر از تیکه ی اول باشه.

۲۵ مهر ۱۳۹۳، ساعت ۱۵:۴۵
• مسعود اقدسی فام

درست می‌گید فرزاد خان. این مساله به خاطر درجا بودن کد الگوریتم ادغامی هست که اینجا استفاده شده و برای هر درجی در بدترین شرایط ممکنه لازم باشه کل قسمت اول جابجا بشه.

چند خط توضیح بیشتر به مطلب اضافه کردم که این ابهام برطرف شه.

• محمد
۱۳ دی ۱۳۹۳، ساعت ۲۱:۳۵

مرسییییییییییییییییییی

• ali
۲۳ فروردین ۱۳۹۶، ساعت ۲۰:۴۴

very goooooood06

• امیر
۲۹ دی ۱۳۹۶، ساعت ۰۰:۴۴

چطوری میشه تعداد مقایسه هارو هم نشون داد ؟؟

• اسرا
۳۰ بهمن ۱۳۹۷، ساعت ۲۱:۱۶

0404040413080905050505 عاشق سایت واین ایموجی ها هستم

• مهدی
۱۸ اردیبهشت ۱۳۹۸، ساعت ۰۳:۴۶

'12 عالی بود 12

• کاربر
۲۰ آبان ۱۳۹۹، ساعت ۱۶:۴۳

توضیحات کمی نامفهوم بود کاش در یک مثال کد میزدید

• ....
۲۰ آبان ۱۳۹۹، ساعت ۱۶:۴۴

ممنون 01