پیاده سازی مرتب سازی ادغامی در #C
اگر از شما بخواهند که از میان یک لیست کوچکترین عدد را انتخاب کنید می توانید با چند بررسی شرطی آن را پیدا کنید ولی اگر از شما بخواهند که چهارمین عدد کوچکتر از لیست را انتخاب کنید در این حالت برای رسیدن به جواب باید آرایه را مرتب کنید . در سی شارپ متد Sort کار مرتب کردن آرایه ها را انجام می دهد .
الگوریتم های مختلفی برای مرتب کردن آرایه ها وجود دارد از جمله :
Selection Sort
Insertion Sort
Bubble Sort
Counting Sort
Quick Sort
در این مقاله قصد داریم بپردازیم به الگوریتم مرتب سازی ادغامی و توابعی را معرفی کنیم که این کار را انجام می دهند .
مرتب سازی ادغامی (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 |
private void Merge(int[] input, int left, int middle, int right) { int[] leftArray = new int[middle - left + 1]; int[] rightArray = new int[right - middle]; Array.Copy(input, left, leftArray, 0, middle - left + 1); Array.Copy(input, middle + 1, rightArray, 0, right - middle); int i = 0; int j = 0; for (int k = left; k < right + 1; k++) { if (i == leftArray.Length) { input[k] = rightArray[j]; j++; } else if (j == rightArray.Length) { input[k] = leftArray[i]; i++; } else if (leftArray[i] <= rightArray[j]) { input[k] = leftArray[i]; i++; } else { input[k] = rightArray[j]; j++; } } } private void MergeSort(int[] input, int left, int right) { if (left < right) { int middle = (left + right) / 2; MergeSort(input, left, middle); MergeSort(input, middle + 1, right); Merge(input, left, middle, right); } } |
و در نهایت برای فراخوانی و مرتب کردن آرایه :
|
1 2 3 4 5 6 7 8 9 |
int[] arr = new int[10] { 1, 5, 4, 11, 20, 8, 2, 98, 90, 16 }; MergeSort(arr, 0, arr.Length - 1); Console.WriteLine("Sorted Values:"); for (int i = 0; i < arr.Length; i++) Console.WriteLine(arr[i]); |
دیدگاهتان را بنویسید
برای نوشتن دیدگاه باید وارد بشوید.