در تپش این هفته، ماجرای فریب و تعرض در پوشش عرفانهای دروغین و رمالی را بررسی کردیم
مرتبسازی به روش انتخابی
لطفا به ترتیب قد وارد شوید!
یکی از الگوریتمهای پرکاربرد در دنیای برنامهنویسی الگوریتمهای مرتبسازی است و اهمیت این موضوع در تمام زمینههای برنامهنویس مشهود است. وقتی در شبکه مشغول دریافت اطلاعات هستید، اطلاعات باید بهصورت مرتب در کنار هم قرار گرفته تا نمایشدهنده اطلاعات اصلی باشند. اگر میخواهید بیشترین درآمد را بین کارمندان پیدا کنید، پس باید اطلاعات کارمندان را بر اساس حقوق دریافتی خود مرتب کنید. اگر کوچکترین عضو یک دانشکده را میخواهید، اول باید اطلاعات دانشجویان را بر اساس تاریخ تولد بهصورت نزولی مرتب کنید.
دو نوع مرتبسازی داریم: یکی بهصورت صعودی و دیگری بهصورت نزولی. منظور از صعودی این است که عناصر بهترتیب از بزرگترین تا کوچکترین عنصر مرتب میشوند و بهعکس منظور از نزولی این است که عناصر بهترتیب از کوچکترین تا بزرگترین عنصر در آرایه جای میگیرند.
یکی از سادهترین الگوریتمهای مرتبسازی، مرتبسازی بهروش انتخابی است. امااین الگوریتم چگونه دادهها را مرتب میکند؟
ابتدا بزرگترین عدد را در مجموعه پیدا کرده وسپس آن را با آخرین عنصر آرایه یعنی جابهجا میکنیم. حال از بین عناصر [
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) است.حد این عبارت در بینهایت برابر n2 است، پس میتوان گفت که مرتبه اجرایی الگوریتم فوق n2 (n به توان 2) است یا
(O(n2. این نشان میدهد استفاده از این الگوریتم برای مجموعه دادههای بزرگ اصلا به صرفه نیست.
تازه ها
گوناگون
پیشنهاد سردبیر
گزارش «جامجم» درباره دستاوردهای زبان فارسی در گفتوگو با برخی از چهرههای ادب معاصر
فارسی، زبان گفتوگوی جهان
معاون وزیر بهداشت:
