sobhan1990
یک شنبه 23 آبان 1389, 12:24 عصر
سلام
صورت سوال
تعداد عمل جابجایی مورد نیاز برای مرتب سازی حبابی(Buble Sort) یک ارایه به روش تقسیم و غلبه(بازگشتی) چطور بدست میاد؟
اگر بدترین حالت را در نظر بگیریم، یعنی زمانیکه ارایه بصورت نزولی مرتب شده باشد، باید برای عنصر اول، N-1 جایحایی و برای عنصر دوم،N-2 جابجایی و الی آخر...
از روش غیر بازگشتی براحتی بدست میاد ولی روش بازگشتی رو میخوام.
راستی حتما باید از O(nlogn) باشه.
صورت دیگه سوال اینه:
اگر اندیس j بزرگتر از اندیس i باشد، و عنصر موجود در مکان i بزرگتر از عنصر موجود در مکان j باشد، آنگاه یک واحد شمارنده را زیاد کن. که شمارنده همون تعداد عمل مورد نیاز جابجایی هست.
ممنون میشم راهنمایی کنید.
صورت سوال
تعداد عمل جابجایی مورد نیاز برای مرتب سازی حبابی(Buble Sort) یک ارایه به روش تقسیم و غلبه(بازگشتی) چطور بدست میاد؟
اگر بدترین حالت را در نظر بگیریم، یعنی زمانیکه ارایه بصورت نزولی مرتب شده باشد، باید برای عنصر اول، N-1 جایحایی و برای عنصر دوم،N-2 جابجایی و الی آخر...
از روش غیر بازگشتی براحتی بدست میاد ولی روش بازگشتی رو میخوام.
راستی حتما باید از O(nlogn) باشه.
صورت دیگه سوال اینه:
اگر اندیس j بزرگتر از اندیس i باشد، و عنصر موجود در مکان i بزرگتر از عنصر موجود در مکان j باشد، آنگاه یک واحد شمارنده را زیاد کن. که شمارنده همون تعداد عمل مورد نیاز جابجایی هست.
ممنون میشم راهنمایی کنید.