آبجی
14th April 2010, 12:55 AM
روش تقسیم و حل یکی از مباحث مهم طراحی الگوریتم است که در آن مسائل را می شکنیم و به قسمت های کوچک تر تقسیم می کنیم و مسئله را حل می کنیم.
در این پست مسئله ی مرتب سازی ادغامی یا merge sort را در زبان برنامه نویسی c# بررسی می کنیم و در نهایت سورس کد آن را به همراه فایل اجرایی برنامه ،ضمیمه ی این پست می کنیم.
در همین این الگوریتم را در زبان c++ بررسی می کنیم و سورس آن را به صورت کامل در اختیار شما قرار می دهیم.
قابل ذکر است که این الگوریتم به صورت بازگشتی یا Recursive هست یعنی در تابع خود تابع اصلی دوباره صدا زده می شود.
پیچیدگی زمانی این الگوریتم n log n است که در مقایسه با bubble sort که n^2 است،سرعت بالاتری دارد.
http://www.otf-uni.ir/Upload/time%20complexity.png
مرتب سازی ادغامی به صورت divide-and-conquer algorithm بدین صورت است که ما لیست گرفته شده از کاربر را به 2 قسمت تبدیل می کنیم.
سپس هر قسمت را دوباره به قسمت های مساوی تبدیل می کنیم و می شکنیم تا در نهایت به 1 المنت جدا برسیم.سپس المان ها را با هم مقایسه می کنیم و ادغام می کنیم و با المان های بعدی مقایسه می کنیم به همین ترتیب تا نهایتا به یک آرایه ی مرتب شده برسیم.
شکل زیر این مطلب را می رساند :
http://www.otf-uni.ir/Upload/mergesorttrace.png
در کتاب جعفر نژاد قمی شبه کد بدین صورت است :
کد:
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);
}
}
الگوریتم ادغام :
کد:
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 ]
}
اما کدی که ما داریم بدین صورت است :
کد:
//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.
کد:
//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
}
[color=#0000CD]حال این آرایه را trace می کنیم .یک آرایه ی 4 عنصری با المان های زیر :[/color/]
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 را انجام می دهیم :
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)
همان طور که می بیند این کد به درستی کار می کند.
================================================== ========
اما چیزی که در فایل ضمیمه قرار گرفته در واقع این برنامه است اما به زبان سی شارپ که هم فایل اجرایی هست و هم سورس کد کامل
چیزی که این برنامه اجرا می کند مانند شکل زیر است :
http://www.otf-uni.ir/Upload/mergesortcs.jpg
در این پست مسئله ی مرتب سازی ادغامی یا merge sort را در زبان برنامه نویسی c# بررسی می کنیم و در نهایت سورس کد آن را به همراه فایل اجرایی برنامه ،ضمیمه ی این پست می کنیم.
در همین این الگوریتم را در زبان c++ بررسی می کنیم و سورس آن را به صورت کامل در اختیار شما قرار می دهیم.
قابل ذکر است که این الگوریتم به صورت بازگشتی یا Recursive هست یعنی در تابع خود تابع اصلی دوباره صدا زده می شود.
پیچیدگی زمانی این الگوریتم n log n است که در مقایسه با bubble sort که n^2 است،سرعت بالاتری دارد.
http://www.otf-uni.ir/Upload/time%20complexity.png
مرتب سازی ادغامی به صورت divide-and-conquer algorithm بدین صورت است که ما لیست گرفته شده از کاربر را به 2 قسمت تبدیل می کنیم.
سپس هر قسمت را دوباره به قسمت های مساوی تبدیل می کنیم و می شکنیم تا در نهایت به 1 المنت جدا برسیم.سپس المان ها را با هم مقایسه می کنیم و ادغام می کنیم و با المان های بعدی مقایسه می کنیم به همین ترتیب تا نهایتا به یک آرایه ی مرتب شده برسیم.
شکل زیر این مطلب را می رساند :
http://www.otf-uni.ir/Upload/mergesorttrace.png
در کتاب جعفر نژاد قمی شبه کد بدین صورت است :
کد:
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);
}
}
الگوریتم ادغام :
کد:
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 ]
}
اما کدی که ما داریم بدین صورت است :
کد:
//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.
کد:
//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
}
[color=#0000CD]حال این آرایه را trace می کنیم .یک آرایه ی 4 عنصری با المان های زیر :[/color/]
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 را انجام می دهیم :
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)
همان طور که می بیند این کد به درستی کار می کند.
================================================== ========
اما چیزی که در فایل ضمیمه قرار گرفته در واقع این برنامه است اما به زبان سی شارپ که هم فایل اجرایی هست و هم سورس کد کامل
چیزی که این برنامه اجرا می کند مانند شکل زیر است :
http://www.otf-uni.ir/Upload/mergesortcs.jpg