روش مرتب سازی shellsort

با نام خدا
سلام
چون دیدم اغلب برای روبوکاپ باید چند امتیاز 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 را تعریف کنیم(به جای y در [y] آرایه نمی توان متغییر نهاد) متوانستیم از عملگر new استفاده کنبم.
محاسبه زمان:
در روشهای حبابی و درج با n داده, ناظر n² جابجایی در آرایه هستیم ولی در این روش شاهد n^1.2 هستیم (این اعداد با محاسبه نه چندان زیاد محاسبه میشوند در مورد این مبحث در آینده بحث میکنیم ).

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

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

منبع : اولین انجمن تخصصی فاری زبان آموزش روبوکاپ - روش مرتب سازی shellsort