সন্নিবেশ বাছাই হল একটি সাজানোর অ্যালগরিদম যা কার্ডের ডেকের মতো উপাদানগুলিকে সন্নিবেশ করে ডেটা সাজানোর জন্য ব্যবহৃত হয়। সমস্ত উপাদান বাম থেকে ডানে সাজানো হয় তারপর প্রথমটিকে ইতিমধ্যে সাজানো হিসাবে বিবেচনা করে, বামদিকে সাজানো তালিকায় বিশ্রাম ঢোকান। প্রতিটি উপাদান বাম তালিকার প্রতিটি উপাদানের সাথে তুলনা করা হয় যতক্ষণ না এটি সঠিক অবস্থানে ঢোকানো হয়।
সন্নিবেশ সাজানোর অ্যালগরিদম
-
int arr[5]={ 5,4,2,1,3 };
-
int i, j;
-
সূচী j=i+1 থেকে j<অ্যারে আকার
এ যান -
প্রতিটি উপাদানের জন্য arr[j] তালিকার arr[0 থেকে i] উপাদানের সাথে তুলনা করুন যতক্ষণ না উপাদান পাওয়া যায় যেমন arr[i]
-
তালিকায় arr[j] রাখুন এবং সমস্ত বৃহত্তর উপাদানকে এক অবস্থানে ডানদিকে সরান৷
-
সমাপ্তি
পুনরাবৃত্ত সন্নিবেশ বাছাই
-
যদি অ্যারের দৈর্ঘ্য 1 হয় তাহলে ফেরত দিন।
-
সূচক 0 থেকে অ্যারের আকার-1
এ পুনরাবৃত্তিমূলকভাবে সাজান উপাদান -
সাজানো অ্যারেতে শেষ উপাদান ঢোকান
উদাহরণ
ইনপুট − Arr[] ={ 5,7,2,3,1,4 }; দৈর্ঘ্য=6
আউটপুট − সাজানো অ্যারে:1 2 3 4 5 7
ব্যাখ্যা −
5 7 2 3 1 4 → 5 already sorted 5 7 2 3 1 4 → 7 at correct place 2 5 7 3 1 4 → 2 compared with 5,7 and inserted 2 3 5 7 1 4 → 3 compared with 5,7 and inserted 1 2 3 5 7 4 → 1 compared with 2,3,5,7 and inserted 1 2 3 4 5 7 → 4 compared with 5,7 and inserted
ইনপুট − Arr[] ={ 1, 2, 3, 3, 2 };
আউটপুট − সাজানো অ্যারে:1 2 2 3 3
ব্যাখ্যা −
1, 2, 3, 3, 2 → 1 already sorted 1, 2, 3, 3, 2 → 2 at correct place 1, 2, 3, 3, 2 → 3 at correct place 1, 2, 3, 3, 2 → 3 at correct place 1, 2, 2, 3, 3 → 2 compared with 3,3 and inserted
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
বুদবুদ সাজানোর পুনরাবৃত্তিমূলক পদ্ধতিতে, বেস কেস হল অ্যারের দৈর্ঘ্য =1। অন্যথায় লুপের জন্য একক ব্যবহার করে অ্যারেটি অতিক্রম করুন এবং সেই অনুযায়ী উপাদানগুলি অদলবদল করুন।
-
ইনপুট অ্যারে Arr[] এবং এর মধ্যে উপাদানের সংখ্যা হিসাবে দৈর্ঘ্য নিন।
-
ফাংশন recurbublSort(int arr[], int len) অ্যারে এবং এর দৈর্ঘ্য নেয় এবং বুদবুদ সাজানোর ব্যবহার করে অ্যারেটিকে পুনরাবৃত্তিমূলকভাবে সাজায়৷
-
একটি পরিবর্তনশীল তাপমাত্রা নিন।
-
যদি অ্যারের দৈর্ঘ্য 1 হয় তাহলে অকার্যকর রিটার্ন করুন।
-
অন্যথায় লুপের জন্য একক ব্যবহার করে অ্যারে অতিক্রম করুন এবং প্রতিটি উপাদানের জন্য arr[i]>arr[i+1], সেই উপাদানগুলি অদলবদল করুন।
-
temp=arr[i], arr[i]=arr[i+1] এবং arr[i+1]=temp সেট করুন।
-
এখন দৈর্ঘ্য 1 দ্বারা হ্রাস করুন কারণ আগের লুপটি সবচেয়ে বড় উপাদানটিকে শেষ অবস্থানে রেখেছিল।
-
RecurbublSort(arr,len) কে রিকার্সিভ কল করুন।
-
সমস্ত কলের শেষে, যখন লেন 1 হয়ে যায় তখন আমরা পুনরাবৃত্তি থেকে বেরিয়ে আসব এবং অ্যারেটি সাজানো হবে৷
-
প্রধান ভিতরে সাজানো অ্যারে প্রিন্ট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void recurbublSort(int arr[], int len){
int temp;
if (len == 1){
return;
}
for (int i=0; i<len-1; i++){
if (arr[i] > arr[i+1]){
temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
len=len-1;
recurbublSort(arr, len);
}
int main(){
int Arr[] = {21, 34, 20, 31, 78, 43, 66};
int length = sizeof(Arr)/sizeof(Arr[0]);
recurbublSort(Arr, length);
cout<<"Sorted array : ";
for(int i=0;i<length;i++){
cout<<Arr[i]<<" ";
}
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট তৈরি করবে
Sorted array : 20 21 31 34 43 66 78
