خسته نباشید
همونطور که میدونیم مرتب سازی ادغامی مصرف حافظه ای برابر O(n) داره. واسه مشکل حافظه این الگوریتم الگوریتمی با مصرف حافظه O(1) به نام ادغامی در جا ارائه شده.
میشه لطفا الگوریتم ادغامی درجا رو به زبان سی پیاده کنین و فرقش رو با حالت معمولی توضیح بدین. خیلی ممنون
مرتب سازی درجا نوعی الگوریتم مرتب سازی است که از فضایی بیشتر از آنچه که مورد نیاز نگهداری ورودی است ، استفاده نمی کند .در لینک های زیر الگوریتم اول درجا نیست زیرا از آرایه های U,V بعلاوه آرایه ورودی S استفاده می کند .
کد ها از لینک های زیر به دست میاد :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
تو کتاب Horowitz توضیح داده.کدش رو هم نوشته
(01 اردیبهشت 1391 01:25 ب.ظ)mfXpert نوشته شده توسط: [ -> ]تو کتاب Horowitz توضیح داده.کدش رو هم نوشته
ترجمه جعفر نژاد هم این موضوع رو پوشش داده . تقریبا 7-8 صفحه مرتب سازی ادغامی رو شرح داده .
ابتدا الگوریتم مرتب سازی ادغامی معمولی:
کد:
void mergesort (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 merge ( 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 ]
}
حالا الگوریتم مرتب سازی ادغامی درجا :
کد:
void mergesort2 (index low, index high)
{
index mid;
if (low < high) {
mid = Į ( low + high) / 2 ⌡;
mergesort 2 (low, mid);
mergesort 2 (mid +1, high);
merge2(low,mid,high)
}
}
void merge2 (index low, index mid, index high)
{
index i, j , k;
keytype U [ low..high]
i = low; j = mid +1 ; k = low;
while ( i <= mid && j <= high) {
if ( S [i] < S [j] ) {
U [k] = S [i];
i + + ;
}
else {
U [k] = S [j]
j ++;
}
k ++;
}
if ( i > mid )
move S [j] through S [high] to U [k] through U [high]
else
move S [i] through S [mid] to U [k] through U [high]
move U [low] through U [high] to S [low] through S [high]
}
[/php]
همونطور که ملاحظه می کنید در الگوریتم اول آرایه های U و V همراه با آرایه S استفاده می شوند. اگر U و V پارامترهای متغیر در merge باشند یک کپی دیگر از این آرایه ها هنگام فراخوانی merge ایجاد نخواهد شد. اما با هر بار فراخوانی mergesort آرایه های U و V ایجاد خواهند شد.
در الگوریتم دوم n و S بصورت عمومی تعریف می شوند.
این توضیحات از کتاب نیپولیتان ترجمه جعفرنژاد است
اینم پیاده سازی
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.