محاسبه تعداد عمل جابجایی مورد نیاز در مرتب سازی ارایه بصورت بازگشتی

[sobhan1990]

سلام

صورت سوال

تعداد عمل جابجایی مورد نیاز برای مرتب سازی حبابی(Buble Sort) یک ارایه به روش تقسیم و غلبه(بازگشتی) چطور بدست میاد؟

اگر بدترین حالت را در نظر بگیریم، یعنی زمانیکه ارایه بصورت نزولی مرتب شده باشد، باید برای عنصر اول، N-1 جایحایی و برای عنصر دوم،N-2 جابجایی و الی آخر...

از روش غیر بازگشتی براحتی بدست میاد ولی روش بازگشتی رو میخوام.

راستی حتما باید از O(nlogn) باشه.


صورت دیگه سوال اینه:
اگر اندیس j بزرگتر از اندیس i باشد، و عنصر موجود در مکان i بزرگتر از عنصر موجود در مکان j باشد، آنگاه یک واحد شمارنده را زیاد کن. که شمارنده همون تعداد عمل مورد نیاز جابجایی هست.

ممنون میشم راهنمایی کنید.

[Mahdi1001]

سلام

راستش تو اينهمه سالى كه من درس خوندم bubble سورت بازگشتس جاى ندیدم و نشنيدم.
چون آسان ماهيتِ بازگشتی نداره. و وقتى بازگشتی بشه bubble sort نيس!
حالا اگه واقعا bubble سورت بتونين بازگشتی بنويسين حتما بذارين کدشو تا ماهم ياد بگيريم.
quick sort تو ديدين دیگه ، يه الگوریتم بازگشتی nlogn كه ريز بشين توش ميبينن مرحله آخر كه به يك اعداد ميرسه با بقلیش مقايسه ميكنه و همين طور تمام عددِ فرد با عددِ زوج مقايسه ميشن.
اما bubble به ترتیب هر اعداد با بقلیش يعنى ۱ با ۲ و ۲ ba3 و ... ميشه بازگشتی یه جور دیگه بنويسى اما اينطورى نميشه.

اگه کدشو بذارين كه حل ميشه