সন্নিবেশ বাছাই হল একটি সাজানোর অ্যালগরিদম যা একটি অভ্যন্তরীণ তুলনা-ভিত্তিক অ্যালগরিদম।
অ্যালগরিদম সাজানো সাব-অ্যারেতে তাদের অবস্থানে উপাদানের দ্বারা কাজ করে অর্থাৎ উপাদানের পূর্বে থাকা সাব-অ্যারে যা একটি সাজানো সাব-অ্যারে।
অ্যালগরিদম
ধাপ1 − 1 থেকে n-1 পর্যন্ত লুপ করুন এবং −
করুনধাপ 2.1 - অবস্থান i, অ্যারে[i] এ উপাদান নির্বাচন করুন।
ধাপ 2.2 − বাছাই করা সাব-অ্যারে অ্যারে[0] তে অ্যার[i] করতে উপাদানটিকে তার অবস্থানে প্রবেশ করান।
আলগোরিদম বোঝার জন্য একটি উদাহরণ নেওয়া যাক
অ্যারে =[৩৪, ৭, ১২, ৯০, ৫১]
আমার জন্য =1, arr[1] =7, subarray arr[0] - arr[1]-এ তার অবস্থানে স্থাপন করা।
[7, 34, 12, 90, 51]
i =2 এর জন্য , arr[2] =12, subarray arr[0] - arr[2]-এ তার অবস্থানে স্থাপন করা।
[7, 12, 34, 90, 51]
i =3 এর জন্য , arr[3] =90, subarray arr[0] - arr[3]-এ তার অবস্থানে স্থাপন করা।
[7, 12, 34, 90, 51]
আমার জন্য =4, arr[4] =51, subarray arr[0] - arr[4]-এ তার অবস্থানে স্থাপন করা।
[7, 12, 34, 54, 90]
এখানে, আমরা দেখব কিভাবে রিকার্সিভ ইনসার্টেশন সর্ট কাজ করে। এটি একটি বিপরীত ভিত্তিতে কাজ করে যেমন বর্তমান পুনরাবৃত্তির তুলনায় n-1 উপাদান অ্যারে সাজানোর জন্য আমরা recursively recursiveInsertionSort() ফাংশনকে কল করব। এবং তারপর এই সাজানো অ্যারেতে যা ফাংশন দ্বারা ফেরত দেওয়া হবে, আমরা সাজানো অ্যারের মতো তার অবস্থানে nth উপাদান সন্নিবেশ করব।
পুনরাবৃত্ত সন্নিবেশ সাজানোর জন্য প্রোগ্রাম -
উদাহরণ
#include <stdio.h>
void recursiveInsertionSort(int arr[], int n){
if (n <= 1)
return;
recursiveInsertionSort( arr, n-1 );
int nth = arr[n-1];
int j = n-2;
while (j >= 0 && arr[j] > nth){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = nth;
}
int main(){
int array[] = {34, 7, 12, 90, 51};
int n = sizeof(array)/sizeof(array[0]);
printf("Unsorted Array:\t");
for (int i=0; i < n; i++)
printf("%d ",array[i]);
recursiveInsertionSort(array, n);
printf("\nSorted Array:\t");
for (int i=0; i < n; i++)
printf("%d ",array[i]);
return 0;
} আউটপুট
Unsorted Array: 34 7 12 90 51 Sorted Array: 7 12 34 51 90
