ইন্সারশন সর্ট একটি সর্টিং অ্যালগরিদম যা এলিমেন্টগুলো তাসের পাতার মতো ইনসার্ট করে সাজায়। বামপাশের লিস্ট সর্টেড থাকে, ডানপাশের এলিমেন্টগুলো সেটি তুলনা করে সঠিক স্থানে ইনসার্ট করা হয়।
ইন্সারশন সর্ট অ্যালগরিদম
int arr[5] = {5,4,2,1,3};for j=i+1 to size-1→arr[j]কে বামপাশের সর্টেড লিস্টে সঠিক স্থানে ইনসার্ট করুন।
রিকারসিভ ইন্সারশন সর্ট
যদি অ্যারে দৈর্ঘ্য ১ হয়, ফেরত যান।
রিকারসিভভাবে ০ থেকে size-2 পর্যন্ত সর্ট করুন।
শেষ এলিমেন্টকে সর্টেড অ্যারেতে ইনসার্ট করুন।
উদাহরণ
ইনপুট − Arr[] = {5,7,2,3,1,4}, length=6
আউটপুট − সর্টেড অ্যারে: 1 2 3 4 5 7
ইনপুট − Arr[] = {1,2,3,3,2}
আউটপুট − সর্টেড অ্যারে: 1 2 2 3 3
প্রোগ্রামে ব্যবহৃত পদ্ধতি
বেস কেস: অ্যারে দৈর্ঘ্য = ১। অন্যথায় সিঙ্গল ফর লুপ দিয়ে স্ব্যাপ করে রিকারসিভ কল।
ইনপুট অ্যারে
Arr[]ও দৈর্ঘ্যlength।recurbublSort(int arr[], int len)ফাংশন রিকারসিভভাবে বাবল সর্ট করে (নোট: কোডে বাবল সর্ট ব্যবহৃত হয়েছে)।যদি
len == 1হয়, ফেরত যান।ফর লুপে
arr[i] > arr[i+1]হলে স্ব্যাপ করুন।len--করেrecurbublSort(arr, len)কল করুন।
উদাহরণ কোড
#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
