کارت‌های مرا مرتب کن

اما این الگوریتم چگونه کار می‌کند. فرض کنید داده‌های ما بصورت زیر تعریف شده‌اند.

A1, A2, A3, … , An

ابتدا عنصر A1 و A2 را انتخاب می‌کنیم سپس این دو عنصر را با هم مقایسه می‌کنیم و در جای مناسب نسبت به هم قرار می‌دهیم به طوری که مجموعه حاصل از انتخاب عناصر A1 و A2 مرتب باشد. سپس در مرحله بعد عنصر A3 را انتخاب می‌کنیم و آن را با A1 و A2 مقایسه می‌کنیم و در جای مناسب خود قرار می‌دهیم به طوری که مجموعه حاصل مرتب باشد. این عمل را آنقدر ادامه می‌دهیم تا به عنصر nام برسیم.

بگذارید الگوریتم بالا را با یک مثال عددی بیشتر بررسی بکنیم، داریم:

12,1,15,23

در مرحله اول 12 و 1 را انتخاب می‌کنیم سپس آنها را نسبت به هم در جای مناسبی قرار می‌دهیم تا مجموعه حاصل مرتب باشد که حاصل بصورت زیر می‌شود:

1,12

سپس عدد 15 را انتخاب می‌کنیم و آن را طوری در مجموعه قبلی قرار می‌دهیم که ترتیب عناصر به‌هم نخورد، یعنی عنصر 15 را در جای مناسب خود نسبت به اعد اد 12 و 1 قرار می‌دهیم که خروجی این مرحله بصورت زیر می‌شود:

1,12,15

در مرحله بعدی که عدد 23 را انتخاب می‌کنیم خروجی به صورت زیر می‌شود:

1,12,15,23

2 نکته در مورد این الگوریتم حائز اهمیت هست؛

اول این که این الگوریتم مانند روش مرتب‌سازی انتخابی نیاز به حافظه اضافی ندارد.

دوم این که همان طور که در مثال بالا مشاهده می‌کنید، هر مرحله که این الگوریتم جلو می‌رود مجموعه حاصل مرتب شده است و این خودش یکی از مزیت‌های این الگوریتم است.

شبه کد این الگوریتم به زبان ++C بصورت زیر است:

void InsertSort(int a[]،int n){

int i،j،temp;

for(i=1;i«n;++i){

temp = a[i];

j = i - 1;

while(j»=0 && temp« a[j]){

a[j+1] = a[j];

--j; }

a[j+1] = temp; }

}

Zigma i=2 to n (i-1) = n(n-1)/2

i 1

i-1 2

i-2 3

...

2 i-1

1 i-1

اگر عنصر iم در محل اول آرایه یعنی 1 قرار بگیرد تعداد مقایسه برابر i-1است، بخاطر این‌که در حلقه درونی مقدار j برابر صفر می‌گردد و شرط اول حلقه while اشتباه می‌شود و شرط دوم دیگر محاسبه نمی‌شود. با این استدلال برای مقدار مشخص i میانگین تعداد مقایسه‌ای که برای درج عنصر i باید انجام شود از روش زیر محاسبه می‌شود.

1(1/i)+2(2/i)+…( i-1)(1/i)+(i-1)(1/i)

= 1/I Zigma k

= 1 to I -1 (k+( i-1)/i)

= (i-1)(i)/2i + (i-1)/i

=( i+1)/2 – 1/i

پس میانگین تعداد مقایسه برای مرتب کردن آرایه مورد نظر در روش مرتب‌سازی درجی به صورت زیر محاسبه می‌شود:

Zigma I = 2 to n (( i+1)/2 – 1/i)

=(n+4)(n-1)/4–Zigma i=2 to n (1/i)

محاسبه سری با جمله عمومی1/i برابر Ln است(در ریاضی اثبات شده است)، پس عبارت درجه بیشتر در بالا مقدار:

(n+4)(n-1)/4

همان‌طور که مشخص است حد بی نهایت عبارت بالا برابر n به توان 2 تقسیم بر 4 است، پس می‌توان گفت این الگوریتم از مرتبه n² است.

اگر نتایج بدترین حالت و حالت میانگین را با هم مقایسه کنیم می‌بینیم که تعداد مقایسه‌‌ها در حالت میانگین نصف بدترین حالت است.

امیر بهاالدین سبط الشیخ