ইনসারশন সর্ট (Insertion sort) হলো একটি অ্যারে সর্ট করার সহজ পদ্ধতি। এই টেকনিক-এ, অ্যারেটি ভার্চুয়ালি সর্টেড এবং আনসর্টেড পার্টে ভাগ করা হয়। আনসর্টেড পার্ট থেকে একটি এলিমেন্ট বাছাই করা হয় এবং সেটি সর্টেড পার্টে সঠিক পজিশনে রাখা হয়।
অ্যারে এলিমেন্টগুলো ১ থেকে n পর্যন্ত ট্রভার্স করা হয়।
যদি পজিশন i-তে অ্যারে এলিমেন্ট এর প্রিডিসেসর (predecessor) থেকে বড় হয়, তবে সেটিকে সরানোর দরকার নেই।
যদি পজিশন i-তে অ্যারে এলিমেন্ট এর প্রিডিসেসর থেকে ছোট হয়, তবে সেটিকে বাম দিকে শিফট করতে হয় যতক্ষণ না আমরা সেটির চেয়ে ছোট একটি প্রিডিসেসর পাই অথবা অ্যারেতে বামেagu rasgos চলে যাই।
উদাহরণ
নিচের উদাহরণ দিয়ে উপরের ধারণাটি আরও স্পষ্টভাবে বুঝা যাবে। মান লিন, আমাদের নিচের অ্যারেটি আছে:
| 4 | 6 | 1 | 7 | 2 | 5 |
আমাদের ইনডেক্স ১ থেকে অ্যারে ট্রভার্স শুরু করতে হবে (কারণ ইনডেক্স ০-র কোনো প্রিডিসেসর নেই)।
ইন্ডেক্স ১-এ -
৬ তার প্রিডিসেসর থেকে বড়, তাই কিছু করার দরকার নেই।
| 4 | 6 | 1 | 7 | 2 | 5 |
ইন্ডেক্স ২-এ -
| 4 | 6 | 1 | 7 | 2 | 5 |
১ তার প্রিডিসেসর থেকে ছোট, তাই সেটিকে বাম দিকে শিফট করতে হবে যতক্ষণ না আমরা তার চেয়ে ছোট একটি প্রিডিসেসর পাই অথবা ইনডেক্স ০-এ পৌঁছাই। এই কেসে আমরা ইনডেক্স ০-এ পৌঁছাব।
| 1 | 4 | 6 | 7 | 2 | 5 |
ইন্ডেক্স ৩-এ -
| 1 | 4 | 6 | 7 | 2 | 5 |
ইন্ডেক্স ৪-এ -
| 1 | 4 | 6 | 7 | 2 | 5 |
২ কে বাম দিকে শিফট করুন, যতক্ষণ না ২-র চেয়ে ছোট একটি প্রিডিসেসর পাওয়া যায়।
| 1 | 2 | 4 | 6 | 7 | 5 |
ইন্ডেক্স ৫-এ -
| 1 | 2 | 4 | 6 | 7 | 5 |
৫ কে বাম দিকে শিফট করুন, যতক্ষণ না ৫-র চেয়ে ছোট একটি প্রিডিসেসর পাওয়া যায়।
| 1 | 2 | 4 | 5 | 6 | 7 |
এভাবে, আমরা সর্টেড অ্যারে পাই।
ইনসারশন সর্ট একটি ইন-প্লেস সর্টিং অ্যালগরिदম যার টাইম কমপ্লেক্সিটি O(n^2) এবং স্পেস কমপ্লেক্সিটি O(1)।
উদাহরণ
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i] # get each element
j = i-1
while j >= 0 and key < arr[j]: # keep shifting until reaching index 0 or getting an element smaller than key
arr[j + 1] = arr[j]
j = j-1
arr[j + 1] = key
arr = [4,6,1,7,2,5]
insertionSort(arr)
for i in range(len(arr)):
print(arr[i], end=" ")
আউটপুট
1 2 4 5 6 7
