تبلیغات
الکترونیک - آموزش - ++C

الکترونیک

دوشنبه 4 آذر 1387

آموزش - ++C

نویسنده: محسن   

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

این مرتب سازی جالب توسط شخص SHELL اختراع شد. فرض کنید می خواهیم یک رشته dafcbe را مرتب کنیم::
شروع: 5487  5487  5487  5487  5487  5487  5487  5487  5487 d 5487  5487  5487  5487  5487  5487  5487  5487 a 5487  5487  5487  5487  5487  5487  5487  5487 f 5487  5487  5487  5487  5487  5487  5487  5487  5487  5487 c 5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487b 5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487 e
1: 5487  5487  5487  5487  5487  5487  5487  5487 5487  5487 5487  5487  5487 c 5487  5487  5487  5487  5487  5487  5487  5487 a 5487  5487  5487  5487  5487  5487  5487  5487 e 5487  5487  5487  5487  5487  5487  5487  5487  5487  5487d 5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487b 5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487 f 5487
2: 5487  5487  5487  5487  5487  5487  5487  5487  5487 5487  5487 5487  5487 c 5487  5487  5487  5487  5487  5487  5487  5487 a 5487  5487  5487  5487  5487  5487  5487  5487 b 5487  5487  5487  5487  5487  5487  5487  5487  5487  5487d 5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487e 5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487 f
3: 5487  5487  5487  5487  5487  5487  5487  5487  5487  5487 5487 5487  5487 a 5487  5487  5487  5487  5487  5487  5487  5487 b 5487  5487  5487  5487 5487  5487  5487  5487  5487c 5487  5487 5487  5487  5487  5487  5487  5487  5487  5487 d 5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487e 5487  5487  5487  5487  5487  5487  5487  5487  5487  5487  5487 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)
{
 5487  5487const int ct=count;
 5487  5487register int i, j, step, k=0, p;
 5487  5487int dis[ct];
 5487  5487char x;
 5487  5487dis[0]=count/2;
 5487  5487while(dis[k]>1){
 5487  5487  5487 k++;
 5487  5487  5487 dis[k]=dis[k-1]/2;
 5487  5487}
 5487  5487for(i=0 ; i<=k ; i++){
 5487  5487  5487 step=dis[i];
 5487  5487  5487 for(j=0 ; j 5487  5487  5487  5487  5487x=item[j];
 5487  5487  5487  5487  5487p=j-step;
 5487  5487  5487  5487  5487while( p>=0 && x < item[p] ){
 5487  5487  5487  5487  5487  5487 item[p+step]=item[p];
 5487  5487  5487  5487  5487  5487 p-=step;
 5487  5487  5487  5487  5487}
 5487  5487  5487  5487  5487item[p+step]=x;
 5487  5487  5487 }
 5487  5487}
}
توضیح:
item 5487 همان آرایه ورودی است(شما میتوانید رشته ارسال کند compiler خودش با تبدیل انواع حل میکند ) و count طول آرایه ورودی است (برای رشته از تابع 5487 strlen استفاده کنید). کاراکتر x نیز برای جابجایی در آرایه است و متغییرهای خط 4 چون گامهای حلقه و پر کاربردند برای بهبود سرعت register انتخاب شدند مخصوصا شرط 5487 [xهدف از انتخاب const ct این بود تا بتوانیم آرایه dis 5487 را تعریف کنیم(به جای x در
  • آرایه نمی توان متغییر نهاد) متوانستیم از عملگر new استفاده کنبم.
محاسبه زمان:
در روشهای حبابی و درج با n داده, ناظر n2 جابجایی در آرایه 5487 هستیم ولی در این روش شاهد n1.2 هستیم (این اعداد با محاسبه نه چندان زیاد محاسبه میشوند در مورد این مبحث در آینده بحث میکنیم ).

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

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

 5487(*)یامهدی ادرکنی (*)
یا حق
bay
 5487@};-

نظرات() 
 
لبخندناراحتچشمک
نیشخندبغلسوال
قلبخجالتزبان
ماچتعجبعصبانی
عینکشیطانگریه
خندهقهقههخداحافظ
سبزقهرهورا
دستگلتفکر

نویسندگان

آمار وبلاگ

  • کل بازدید :
  • بازدید امروز :
  • بازدید دیروز :
  • بازدید این ماه :
  • بازدید ماه قبل :
  • تعداد نویسندگان :
  • تعداد کل پست ها :
  • آخرین بازدید :
  • آخرین بروز رسانی :