ابهام در تحلیل یک الگوریتم مرتب سازی

[veniz2008]

سلام دوستان،یک سوال داشتم که در انجام دادنش به بن بست رسیدم،در واقع نتونستم تحلیل درستی از مسئله رو بدست بیارم،از اساتید تقاضا دارم که راهنمایی کنن،اما سوال: مرتب سازی جابجایی "زوج - فرد" به اینصورت انجام میگیرد:در سراسر فایل چندبار گذر کنید. در گذر اول x[i] رابا x[i+1] برای کلیه مقادیر فرد i مقایسه کنید. در گذر دوم x[i] را با x[i+1] برای کلیه مقادیر زوج i مقایسه کنید. هروقت x[i]>x[i+1 ،جای آنها را با هم عوض کنید.این فرآیند را تا مرتب شدن فایل ادامه دهید.
الف.شرط پایان روش مرتب سازی چیست؟
ب.کارایی(مرتبه زمانی)این روش در حالت متوسط چگونه است؟
ممنونم از راهنمایی هایی که انجام میدید.

[اسماعیل ابراهیمی]

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

using System;

namespace Whittle.Sorting.Exchange
{
class OddEven<T> : Sorts<T> where T : IComparable
{
override public string Name
{
get { return "Odd-Even"; }
}

override public void Sort(T[] items)
{
int n = items.Length;
Boolean sorted = false;
while (sorted == false)
{
sorted = true;
for (int i = 1; i < n - 1; i += 2)
{
if (items[i].CompareTo(items[i + 1]) > 0)
{
Swap(items, i, i + 1);
sorted = false;
}
}

for (int i = 0; i < n - 1; i += 2)
{
if (items[i].CompareTo(items[i + 1]) > 0)
{
Swap(items, i, i + 1);
sorted = false;
}
}
}
}
}
}

[veniz2008]

ضمن تشکر از شما،اما در مورد دو تا سوالی که پرسیدم،به نظر میاد شرط پایان برنامه اینه که مقدار i به انتها رسیده(یعنی n-2) و جابه جایی هم صورت نگرفته چون درواقع زمانی که sorted = true باشه و به انتهای حلقه برسیم اونوقت لیست مرتب شده است،آیا این تحلیل درسته؟، اما در مورد مرتبه در حالت متوسط:حلقه های for هر کدومشون n/2 بار تکرار میشن(برای دو حلقه for داریم n/2 +n/2 که میشه n)حلقه while هم به تعداد n/2 بار اجرا میشود که در نهایت داریم: n/2 * n = O(n^2 ،این تحلیل آیا درسته؟

[amir11205]

سلام دوست عزیز
شرط پایان حلقه اینه که مقدار sorted مساوی ture بشه.داخل حلقه while رو اگه بخوایم دقیق بررسیش کنیم در صورتی که n زوج باشه حلقه for اول n\2)-1) بار و حلقه for دوم n/2 بار اجرا میشه و اگر n فرد باشه هر دو حلقه for کف n/2 بار اجرا میشه که در هر دو حالت (n زوج یا فرد) جمعا هر دو حلقه باهم n-1 بار اجرا میشه.اما چون در مرتبه زمانی n-1 با n تفاوتی نداره داخل حلقه while مرتیه زمانیش O(n میشه و در هر سه حالت بدترین و متوسط و بهترین این مقدار ثابته.اما زمان کل اجرای الگوریتم به تعداد اجرای خود حلقه while وابسته است.سه حالت زیر امکان داره اتفاق بیفته
1- بهترین حالت:بهترین حالت زمانیه که ورودی از قبل مرتب باشه که در این صورت حلقه while یکبار اجرا میشه و میشه همون O(n
2- بدترین حالت: بدترین حالت زمانیه که ورودی از قبل نزولی مرتب باشه یا بهتره بگیم کوچکترین مقدار ورودی تو آخرین خونه باشه که در این صورت حلقه while دقیقا n بار اجرا میشه تا کوچکترین مقدار رو با اولین خونه برگردونه که در این صورت میشه O(n^2
3- حالت متوسط: فکر کنم اینجوری باشه که نصفه ی (یعنی n/2) اول ورودی از قبل صعودی مرتب باشه و نصفه ی دوم ورودی از قبل نزولی مرتب باشه و همچنین بیشترین مقدار نصفه ی اول، کمتر مساوی کمترین مقدار نصفه ی دوم باشه مثلا ورودی به صورت زیر باشه: (از چپ به راست)
7و8و9و10و4و3و2و1
به 4 (بیشترین مقدار نصفه ی اولی) و 7 (کمترین مقدار نصفه ی دومی) فکر کنین
که در این صورت در نصفه ی اول ورودی تغییری ایجاد نمیشه و فقط تو نصفه ی دوم مقایسه و جابجایی داریم که در این حالت حلقه while فکر کنم n/2 بار اجرا میشه
که بازم در این حالت مرتبه زمانی برابر O(n^2هستش. یعنی داریم
n/2 * (n-1
امیدوارم که گفته هام درست باشه