পাইথনে সন্নিবেশ বাছাই কি?

সন্নিবেশ বাছাই একটি অ্যারে সাজানোর সহজ পদ্ধতি। এই কৌশলে, অ্যারেটি কার্যত সাজানো এবং সাজানো অংশে বিভক্ত হয়। সাজানো অংশ থেকে একটি উপাদান বাছাই করা হয় এবং সাজানো অংশে সঠিক অবস্থানে রাখা হয়।

• অ্যারের উপাদানগুলি 1 থেকে n পর্যন্ত অতিক্রম করা হয়।

• যদি i অবস্থানে থাকা অ্যারের উপাদানটি তার পূর্বসূরীর থেকে বড় হয়, তাহলে এটিকে সরানোর প্রয়োজন নেই৷

• যদি i অবস্থানে থাকা অ্যারের উপাদানটি তার পূর্বসূরীর থেকে কম হয়, তাহলে এটিকে বাম দিকে সরাতে হবে যতক্ষণ না আমরা এটির থেকে ছোট একটি পূর্বসূরী খুঁজে পাই বা যদি আমরা অ্যারের সবচেয়ে বাম অবস্থানে না পৌঁছাই৷

উদাহরণ

আমরা একটি উদাহরণের সাহায্যে উপরের ধারণাটি আরও স্পষ্টভাবে বুঝতে পারি। ধরুন আমাদের নিচের অ্যারে আছে −

আমাদের সূচী 1 থেকে অ্যারে অতিক্রম করা শুরু করতে হবে (কারণ সূচক 0 এর কোনো পূর্বসূরি নেই)।

সূচী 1 এ −

6 এর পূর্বসূরীর চেয়ে বড়, তাই কিছুই করার দরকার নেই।

সূচী 2 এ −

1 এর পূর্বসূরীর থেকে কম, তাই আমাদের এটিকে বাম দিকে সরাতে হবে যদি না আমরা এটির থেকে ছোট একটি পূর্বসূরি খুঁজে পাই বা যদি আমরা সূচক 0-এ পৌঁছে যাই। এই ক্ষেত্রে আমরা সূচক 0-এ পৌঁছাব।

সূচী 3 এ −

সূচী 4 এ −

2 বাম দিকে সরান, যতক্ষণ না আমরা 2-এর থেকে ছোট একটি পূর্বসূরী খুঁজে পাই।

5 সূচকে −

5 বাম দিকে সরান, যতক্ষণ না আমরা 5-এর থেকে ছোট একটি পূর্বসূরী খুঁজে পাই।

তাই, আমরা সাজানো অ্যারে পাই।

সন্নিবেশ বাছাই হল 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 &lit; 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