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

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

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




---------------------------------------
[tex]www.7DataWebDesign.com[/tex]

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