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
# 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))
