ইন্সারশন সর্ট হল একটি সর্টিং অ্যালগরিদম যা একটি ইন-প্লেস কম্পারিজন-বেসড অ্যালগরিদম।
এই অ্যালগরিদমটি উপাদানগুলিকে সোর্টেড সাব-অ্রেতে তাদের সঠিক অবস্থানে রাখে, অর্থাৎ উপাদানের পূর্ববর্তী সাব-অ্রে যা ইতিমধ্যে সোর্টেড।
এলগরিদম
স্টেপ ১ − ১ থেকে n-1 পর্যন্ত লুপ চালাও এবং নিচের কাজগুলো করো −
স্টেপ ২.১ − i পজিশনের উপাদানটি নির্বাচন করো, array[i]।
স্টেপ ২.২ − উপাদানটিকে সোর্টেড সাব-অ্রে array[0] থেকে arr[i]-তে এর সঠিক পজিশনে ইনসার্ট করো।
এলগরিদম বোঝার জন্য একটি উদাহরণ নিই
অ্যারে = [34, 7, 12, 90, 51]
i = 1 এর জন্য, arr[1] = 7, সাবঅ্রে arr[0] - arr[1]-এ এর পজিশনে রাখা।
[7, 34, 12, 90, 51]
i = 2 এর জন্য, arr[2] = 12, সাবঅ্রে arr[0] - arr[2]-এ এর পজিশনে রাখা।
[7, 12, 34, 90, 51]
i = 3 এর জন্য, arr[3] = 90, সাবঅ্রে arr[0] - arr[3]-এ এর পজিশনে রাখা।
[7, 12, 34, 90, 51]
i = 4 এর জন্য, arr[4] = 51, সাবঅ্রে arr[0] - arr[4]-এ এর পজিশনে রাখা।
[7, 12, 34, 51, 90]
এখানে, আমরা দেখব কিভাবে রিকারসিভ ইন্সারশন সর্ট কাজ করে। এটি বিপরীত ভিত্তিতে কাজ করে অর্থাৎ আমরা recursiveInsertionSort() ফাংশনটি n-1 উপাদানের অ্যারে সর্ট করার জন্য রিকারসিভভাবে কল করব। এবং তারপর এই সোর্টেড অ্যারেটিতে (যেটি ফাংশনটি রিটার্ন করবে) 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
