مرتب سازی فقط با یک حلقه for

[shahzadeh_jadid]

کسی میدونی چطوری میشه با یک حقله for (همچنین بدون استفاده از توابع بازگشتی) الگوریتمی بنویسه که یک آرایه ای از n عدد صحیح رو مرتب کنه؟:متفکر:

[مسعود اقدسی فام]

کسی میدونی چطوری میشه با یک حقله for (همچنین بدون استفاده از توابع بازگشتی) الگوریتمی بنویسه که یک آرایه ای از n عدد صحیح رو مرتب کنه؟:متفکر:

ثابت شده که مرتب‌سازی‌های مبتنی بر مقایسه‌ی عناصر امکان نداره کمتر از n log n باشن. یعنی خطی نمی‌شه. حالا این تک حلقه‌ی شما یا باید به نحوی n log n رو پیاده‌سازی کنه! یا مبتنی بر مقایسه نباشه.

[shahzadeh_jadid]

چجوری میشه مبتنی بر مقایسه نباشه؟
مثلا میشه با شرطها کار کرد و شمارنده حلقه داخل این شرطها باشه؟

[مسعود اقدسی فام]

چجوری میشه مبتنی بر مقایسه نباشه؟
مثلا میشه با شرطها کار کرد و شمارنده حلقه داخل این شرطها باشه؟
روش hashing (یا نگاشت) یه روش مرتب‌سازی بدون استفاده از مقایسه هستش.
اگه استفاده از پشته مجاز باشه می‌تونید توابع بازگشتی رو با پشته داخل همون حلقه شبیه‌سازی کنید.

[shahzadeh_jadid]

تو پست اول ذکر کردم بدون استفاده از توابع بازگشتی(مرتب سازی ادغامی همین کارو انجام میده)

[مسعود اقدسی فام]

تو پست اول ذکر کردم بدون استفاده از توابع بازگشتی(مرتب سازی ادغامی همین کارو انجام میده)

می‌دونم. منم منظورم شبیه‌سازی روابط بازگشتی با پشته بود؛ نه اینکه تابع به صورت بازگشتی فراخوانی بشه. اگه استفاده از پشته مجاز نیست که خب باید دنبال راه دیگه‌ای بود.

[tiphooo]

می توانید شمارنده حلقه را توسط شرطها تغییر دهید ولی در هر صورت با توجه به گفته دوستمان BIG O کماکان n log n خواهد بود که با استفاده از حلقه While معقولتر است

[shahzadeh_jadid]

مرسی دوستان
بقول دوستمون با استفاده از شرطها و تغییر شمارنده حلقه میشه نوشتش، منم از همین روش استفاده کردم
الگوریتمش یه ذره خنده دار شده(تقریبا همون مرتب سازی حبابی) ولی جواب داد:لبخند: