الگوریتم مرتب سازی ادغامی Merge Sort به روش تقسیم و حل+سورس کددر c#

**آبجی** · 14th April 2010 12:55 AM

روش تقسیم و حل یکی از مباحث مهم طراحی الگوریتم است که در آن مسائل را می شکنیم و به قسمت های کوچک تر تقسیم می کنیم و مسئله را حل می کنیم.
در این پست مسئله ی مرتب سازی ادغامی یا 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)

همان طور که می بیند این کد به درستی کار می کند.
================================================== ========
اما چیزی که در فایل ضمیمه قرار گرفته در واقع این برنامه است اما به زبان سی شارپ که هم فایل اجرایی هست و هم سورس کد کامل
چیزی که این برنامه اجرا می کند مانند شکل زیر است :

**قریشی** · 25th October 2010 10:41 AM

سلام
ببخشید میشه این برنامه رو به زبان c بهم میل کنید
ghoorishy@yahoo.com
من منتظرم

**libera** · 2nd June 2011 09:05 PM

سلام خسته نباشید(ابجی)

من برنامه مرتب سازی ادغامی و یا سریع رو به زبان سی شارپ میخوام هر کار کردم اصلا نتونستم فایلی رو که گزاشتین رو صفحه پیدا کنم فقط کد ها به زبان دیگه ای بود میشه لطف کنید و برای میلم بفرستید ممنون میشم ftalei69@yahoo.com
واقها حیاتیه یه دنیا تشکررررررررررررررر