(25 امتیاز از 6 رای)
Loading...
الگوریتم مرتب سازی ادغامی (Merge Sort)
الگوریتم مرتب سازی ادغامی (Merge Sort) مانند الگوریتم QuickSort، به روش تقسیم و غلبه (Divide and Conquer) عمل می کند. در این الگوریتم آرایه داده شده به بخش های کوچک تر تقسیم می شود و هر بخش مرتب شده و بخش بعدی ادغام می شود تا در نهایت کل آرایه مرتب شد.
تابع merge برای ادغام دو بخش از آرایه مورد استفاده قرار می گیرد. merge(arr, l, m, r) فرآیند کلیدی است که فرض می کند arr[l..m] و arr[m+1..r] به صورت مرتب شده هستند و دو زیر آرایه مرتب شده را با هم ادغام می کند.
1 2 3 4 5 6 7 8 9 10 | 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) |
تصویر زیر کل فرآیند مرتب سازی یک آرایه توسط الگوریتم مرتب سازی ادغامی را نشان می دهد. اگر به تصویر زیر نگاه کنید متوجه خواهید شد که تقسیم آرایه به زیر آرایه تا زمانی که تعداد عناصر به 1 نرسیده، ادامه می یابد. زمانی که به 1 رسید، فرآیند ادغام کردن بلوک های مختلف شروع می شود و تا ادغام کل آرایه ادامه می یابد.
پیاده سازی الگوریتم Merge Sort با استفاده از زبان برنامه نویسی C:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | /* 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; } |
خروحی:
1 2 3 4 | Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13 |
تغییر به حالت نزولی
برای تغییر به حالت نزولی کافیست در تابع merge شرط موجود در حلقه while را از if (L[i] <= R[j]) به if (L[i] >= R[j]) تغییر دهید.
نکات
- پیچیدگی زمانی در هر سه حالت (بدترین، متوسط، بهترین) برابر است
- فضای اضافه برابر است با O(n).
- این الگوریتم برای مرتب سازی لینک لیست ها با زمان O(nlogn) مناسب است.
سلام، وقت بخیر. ببخشید امکانش هست که برنامه ی مرتب سازی ادغامی رو بدون استفاده از توابع و کلاس ها در زبان c++ بذارید؟ ممنون
سلام..تا جایی که من بلدم نمیشه همچین کاری کرد...باید از توابع استفاده بشه
ممنون که جواب دادین. من از استادمون پرسیدم گفتن میشه.