الگوریتم مرتب سازی ادغامی (Merge Sort)
الگوریتم مرتب سازی ادغامی (Merge Sort) مانند الگوریتم QuickSort، به روش تقسیم و غلبه (Divide and Conquer) عمل می کند. در این الگوریتم آرایه داده شده به بخش های کوچک تر تقسیم می شود و هر بخش مرتب شده و بخش بعدی ادغام می شود تا در نهایت کل آرایه مرتب شد.
تابع merge برای ادغام دو بخش از آرایه مورد استفاده قرار می گیرد. merge(arr, l, m, r) فرآیند کلیدی است که فرض می کند arr[l..m] و arr[m+1..r] به صورت مرتب شده هستند و دو زیر آرایه مرتب شده را با هم ادغام می کند.
MergeSort(arr[], l, r) If r > l Find the middle point to divide the array into two halves: middle m = (l+r)/2 Call mergeSort for first half: Call mergeSort(arr, l, m) Call mergeSort for second half: Call mergeSort(arr, m+1, r) Merge the two halves sorted in step 2 and 3: Call merge(arr, l, m, r)
تصویر زیر کل فرآیند مرتب سازی یک آرایه توسط الگوریتم مرتب سازی ادغامی را نشان می دهد. اگر به تصویر زیر نگاه کنید متوجه خواهید شد که تقسیم آرایه به زیر آرایه تا زمانی که تعداد عناصر به ۱ نرسیده، ادامه می یابد. زمانی که به ۱ رسید، فرآیند ادغام کردن بلوک های مختلف شروع می شود و تا ادغام کل آرایه ادامه می یابد.
پیاده سازی الگوریتم Merge Sort با استفاده از زبان برنامه نویسی C:
/* C program for Merge Sort */
#include<stdlib.h>
#include<stdio.h>
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
/* Driver program to test above functions */
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
امتحان کنید
خروحی:
Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13
نکات
- پیچیدگی زمانی در هر سه حالت (بدترین، متوسط، بهترین) برابر است
- فضای اضافه برابر است با O(n).
- این الگوریتم برای مرتب سازی لینک لیست ها با زمان O(nlogn) مناسب است.
نوشته الگوریتم مرتب سازی ادغامی (Merge Sort) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.
