پاورپوینت و اسلاید MergeSort ارائه دو الگوریتم برای ادغام دو لیست مرتب

    —         —    

ارتباط با ما     —     لیست پایان‌نامه‌ها

... دانلود ...

لطفا به نکات زیر در هنگام خرید

دانلود پاورپوینت و اسلاید MergeSort ارائه دو الگوریتم برای ادغام دو لیست مرتب

توجه فرمایید.

1-در این مطلب, متن اسلاید های اولیه 

دانلود پاورپوینت و اسلاید MergeSort ارائه دو الگوریتم برای ادغام دو لیست مرتب

قرار داده شده است

2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد,در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید, می توانید با پشتیبانی تماس حاصل فرمایید

3-پس از پرداخت هزینه , حداکثر طی 12 ساعت پاورپوینت خرید شده , به ادرس ایمیل شما ارسال خواهد شد

4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ,دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت,به هیچ وجه بهم ریختگی وجود ندارد

5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار داده نشده است


بخشی از متن پاورپوینت و اسلاید MergeSort ارائه دو الگوریتم برای ادغام دو لیست مرتب :

اسلاید 1 :

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

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

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

اسلاید 2 :

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

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

     نکات:تعداد آرایه ها یا لیست های تک عضوی همان تعداد اولیه ی نودها یا اعضای آرایه هستند .                  

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

     به جای آرایه لیست به کار می بریم .

اسلاید 3 :

lبعد از شکستن لیست,زیرلیست ها را با هم ادغام می کنیم و

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

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

اسلاید 4 :

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

 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 ایجاد می شود.

اسلاید 5 :

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];

}      

   

اسلاید 6 :

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

MergePass Function

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

اسلاید 7 :

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

اسلاید 8 :

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];

}

اسلاید 9 :

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;

}

اسلاید 10 :

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

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

l

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

l

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

لینک کمکی