انجمن تخصصی فارسی هوش مصنوعی
اولين و بزرگترين وب سايت دانلود فارسي
روش مرتب سازی shellsort مشاهده در قالب پی دی اف چاپ فرستادن به ایمیل
آموزش - ++C
نوشته شده توسط بهنام مشرف   
چهارشنبه, 23 مرداد 1387 14:35
با نام خدا
سلام
چون دیدم اغلب برای روبوکاپ باید چند امتیاز sort شود تصمیم به آموزش دو روش sort گرفتم:
1.shellsort
2.quicksort
چون حجم مطلب زیاد است در اینجا shellsort را توضیح میدهم و quicksort را در پست بعدی ارائه میدهم.

این مرتب سازی جالب توسط شخص SHELL اختراع شد. فرض کنید می خواهیم یک رشته dafcbe را مرتب کنیم:
شروع:                  d                a                f                    c                         b                      e
1:                        c                a                e                   d                         b                      f 
2:                        c                a                b                   d                         e                      f
3:                        a                b                c                   d                         e                      f
در مرحله اول داده ها با فاصله 3 و در مرحله 2 با فاصله 2 و در مرحله 1 با فاصله 1 و در مرحله 4 با فاصله صفر مقایسه و مرتب سازی میشوند (منظور از فاصله 2 یعنی مثلا داده 1 با داده 3 (1+2=3)) اگر دقت کنید میبینید با این کار داده ها برای مرحله آخر که فاصله 1 است آماده میشوند. فاصله نیز با تقسیم مکرر داده ها بر دو حاصل میشود تا به صفر برسد(تقسیمها با int است) که در مثال مرحله 4 صفر شده است. مثلا با n=5 داده ابتدا فاصله 2 (n=n/2) بعد 1 (n=n/2) و بعد صفر انتخاب میشود.
حتما خوب توضیح ندادم اما حتما با مطالعه کد زیر متوجه میشوید ولی سوالات شما مکمل بحث خواهد بود

void shell(int *itemp,int count)
{
   const int ct=count;
   register int i, j, step, k=0, p;
   int dis[ct];
   char x;
   dis[0]=count/2;
   while(dis[k]>1){
      k++;
      dis[k]=dis[k-1]/2;
   }
   for(i=0 ; i<=k ; i++){
      step=dis[i];
      for(j=0 ; j<count ; j++){
         x=item[j];
         p=j-step;
         while( p>=0 && x < item[p] ){
            item[p+step]=item[p];
            p-=step;
         }
         item[p+step]=x;
      }
   }
}
توضیح:
item  همان آرایه ورودی است(شما میتوانید رشته ارسال کند compiler خودش با تبدیل انواع حل میکند ) و count طول آرایه ورودی است (برای رشته از تابع  strlen استفاده کنید). کاراکتر x نیز برای جابجایی در آرایه است و متغییرهای خط 4 چون گامهای حلقه و پر کاربردند برای بهبود سرعت register انتخاب شدند مخصوصا شرط  [x<item[p که از کارایی الگوریتم میکاهد.
هدف از انتخاب const ct این بود تا بتوانیم آرایه dis  را تعریف کنیم(به جای x در
  • آرایه نمی توان متغییر نهاد) متوانستیم از عملگر new استفاده کنبم.
محاسبه زمان:
در روشهای حبابی و درج با n داده, ناظر n2 جابجایی در آرایه  هستیم ولی در این روش شاهد n1.2 هستیم (این اعداد با محاسبه نه چندان زیاد محاسبه میشوند در مورد این مبحث در آینده بحث میکنیم ).

پس از سوالات شما و جا افتادن یحث به quicksort  می پردازیم.

در آینده به مبحث وقفه ها (interrupt)  که بسیار مهم است و از پیاده سازی آن کمتر کسی میداند می پردازیم که میتوانید با ++C از پرینتر و جابجا کردن هدر هارد به مکان دلخواه و reset هارد و تمام میانبرها با صفحه کلید و... استفاده کنید.

 (*)یامهدی ادرکنی (*)
یا حق
bay
 @};-
 
انجمن تخصصی فارسی هوش مصنوعی
اولين و بزرگترين وب سايت دانلود فارسي

نظرسنجي

از کدام نسخه از سرور روبوکاپ بیشتر خوشتان میاد؟
 

مسابقات پیش رو

مسابقه خوارزمی

زمان دانش آموزی:

22 الی 24 آبان 1387
دانشگاه خواجه نصیر الدین-تهران

زمان دانشجویی:
17 الی 19 آبان 1387
مجتمع عصر انقلاب-شهریار

(نتایج مسابقه)


China Open 2008
زمان و مکان:
15 الی 17 آذر 1387
شهر ژونگ شا-چین
Powered By Joomla! And Translation By JoomFa Team
Template Design by: Omid Pilevar | Host by: Hostiran.net