همون الگوریتم مرتب سازی ادغامی هستش فقط در قسمتی از الگوریتم که مقایسه و جابجایی انجام میشه یک شمارنده هم قرار میدی، با این شرط که اگر نیاز بود جای دوتا عنصر رو عوض کنی(یعنی اینجا ۱ وارونگی وجود داشته) یکی به شمارنده اضافه کن. (شمارنده رو با این شرط اضافه میکنی)
مرتبه اجرایی مرج سورت هم که همواره nlogn است.

(۳۰ شهریور ۱۳۹۱ ۰۶:۳۶ ب.ظ)eris229 نوشته شده توسط:  همون الگوریتم مرتب سازی ادغامی هستش فقط در قسمتی از الگوریتم که مقایسه و جابجایی انجام میشه یک شمارنده هم قرار میدی، با این شرط که اگر نیاز بود جای دوتا عنصر رو عوض کنی(یعنی اینجا ۱ وارونگی وجود داشته) یکی به شمارنده اضافه کن. (شمارنده رو با این شرط اضافه میکنی)
مرتبه اجرایی مرج سورت هم که همواره nlogn است.

ممنون میشه nlgn را با الگوریتم دیگه ای کمتر کرد

---

(۳۰ شهریور ۱۳۹۱ ۰۶:۳۷ ب.ظ)m@hboobe نوشته شده توسط:  تا زه CLRS خوندم اگر تحلیل اشتباه کردم خواهش میکنم اونایی که تحلیلشون خوبه توضیحاتم یا ویرایش کنن یا تکمیل

خوب اول میگم وارونگی یعنی چی؟! [tex]i < j , A[i]>A[j][/tex]

خب این یعنی یه آرایه که n عضو داره شکسته بشه تا بتونیم عناصر اون رو تک تک با هم مقایسه کنیم و میدونیم که فقط یه ارایه یک عنصری ذاتا مرتب شده است پس توسط merge sort در وهله اول الگوریتم هر بار نصف میکنه تا به تک تک اعداد برسیم

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

تا توضیحات mergرا درست گفتی دوست من اما اگر قرار باشه تک تک عناصر با همگی مقایسه بشند درجه ما n^2 خواهد شد

تا زه CLRS خوندم اگر تحلیل اشتباه کردم خواهش میکنم اونایی که تحلیلشون خوبه توضیحاتم یا ویرایش کنن یا تکمیل

خوب اول میگم وارونگی یعنی چی؟! [tex]i < j , A[i]>A[j][/tex]

خب این یعنی یه آرایه که n عضو داره شکسته بشه تا بتونیم عناصر اون رو تک تک با هم مقایسه کنیم و میدونیم که فقط یه ارایه یک عنصری ذاتا مرتب شده است پس توسط merge sort در وهله اول الگوریتم هر بار نصف میکنه تا به تک تک اعداد برسیم

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