کسی نیست توی این مساله کمک کنه؟

(۱۳ آذر ۱۳۹۱ ۰۳:۴۲ ب.ظ)mahsa.tsi نوشته شده توسط:  کسی نیست توی این مساله کمک کنه؟

سلام دوست عزیز
شما میتونید با مقدار دهی k و آزمایش کردن آن مسله را حل کنید
بطور مثال k=1 آنگاه آرایه مرتب است: $a[1]\leq a[2]\leq a[3]\leq ...\leq a[k]$
و نیاز به جابجایی نیست: nlog1=0 و برای k=2 داریم:
$a[1]\leq a[3]\leq a[5] ...$
و $a[2]\leq a[4]\leq a[6] ...$
بنابراین از دونیم آرایه مرتب تشکیل شده است که
نیاز به n جابجایی است : $nlog(2)=n$
و در حالت کلی $k=2^m$ ، آرایه از K زیر
آرایه مرتب تشکیل شده و هر کدام $n/k$
عنصر دارد که در $m=log(k)$مرحله که هر
مرحله شامل n جابجایی است کل آرایه را مرتب کرد.
پس آرایه در $nlog(k)$ حل میشود




---------------------------------------
$www.7DataWebDesign.com$

این نکته تو کتاب CLRS تویه تمرین از فصل ۲ ام کتابش اومده
یه آرایه رو به K زیر آرایه تقسیم می کنیم که طول هر کدوم n/k هست، هر آرایه رو با زمان nk مرتب می کنیم و بعدش کل آرایه ها رو با زمان nlogn/k ام با مرتب سازی درجی مرتبش می کنیم پس میشه nk+nlogn/k ، اگه طول هر زیر آرایه k=logn باشه خواهیم داشت:
با ادغام استاندرد میتونیم آرایه که شامل K زیر لیست رو هر عنصر را در زمان logk (توسط درخت بازنده و برنده) مرتب کنیم پس میتونیم n عنصر را بر فرض مرتب بودن آنها در زمان nlogk مرتب کنیم.
در حقیقت در بدترین حالت دارای nk+nlogn/k هم هست که با مرتب سازی درجی یکسان است اما با توجه به ضرایب کوچیک در مرتب سازی درجی، الگوریتم سریع تر و بهینه تر خواهد شد.
همین مساله تو مرتب سازی سریع هم عینا هست، تو مرتب سازی سریع هم ضرایب بالاست و برای ورودی های کوچک میشه از این روش استفاده کرد که در بدترین حالت میشه مرتب سازی سریع اما در حالت میانگین بهتر و سریع تره .