Data Structure and Algorithms Insertion Sort

Insertion Sort সাধারণ sorting আলগরিদম । এটা আমাদের হাতে কার্ড খেলার সময় যেভাবে সাজানোর চেষ্টা করি । সেরকম একটা উপাই ।

এটাই মুল তথ্য ।

Insertion sort ভিত্তি করে একটা আইডিয়া এর উপর সেটা হলো :

একটা উপাদান (Element) ইনপুট থেকে নিয়ে ধরে ধরে দেখে প্রত্যেক iteration । যতক্ষণ না পর্যন্ত ওই উপাদানের নিদিষ্ট জায়গা খুজে না পায় । উলেখ্য যে যার অবস্থান একটি সাজানো array এর মধ্যে অবস্থিত ।

এই iteration এমন ভাবে চলে যে ১ম উপাদানের সাথে ২য় উপাদানের কম্পেয়ার করে swap এর মাধ্যমে চলে । এবং এর সঠিক জায়গা নির্ধারণ করে । ১ম উপাদান যদি ২য় উপাদান থেকে বড় হয় তাহলে তাদের জায়গা পরিবর্তন করবে । আবার যদি দেখা যায় ১ম উপাদানটা ছোট ২য় উপাদান থেকে তাহলে তাদের জায়গার কোনও পরিবর্তন করা যাবে না । উলেখ্য যে একটা একটা করে নিদিষ্ট উপাদানের সাথে কম্পেয়ার করতে হবে । নিচের উদাহরণটা দেখলে সম্পূর্ণ বিষয়টা ক্লিয়ার হবে ।

# আমরা এমন একটা array নিবো যেটা sorted না ।

Insertion Sort তুলনা করবে প্রথমের দুইটা উপাদানের মধ্যে অর্থাৎ 14 ও 33 এর মধ্যে ।

আমরা এখানে একটা জিনিশ লক্ষ্য করতে পারছি যে আগে থেকেই এখানে 14 ও 33 উভয়ই Ascending order এ সাজানো আছে । তাই 14 হলো sorted sub-list ।

Insertion Sort একধাপ এগিয়ে গেলো এবং 33 এবং 27 এর মধ্যে তুলনা করবে । এবং আমরা দেখতে পাচ্ছি যে 33 এবং 27 তারা তাদের সঠিক পজিশানে নেই ।

এটা Swap করবে 33 এবং 27 এর মধ্যে । এখানে আরো দেখতে হবে যে , sorted sub-list এর সাথে সঠিক পজিশানে আছে কি না । এখানে আমরা দেখতে পাচ্ছি যে , sub-list এ শুধুমাত্র একটি উপাদান 14 । এবং 27 হলো 14 থেকে বড় । অতঃ পর sorted sub-list সাজানো হয় swapping এর পর ।

এখন 14 এবং 27 sorted sub-list । Insertion Sort একধাপ এগিয়ে গেলো এবং 33 এবং 10 এর মধ্যে তুলনা করবে । এবং আমরা দেখতে পাচ্ছি যে 33 এবং 10 তারা তাদের সঠিক পজিশানে নেই ।

এটা Swap করবে 33 এবং 10 এর মধ্যে ।

এর মধ্যে 27 এবং 10 unsorted । একে sorted করতে হবে ।

একে অর্থাৎ 27 এবং 10 sorted করতে হবে ।

পুনরায় 14 এবং 10 unsorted । একে sorted করতে হবে ।

পুনরায় অর্থাৎ 14 এবং 10 sorted করতে হবে । ৩য় iteration এর পর । এখন আমাদের কাছে আছে ৪টা sorted sub-list ।

এভাবে insertion sort চলতেই থাকবে । যতক্ষণ না পর্যন্ত শেষ array উপাদান sorted sub-list না হয় ।

# Algorithm

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

# Pseudocode

INSERTION-SORT (A, n) ⊳ A[0 . . n]

for j ← 1 to n

do key ← A[ j]

i ← j — 1

while i > =0 and A[i] > key

do A[i+1] ← A[i]

i ← i — 1

A[i+1] = key

Time Complexity: O(n*n)

Auxiliary Space: O(1)

#JAVA_CODE :

class InsertionSort{
/*Function to sort array using insertion sort*/
void sort(int arr[]) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i — 1;

/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j — 1;
}
arr[j + 1] = key;
}
}

/* A utility function to print array of size n*/

static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + “ “);

System.out.println();
}

// Driver method
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6};

InsertionSort ob = new InsertionSort();
ob.sort(arr);

printArray(arr);
}

#PYTHON_CODE :

Algorithm insertion sort with visualize python Code

[code language=”python”]# Python program for implementation of Insertion Sort
def insertion_sort(list):
for j in range(1, len(list)):
value = list[j]
i = j-1
while i>= 0:
if value < list[i]:
list[i+1] = list[i]
i = i-1
list[i+1] = value
else:
break
return list
a = [2,1,4,3]
print(insertion_sort(a))[/code]