۰
subtitle
ارسال: #۱
مرتب سازی ادغامی با مصرف حافظه (O(1
خسته نباشید
همونطور که میدونیم مرتب سازی ادغامی مصرف حافظه ای برابر O(n) داره. واسه مشکل حافظه این الگوریتم الگوریتمی با مصرف حافظه O(1) به نام ادغامی در جا ارائه شده.
میشه لطفا الگوریتم ادغامی درجا رو به زبان سی پیاده کنین و فرقش رو با حالت معمولی توضیح بدین. خیلی ممنون
همونطور که میدونیم مرتب سازی ادغامی مصرف حافظه ای برابر O(n) داره. واسه مشکل حافظه این الگوریتم الگوریتمی با مصرف حافظه O(1) به نام ادغامی در جا ارائه شده.
میشه لطفا الگوریتم ادغامی درجا رو به زبان سی پیاده کنین و فرقش رو با حالت معمولی توضیح بدین. خیلی ممنون
۰
ارسال: #۲
RE: مرتب سازی ادغامی با مصرف حافظه O(1)
ابتدا الگوریتم مرتب سازی ادغامی معمولی:
حالا الگوریتم مرتب سازی ادغامی درجا :
[/php]
همونطور که ملاحظه می کنید در الگوریتم اول آرایه های U و V همراه با آرایه S استفاده می شوند. اگر U و V پارامترهای متغیر در merge باشند یک کپی دیگر از این آرایه ها هنگام فراخوانی merge ایجاد نخواهد شد. اما با هر بار فراخوانی mergesort آرایه های U و V ایجاد خواهند شد.
در الگوریتم دوم n و S بصورت عمومی تعریف می شوند.
این توضیحات از کتاب نیپولیتان ترجمه جعفرنژاد است
اینم پیاده سازی
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
کد:
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]
}همونطور که ملاحظه می کنید در الگوریتم اول آرایه های U و V همراه با آرایه S استفاده می شوند. اگر U و V پارامترهای متغیر در merge باشند یک کپی دیگر از این آرایه ها هنگام فراخوانی merge ایجاد نخواهد شد. اما با هر بار فراخوانی mergesort آرایه های U و V ایجاد خواهند شد.
در الگوریتم دوم n و S بصورت عمومی تعریف می شوند.
این توضیحات از کتاب نیپولیتان ترجمه جعفرنژاد است
اینم پیاده سازی
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
۰
ارسال: #۳
مرتب سازی ادغامی با مصرف حافظه O(1)
مرتب سازی درجا نوعی الگوریتم مرتب سازی است که از فضایی بیشتر از آنچه که مورد نیاز نگهداری ورودی است ، استفاده نمی کند .در لینک های زیر الگوریتم اول درجا نیست زیرا از آرایه های U,V بعلاوه آرایه ورودی S استفاده می کند .
کد ها از لینک های زیر به دست میاد :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
کد ها از لینک های زیر به دست میاد :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
۰
ارسال: #۵
RE: مرتب سازی ادغامی با مصرف حافظه O(1)
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close