|
آموزش -
++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
|