الگوریتم مرتب سازی ادغامی Merge Sort به روش تقسیم و حل+سورس کددر c#
روش تقسیم و حل یکی از مباحث مهم طراحی الگوریتم است که در آن مسائل را می شکنیم و به قسمت های کوچک تر تقسیم می کنیم و مسئله را حل می کنیم.
در این پست مسئله ی مرتب سازی ادغامی یا merge sort را در زبان برنامه نویسی c# بررسی می کنیم و در نهایت سورس کد آن را به همراه فایل اجرایی برنامه ،ضمیمه ی این پست می کنیم.
در همین این الگوریتم را در زبان c++ بررسی می کنیم و سورس آن را به صورت کامل در اختیار شما قرار می دهیم.
قابل ذکر است که این الگوریتم به صورت بازگشتی یا Recursive هست یعنی در تابع خود تابع اصلی دوباره صدا زده می شود.
پیچیدگی زمانی این الگوریتم n log n است که در مقایسه با bubble sort که n^2 است،سرعت بالاتری دارد.
مرتب سازی ادغامی به صورت divide-and-conquer algorithm بدین صورت است که ما لیست گرفته شده از کاربر را به 2 قسمت تبدیل می کنیم.
سپس هر قسمت را دوباره به قسمت های مساوی تبدیل می کنیم و می شکنیم تا در نهایت به 1 المنت جدا برسیم.سپس المان ها را با هم مقایسه می کنیم و ادغام می کنیم و با المان های بعدی مقایسه می کنیم به همین ترتیب تا نهایتا به یک آرایه ی مرتب شده برسیم.
شکل زیر این مطلب را می رساند :
در کتاب جعفر نژاد قمی شبه کد بدین صورت است :
کد:
کد PHP:
void mergsort (int n , keytype S [ ])
{
const int h = Į n/2 ⌡ , m = n – h;
keytype U [1...h],V [1..m];
if (n >1) {
copy S[1] through S[h] to U[h];
copy S [h + 1] through S[h] to V[1] through V[m];
mergesort(h, U);
mergesort(m,V);
merge (h , m , U,V,S);
}
}
الگوریتم ادغام :
کد:
کد PHP:
void merg ( int h , int m, const keytype U[ ],
const keytype V[ ],
keytype S[ ] )
{
index i , j , k;
i = 1; j = 1 ; k = 1;
while (i <= h && j <= m) {
if (U [i] < V [j]) {
S [k] = U [i]
i+ + ;
}
else {
S [k] = V [j];
j+ +;
}
k+ +;
}
if ( i > h)
copy V [j] through V [m] to S [k] through S [ h + m ]
else
copy U [i] through U [h] to S [k] through S [ h + m ]
}
اما کدی که ما داریم بدین صورت است :
کد:
کد PHP:
//Sort array A from index p to index r
MergeSort(A, p, r)
if p < r
q = floor((p+r)/2)
MergeSort(A, p, q)
MergeSort(A, q+1, r)
Merge(A, p, q, r)
}
Initial call: MergeSort(A, 1, n).
Merge() assumes that the array A is sorted from p to q, and from q+1 to r. Then the two parts are “shuffled” to create a sorted part of the array from index p to index r.
Note: p and r are NOT necessarily the first and the last slot. Array A can be sorted for just a portion of it.
کد:
کد PHP:
[PHP]//merge two sorted parts of array A
Merge(A, p, q, r) {
n1 = q-p+1
n2 = r-q
//create L[1, …, n1+1] and R[1, …, n2+1]
for i = 1, i ≤ n1, i++
L[i] = A[p+i-1]
for j = 1, j ≤ n2, j++
R[j] = A[q+j]
//put sentinels
L[n1+1] = ∞
R[n2+1] = ∞
i = j = 1
for ( k = p, k ≤ r, k++ )
if ( L[i] ≤ R[j] )
A[k] = L[i]
i = i+1
else
A[k] = R[j]
j = j+1
}
[/PHP]
[color=#0000CD]حال این آرایه را trace می کنیم .یک آرایه ی 4 عنصری با المان های زیر :[/color/]
کد PHP:
Tracing MergeSort(1,4) on array A = < 4 3 1 2 >.
MergeSort(1,4) p = 1, r = 4
q = 2
MergeSort(1,2) p = 1, r = 2
q = 1
MergeSort(1, 1) -> kick out
MegeSort(2,2) -> kick out
Merge(1,2) ->. Will modify the slots 1 and 2 of array A to be 3 4,
i.e. A = <3 4 1 2>.
MergeSort(3,4) p = 3, r=4
q = 3
MergeSort(3, 3) -> kick out
MegeSort(4,4) -> kick out
Merge(3,4) ->. Will modify the slots 3 and 4 of array A to be 1 2,
i.e. A = <3 4 1 2>.
Merge(1,4) -> will modify array A to be <1 2 3 4>.
حال به صورت حرفه ای تر همین trace را انجام می دهیم :
کد PHP:
Tracing MergeSort(1,4) on array A = < 4 3 1 2 >:
4 3 1 2 MergeSort(1,4)
4 3 MergeSort(1,2)
4 MergeSort(1,1)
3 MergeSort(2,2)
3 4 Merge(1,1,2) -or is it 1,2,2?
1 2 MergeSort(3,4)
1 MergeSort(3,3)
2 MergeSort(4.4)
1 2 Merge(3,4,4) or is it 3,3,4?
1 2 3 4 Merge(1,2,4)
همان طور که می بیند این کد به درستی کار می کند.
================================================== ========
اما چیزی که در فایل ضمیمه قرار گرفته در واقع این برنامه است اما به زبان سی شارپ که هم فایل اجرایی هست و هم سورس کد کامل
چیزی که این برنامه اجرا می کند مانند شکل زیر است :
پاسخ : الگوریتم مرتب سازی ادغامی Merge Sort به روش تقسیم و حل+سورس کددر c#
سلام
ببخشید میشه این برنامه رو به زبان c بهم میل کنید
ghoorishy@yahoo.com
من منتظرم
پاسخ : الگوریتم مرتب سازی ادغامی Merge Sort به روش تقسیم و حل+سورس کددر c#
سلام پس چرا نیست مرتب سازی سی شارپ
اگه میشه بی زحمت برام بفرستید خیلی احتیاج دارم
ghasemi_s70@yahoo.com[labkhand]
پاسخ : الگوریتم مرتب سازی ادغامی Merge Sort به روش تقسیم و حل+سورس کددر c#
با سلام و خسته نباشید.
هر چقدر گشتم فایل ضمیمه ای ندیدم . لطفا فایل ضمیمه را جهت دانلود در این پست قرار درهید
با تشکر
پاسخ : الگوریتم مرتب سازی ادغامی Merge Sort به روش تقسیم و حل+سورس کددر c#
سلام امیدوارم هرجا هستین هستین خوب باشین .لطفا کمکم کنید در مورد الگوریتم ضرب چند جمله ای به روش تقسیم و حل ممنونم
marziyperhiskar@yahoo.com
