الگوریتم sort !!!

[3tareh]

سلام
لطفاً اگر کسی می تونه در مورد این برنامه کمکم کنه ممنون می شم:
هدف مرتب کردن n عدد به صورت صعودی می باشد. می خواهیم به وسیله یک ماشین این کار را انجام دهیم. این ماشین در هر مرحله تعدادی زوج از این اعداد را به عنوان ورودی می گیرد و در جایگشت موجود جای این اعداد را عوض می کند.
می خواهیم با حداکثر O(logn) مرحله استفاده از ماشین هر جایگشتی از اعداد را به صورت صعودی مرتب کنیم.

[Mega7000]

سلام
جایگشت خاصی مورد نیاز هست؟ یا هر روشی اجازه استفاده هست؟

[3tareh]

سلام
هر جایگشتی ممکنه وجود داشته باشه و از هر روشی می شه استفاده کرد!

[Mega7000]

خب می تونید از mergeSort (نوعی که تو خود آرایه مرتب می کنه) استفاده کنین

[3tareh]

فکر کنم از روش تقسیم و حل را باید استفاده کنم ولی احتمالاً MergeSort اینجا به کار نیاد.
چون باید حداکثر O (lgn) بار از آن ماشین استفاده کنیم.
راه حل بهتر که تعداد مراحل کمتر بشه وجود داره؟؟؟؟؟

[Mega7000]

خب شما می تونید الگوریتم mergesorte رو از طریق روش Divide & conqure پیاده سازی کنین

[3tareh]

ببخشید میشه بیشتر توضیح بدین!!

[3tareh]

نقل قول:
الگوریتم MergeSort چه در بهترین حالت و چه در بدترین حالت n logn بار فراخوانی میشود.

من بازم مشکل دارم.:ناراحت: توی استفاده از اون ماشین. چون حداکثر مراحل استفاده از ماشین log n هست. ولی ماشین این قابلیت را داره که توی یک مرحله استفاده از اون چند جفت عدد را با هم جابه جا کنه .
حالا MergeSort را چه جوری پیاده سازی کنم که کمتر از log n بار از ماشین استفاده بشه؟؟

[Mega7000]

آیا حتما باید هر بار تعداد تقسیم مساوی باشد؟

[3tareh]

سلام
این یک نمونه مثال از اجرای این برنامه است که باید در مجموع log n تا Step داشته باشه


2 4 1 3

Step 1: Swap (4,1)

Result: 2 1 4 3

Step 2: Swap(2,1) , Swap (4,3)

Result: 1 2 3 4

اگه کمکم کنین ممنون میشم.

[3tareh]

دوستان سلام

من هنوز هم به راهنمایی نیاز دارم. لطفاً اگه کسی می تونه کمکم کنه!!!!!!!:گریه:

[Mega7000]

سلام ستاره خانم
می شه جوابشو از کسی که این سوال رو مطرح کرده بپرسین بما هم بگین
ممنون