آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «مرتب سازی ادغام»
دی ماه ۱۳۸۵
از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان)
منتشر شده بود.
روش مرتب‌سازی ادغامی (Merge Sort) یک روش مرتب‌سازی مبتنی بر مقایسه‌ی عناصر با استفاده از روش تقسیم و غلبه است. این روش از مراحل بازگشتی زیر تشکیل یافته است:
1- آرایه را به دو زیرآرایه با اندازه‌ی تقریبا یکسان تقسیم کن.
2- دو زیرآرایه را به روش مرتب‌سازی ادغامی مرتب کن.
3- دو زیرآرایه‌ی مرتب‌شده را ادغام کن.
پیاده‌سازی مرتب‌سازی ادغامی
[بازگشت به فهرست]
بر اساس توضیحات فوق قطعه کدهای زیر به زبان‌های برنامه‌نویسی ++C و Python الگوریتم مرتب‌سازی ادغامی را پیاده‌سازی می‌کنند.
| 1 | void merge_sort(int arr[], int low, int high){
|
| 2 | if(low >= high)
|
| 3 | return;
|
| 4 | int mid = (low + high) / 2;
|
| 5 | merge_sort(arr, low, mid);
|
| 6 | merge_sort(arr, mid + 1, high);
|
| 7 | merge(arr, low, mid, high);
|
| 8 | } |
| 1 | def merge_sort(arr, low, high):
|
| 2 | if low >= high:
|
| 3 | return
|
| 4 | mid = (low + high) / 2
|
| 5 | merge_sort(arr, low, mid)
|
| 6 | merge_sort(arr, mid + 1, high)
|
| 7 | merge(arr, low, mid, high) |
این قطعه کدها بازه‌های low تا mid و mid + 1 تا high را به صورت بازگشتی مرتب کرده و سپس توسط تابع merge ادغام می‌کنند. به این ترتیب آرایه‌ی arr از بازه‌ی low تا high مرتب می‌شود.
تابع merge پیاده‌سازی‌های مختلفی دارد. یک روش ساده آن است که ادغام دو زیرآرایه در یک آرایه‌ی کمکی به طول مجموع طول‌های این دو زیرآرایه صورت بگیرد. در این حالت این مرتب‌سازی یک مرتب‌سازی درجا نخواهد بود. چرا که متناسب با طول آرایه نیاز به فضای اضافی جهت مرتب‌سازی وجود دارد.
قطعه کد زیر یک پیاده‌سازی درجا برای تابع merge است.
| 1 | void merge(int arr[], int low, int mid, int high){
|
| 2 | int i, j, k, t;
|
| 3 | j = low;
|
| 4 | for(i = mid + 1 ; i <= high ; i++){
|
| 5 | while(arr[j] <= arr[i] && j < i)
|
| 6 | j++;
|
| 7 | if(j == i)
|
| 8 | break;
|
| 9 | t = arr[i];
|
| 10 | for(k = i ; k > j ; k --)
|
| 11 | arr[k] = arr[k - 1];
|
| 12 | arr[j] = t;
|
| 13 | }
|
| 14 | } |
| 1 | def merge(arr, low, mid, high):
|
| 2 | j = low
|
| 3 | for i in range(mid + 1, high + 1):
|
| 4 | while arr[j] <= arr[i] and j < i:
|
| 5 | j +=1
|
| 6 | if j == i:
|
| 7 | break
|
| 8 | t = arr[i]
|
| 9 | for k in range(i, j, -1):
|
| 10 | arr[k] = arr[k - 1]
|
| 11 | 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- الگوربتم مرتب‌سازی ادغامی با پیاده‌سازی فوق یک روش پایدار است. چنین الگوریتمی ترتیب عناصر با مقدار یکسان را پس از مرتب‌سازی حفظ می‌کند.