কোন একটা লিস্ট নেওয়া, এবং ঐ লিস্টকে ক্রম অনুযায়ী সাজানোটাই হচ্ছে সর্টিং। ক্রম টা বড় থেকে ছোট হতে পারে বা ছোট থেকে বড় হতে পারে। অনেক গুলো সর্টিং অ্যালগরিদম রয়েছে। Insertion Sort তাদের মধ্যে একটি। আর কোন একটা কাজ করার ধাপ গুলোই হচ্ছে অ্যালগরিদম।
Insertion Sort এর ব্যাসিক আইডিয়া হচ্ছে লিস্টটাকে দুইটা অংশে ভাগ করা। একটা হচ্ছে সর্টেড অংশ, আরেকটা হচ্ছে আনসর্টেড অংশ। প্রতিটা ধাপে আনসর্টেড অংশ থেকে একটা নাম্বার নিয়ে সর্টেড অংশে রাখা হয়। রাখার সময় দেখা হয় যেন সর্টেড অংশ সব সময় সর্টেড থাকে।
ধরি আমাদের কাছে রয়েছেঃ 4, 8, 2, 7, 1। আমরা এই নাম্বার গুলোকে ছোট থেকে বড় আকারে সাজাবো।
| 4 | 8 | 2 | 7 | 1 |
আমরা চারটাকে প্রথমে সর্টেড অংশে রাখব। যেহেতু একটাই সংখ্যা রয়েছে, তাই বলা যায় এটি সর্টেড। আর কিছু আমাদের করতে হবে না। এরপর 8 সর্টেড অংশে রাখব। এরপর সর্টেড অংশের বাকি সংখ্যা গুলোর সাথে তুলনা করব। ঐখানে একটিই সংখ্যা রয়েছে। 4 এবং এটি 8 থেকে ছোট। তাই আমাদের আর কিছুই করতে হবে না।
| 4 | 8 | 2 | 7 | 1 |
এরপর আমরা 2 সর্টেড অংশে রাখব।
| 4 | 8 | 2 | 7 | 1 |
এরপর এখন 2 এর সাথে 8 এর তুলনা করে দেখব এরা ভুল জায়গায় রয়েছে। তাই এদের জায়গা পরিবর্তন করব।
| 4 | 2 | 8 | 7 | 1 |
এরপর আবার 2 এবং 4 এর তুলনা করে দেখার পর দেখব 4 বড়। তাই 4 এর জায়গায় 2 রাখব এবং 2 এর জায়গায় 4।
| 2 | 4 | 8 | 7 | 1 |
এরপর আমরা 7 কে সর্টেড অংশে রাখব।
| 2 | 4 | 8 | 7 | 1 |
এরপর দেখতে পাবো 7 থেকে 8 বড়। তাই 7 এর যায়গায় 8 এবং 8 এর জায়গায় 7 রাখব
| 2 | 4 | 7 | 8 | 1 |
এরপর 1 কে আমরা সর্টেড অংশে নিয়ে আসব।
| 2 | 4 | 7 | 8 | 1 |
আমরা দেখতে পাবো 8 থেকে এক ছোট। তাই একটার যায়গায় একটা রাখব।
| 2 | 4 | 7 | 1 | 8 |
আবার 7 এবং 1 এর তুলনা করে দেখব এরাও ভুল যায়গায় রয়েছে। তাই এদের জায়গা অদল বদল করব।
| 2 | 4 | 1 | 7 | 8 |
এরপর আবার 4 এর সাথে যায়গা অদল বদল করতে হবেঃ
| 2 | 4 | 1 | 7 | 8 |
এবং শেষে 2 এর সাথে যায়গা অদল বদল করার পর আমরা সর্টেড লিস্ট পেয়ে যাবোঃ
| 1 | 2 | 4 | 7 | 8 |
এতটুকু দেখার পর অ্যালগরিদমটা নিজের মত করে লিখে নেওয়ার চেষ্টা করতে পারেন। অ্যালগরিদমটিঃ
for i = 1 to length(A)
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1
end while
end for
সি অথবা সি++ এ আমরা এভাবে ইনসার্শন সর্ট ইমপ্লিমেন্ট করতে পারিঃ
#include <stdio.h>
#include <math.h>
int main()
{
int i, j, key;
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
// Insertion Sort
for (i = 1; i < n; i++) { key = arr[i]; j = i-1; while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
// printing sorted list
for (i=0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}