এই বাছাই কৌশলটি কার্ড সাজানোর কৌশলের সাথে একই রকম, অন্য কথায় আমরা সন্নিবেশ বাছাই পদ্ধতি ব্যবহার করে কার্ডগুলি সাজাই। এই কৌশলটির জন্য, আমরা ডেটা সেট থেকে একটি উপাদান বাছাই করি এবং ডেটা সেটে বাছাই করা উপাদানটিকে ফেরত ঢোকানোর জায়গা তৈরি করতে ডেটা উপাদানগুলিকে স্থানান্তরিত করি৷
সন্নিবেশ সাজানোর কৌশলের জটিলতা
-
সময়ের জটিলতা:সেরা ক্ষেত্রে O(n), গড় এবং সবচেয়ে খারাপ ক্ষেত্রে O(n2)
-
স্থান জটিলতা:O(1)
Input − The unsorted list: 9 45 23 71 80 55 Output − Array after Sorting: 9 23 45 55 71 80
অ্যালগরিদম
ইনসার্শন সর্ট(অ্যারে, সাইজ)
ইনপুট :ডেটার একটি অ্যারে, এবং অ্যারের মোট সংখ্যা
আউটপুট :সাজানো অ্যারে
Begin
for i := 1 to size-1 do
key := array[i]
j := i
while j > 0 AND array[j-1] > key do
array[j] := array[j-1];
j := j – 1
done
array[j] := key
done
End উদাহরণ কোড
#include<iostream>
using namespace std;
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void insertionSort(int *array, int size) {
int key, j;
for(int i = 1; i<size; i++) {
key = array[i];//take value
j = i;
while(j > 0 && array[j-1]>key) {
array[j] = array[j-1];
j--;
}
array[j] = key; //insert in right place
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
insertionSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
} আউটপুট
Enter the number of elements: 6 Enter elements: 9 45 23 71 80 55 Array before Sorting: 9 45 23 71 80 55 Array after Sorting: 9 23 45 55 71 80
