لطفا به نکات زیر در هنگام خرید دانلود پاورپوینت MergeSort ارائه دو الگوریتم برای ادغام دو لیست مرتب توجه فرمایید.

1-در این مطلب، متن اسلاید های اولیه دانلود پاورپوینت MergeSort ارائه دو الگوریتم برای ادغام دو لیست مرتب قرار داده شده است 2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید 3-پس از پرداخت هزینه ، حداکثر طی 12 ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد 4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد 5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

اسلاید ۱ :

lارائه دوالگوريتم براي ادغام دو ليست مرتب

lالگوريتم غير بازگشتي Merge Sort

lالگوريتم بازگشتي Merge Sort

اسلاید ۲ :

lMerge Sort      يكي از روش هاي مرتب سازي داخلي است.

lدر مرتب سازي به روش ادغام آرايه يا ليست مورد نظر طي چند مرحله به تعدادي آرايه يا ليست تك عضوي شكسته مي شود.

     نكات:تعداد آرايه ها يا ليست هاي تك عضوي همان تعداد اوليه ي نودها يا اعضاي آرايه هستند .                  

     طول ليست يا آرايه ي اوليه را Nدر نظر بگيريد.

     به جاي آرايه ليست به كار مي بريم .

اسلاید ۳ :

lبعد از شكستن ليست،زيرليست ها را با هم ادغام مي كنيم و

   زيرليست هاي مرتب ديگري بدست مي آوريم .

lزير ليست هاي مرتب را طي چند مرحله با هم ادغام مي كنيم تا به يك ليست مرتب با N عضو برسيم.  

اسلاید ۴ :

ادغام دو ليست مرتب:

 Initlist[l],…,initlist[m]                              initlist[m+1],…,initlist[n]

دو ليست مرتب شده  از نوع Elementهستند، به طوري كه:

Initlist [l].key≤…≤ initlist [m].key

Initlist[m+1].key ≤…≤ initlist [n].key

   در تابع Mergeاين دو ليست مرتب با يكديگر ادغام مي شوندو

 تابع مرتب شده ي جديدي به نام MergedList ايجاد مي شود.

 

اسلاید ۵ :

Merge Algorithm:

void merge(Element *initList,Element *mergedList,

                     const int l,const int m,const int n)

{

  for(int i1=l,iResult=l,i2=m+1;i1<=m&&i2<=n;  iResult ++)

      if(initlist[i1].getkey()<=initlidt[i2].getkey())    {

                    mergedList[iResult]=initList[i1];

                    i1++;    }

       else  {        

                  mergedList[iResult]=initList[i2];

                  i2++;   }            

       if(i1>m)

             for(int t=i2;t<=n;t++)

                   mergedList[iResult+t-i2]=initList[t];

       else

              for(int t=i1;t<=m;t++)

                   mergedList[iResult+t-i1]=initList[t];

}      

   

اسلاید ۶ :

lاز آنجا كه مرتب سازي ادغام شامل چند مرحله است از اين رو بهتر است ابتدا تابعي براي اين منظور معرفي كنيم:

MergePass Function

lپس از آن به معرفي MergeSort Algorithm مي پردازيم كه مرتب سازي را با احضار مكررتابع Merge Pass  انجام مي دهد.  

اسلاید ۷ :

MergePass Algorithm

Void MergePass(Element *initlist, Element *resultlist ,const int n ,const int l )

{

    for ( int i=1 ;  i<=n-2*l+1 ;  i+=2*l )

          merge ( initlist , resultlist , i , i+l-1 , i+2*l-1 );

                                                               i=1< 3                 i=3<=3

                     n=4  l=1  i<=3

                     n=4  l=2  i<=1

 

 

اسلاید ۸ :

MergePass Algorithm

Void MergePass(Element *initlist, Element *resultlist ,const int n ,const int l )

{

    for ( int i=1 ;  i<=n-2*l+1 ;  i+=2*l )

          merge ( initlist , resultlist , i , i+l-1 , i+2*l-1 );

    if ( ( i+l-1) < n)   

          merge ( initlist , resultlist , i , i+l-1 , n);

    else

         for ( int t=i ; t<=n ; t++ )

               resultlist[t]=initlist[t];

}

 

 

اسلاید ۹ :

MergeSort Algorithm

Void MergeSort ( Element * list , const int n )

{

       Element * tempList= new Element [n+1];

       //l is the length of the sublist currently being merged

      for ( int l=1 ; l<n ; l*=2 )

      {      

             MergePass ( list , tempList , n , l );

             l*=2;

             MergePass ( tempList , list , n , l ); // interchange role of list and tempList

      }

     Delete [ ] tempList;

}

اسلاید ۱۰ :

تجزیه و تحلیل تابع MergeSort :

l تابعMergeSort  در چند مرحله از رکوردهای مرتب شونده عبور می کند.در مرحله ی اول لیست هایی به طول ۱ ادغام می شوند.مرحله ی دوم طول لیست های ادغام شونده ۲ است .درمرحله ی i ام لیست های ادغام شونده طول ۲i-1 دارند.

l

lدر نتیجه تعداد کل مراحل عبور از داده ها log2n ]   [  است.

l

lهر مرحله از مرتب سازی ادغام در زمان O(n) انجام می شود و زمان اجرای کل O(n logn) است.