لطفا به ‌ترتیب قد وارد شوید!

یکی از الگوریتم‌های پرکاربرد در دنیای برنامه‌نویسی الگوریتم‌های مرتب‌سازی است و اهمیت این موضوع در تمام زمینه‌های برنامه‌نویس مشهود است. وقتی در شبکه مشغول دریافت اطلاعات هستید، اطلاعات باید به‌صورت مرتب در کنار هم قرار گرفته تا نمایش‌دهنده اطلاعات اصلی باشند. اگر می‌خواهید بیشترین درآمد را بین کارمندان پیدا کنید، پس باید اطلاعات کارمندان را بر اساس حقوق دریافتی خود مرتب کنید. اگر کوچک‌ترین عضو یک دانشکده را می‌خواهید، اول باید اطلاعات دانشجو‌یان را بر اساس تاریخ تولد به‌صورت نزولی مرتب کنید.

دو نوع مرتب‌سازی داریم: یکی به‌صورت صعودی و دیگری به‌صورت نزولی. منظور از صعودی این است که عناصر به‌ترتیب از بزرگ‌ترین تا کوچک‌ترین عنصر مرتب می‌شوند و به‌عکس منظور از نزولی این است که عناصر به‌ترتیب از کوچک‌ترین تا بزرگ‌ترین عنصر در آرایه جای می‌گیرند.

یکی از ساده‌ترین الگوریتم‌های مرتب‌سازی، مرتب‌سازی به‌روش انتخابی است. امااین الگوریتم چگونه داده‌ها را مرتب می‌کند؟

ابتدا بزرگ‌ترین عدد را در مجموعه پیدا کرده وسپس آن را با آخرین عنصر آرایه یعنی جا‌به‌جا می‌کنیم. حال از بین عناصر [1]a تا بزرگ‌ترین عنصر (که دومین بزرگ‌ترین عنصر آرایه است) را پیدا کرده و آن را باجابه‌جا می‌کنیم. این عمل را N-1 بار تکرار می‌کنیم. طبیعی است در تکرار آخر دو عنصر [1]a و [2]a مقایسه می‌شوند و بزرگترین آنها در خانه [2]a قرار می‌گیرد.

شبه کد الگوریتم فوق به‌صورت زیر است:

static void SelectionSort(int[] a, int n)

{

int max, temp;

for (int i = 1; i « n; ++i) {

max = 0;

for (int j = 1; j «= n - i; ++j)

if (a[j]» a[max]) max = j;

if (max != n - i) {

temp = a[max];

a[max] = a[n - i];

a[n - i] = temp;

}

}

}

پیچیدگی الگوریتم مرتب‌سازی

به روش انتخابی

در بیشتر روش‌های مرتب‌سازی از دو حلقه تودرتو استفاده می‌شود و بیشترین زمان طی شده به حلقه داخلی مربوط است. اگر زمان مقایسه در حلقه داخلی را K در نظر بگیریم، زمان لازم برای اجرای حلقه داخلی در هر دور اجرای حلقه بیرونی برابر (b+k(n-i است که مقدار b یک عدد ثابت بوده و زمانی است که طی شده تا به حلقه داخلی برسیم.

اگر مدت زمانی که پس از اجرای حلقه داخلی صرف می‌شود تا به دور بعدی حلقه بیرونی برسیم مقدار ثابت C در نظر بگیرم، مدت اجرا شدن هر دور حلقه بیرونی برابر b+(n-i)k+c خواهد بود.

برای الگوریتم بالا مقدار bبرابر مدت زمان اجرای یک عمل انتصاب (max = 0)، مقدار c برابر مقدار زمان جابه‌جایی دو عدد و مقدار K برابر زمان یک مقایسه و یک عمل انتصاب است.

برای راحتی کار، هر عمل انتصاب و هر عمل مقایسه را برابر 1 در نظر می گیریم؛ پس داریم:

1+c+(n-i)2

برای به‌دست آوردن مقدار C باید زمان اجرای کد زیر را در نظر بگیریم

if (max != n - i) {

temp = a[max];

a[max] = a[n - i];

a[n - i] = temp;

}

همان‌طور که در کد موجود است ما یک عمل مقایسه داریم و سه عمل انتصاب که با توجه به توضیحات داده شده در بالا مقدار C را برابر 4 باید در نظر بگیریم.

حال اگر زمان مصرفی برای رسیدن به حلقه بیرونی را برابر d‌ در نظر بگیریم، زمان اجرای الگوریتم فوق از عبارت زیر به‌دست می‌آید:

d+ ?(5+2(n-i)

که سری فوق از 1 هست تا n. مقدارd در الگوریتم فوق برابر مقدار زمانی است که باید صرف شود تا دو متغیر را تعریف کنیم که آن را برابر 1 در نظر می‌گیریم.

اما جواب نهایی اینگونه به‌دست نمی‌آید. برای محاسبه پیچیدگی زمانی الگوریتم عملی که بیشتر از همه اجرا می‌شود را در نظر می‌گیرند و چون مقادیر دیگر کمتر اجرا می‌شوند از آنها چشم‌پوشی می‌کنند. در مثال بالا عمل مقایسه در حلقه داخلی بیشتر از همه اجرا می‌شود یعنی همان مقدار K.

چون به مقدار n-i بار در حلقه داخلی و به مقدار n در حلقه خارجی اجرا می‌شود پس اگر هر عمل مقایسه را برابر 1 در نظر بگیریم داریم (n-i)? که مقدار i‌ از 1 شروع می‌شود تا بهn-1. پس مقدار سری فوق برابر:n(n-1)/2 یاn2-2n (یعنی n به توان 2 منهای 2 ضربدر n

/ 3 نظر / 17 بازدید
معلم شرکتی

وبلاگ معلمان شرکتی(خرید خدماتی) http://kharidkhadamat.blogfa.com/

کانون محققان انرژی زایی

شفای ذهن‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌ « اگر خواستار شفای جسم هستيد، بايد نخست ذهن را شفا بخشيد » . ( افلاطون 427-347 ق. م ) وبلاگ پدیده های انرژی زایی و روح زایی با مطلب جدیدی پیرامون شفای ذهن به روز شده است از علاقه مندان و دوستداران به مطالب باطنی دعوت می نمائیم تا در این بحث با ما همراه شوند از شما سپاسگزاریم www.oloomebateni.com http://www.energyzaie.blogfa.com/

سمیرا

سلام دوست خوبم امیدوارم روز خوب و پر انرژی داشته باشی گلم وبلاگ خوبی داری خیلی قشنگه و خوشمله [گل] خیلی نازه مثه خودت پیش منم بیا با جدیدترین عکس های بانجو راستی آهنگ خانوم خانومی رو شنیدی که بانجو خونده اگه نشنیدی بدووووووووووو بیا دانلودش کن [گل][بوسه][خجالت][قلب][لبخند][گل] به دوستای گلت هم بگو دانلود کنن فدای محبتت منتظرتم www.banjomusic.us[گل] لطفاً من با نام "" جدیدترین عکس ها و آهنگ های بانجو "" لینک کنید و بگید که شما رو با چه نامی لینک کنم [گل]