اما اين الگوريتم چگونه كار مي‌كند. فرض كنيد داده‌هاي ما بصورت زير تعريف شده‌اند.
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; }
}
محاسبه پيچيدگي زماني الگوريتم
در اين الگوريتم نيز مانند باقي الگوريتم‌ها عمل غالب عمل مقايسه است. اما براي اين الگوريتم ما 2حالت در نظر مي‌گيريم يكي شرايط بد يكي در شرايط ميانگين، معمولا براي مقايسه پيچيدگي زماني چند الگوريتم شرايط ميانگين را ملاك قرار مي‌دهند.
بدترين شرايط
در اين شرايط آرايه بصورت نزولي مرتب شده است و قرار است كه با مرتب‌سازي درجي آن را به صورت صعودي مرتب كنيم. در اين شرايط هر بار كه حلقه بيروني براي انتخاب عنصر بعدي يا همان عنصر iم اجرا مي‌شود. اين عنصر از تمامي‌عناصر موجود در مجموعه بدست آمده در آن مرحله كه i-1 عضو دارد كوچك‌تر است، بنابراين تعداد مقايسهها در حلقه دروني until ـ repeat برابر i-1 است. با توجه به مطالب گفته شده تعداد كل مقايسهها در زمان اجراي حلقه بيروني for از فرمول زير به دست مي‌آيد.
Zigma i=2 to n (i-1) = n(n-1)/2
حالت ميانگين
هر بار كه حلقه بيروني اجرا مي‌شود، براي قرار دادن عنصر iم در مجموعه i حالت وجود دارد. يعني در يكي از خانه‌هاي 1 تا i مي‌تواند قرار بگيرد. حال اگر عنصر iم بصورت تصادفي در يكي از خانه‌هاي 1 تا iم بنشيند احتمال تعلق عنصر iم به آن خانه برابر است. تعداد مقايسهها با توجه به محل قرارگيري عنصر iم در محل iم به صورت جدول زير نشان داده شده است:
محل تعداد مقايسه
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 است، پس مي‌توان گفت اين الگوريتم از مرتبه n2 است.
اگر نتايج بدترين حالت و حالت ميانگين را با هم مقايسه كنيم مي‌بينيم كه تعداد مقايسهها در حالت ميانگين نصف بدترين حالت است.
امير بهاالدين سبط الشيخ
