এই সোর্টিং টেকনিক কার্ড সর্টিং টেকনিকের সাথে মিলিত, অন্য কথায় আমরা কার্ড সর্ট করার সময় ইনসার্শন সর্ট মেকানিজম ব্যবহার করি। এই টেকনিকের জন্য, আমরা ডেটা সেট থেকে একটি এলিমেন্ট নিই এবং ডেটা এলিমেন্টগুলো শিফট করি নেওয়া এলিমেন্টটি ডেটা সেটে ফিরে ইনসার্ট করার জায়গা তৈরি করার জন্য।
ইনসার্শন সর্ট টেকনিকের জটিলতা
সময় জটিলতা: বেস্ট কেসে O(n), গড় এবং ওasst কেসে O(n²)
স্পেস জটিলতা: O(1)
ইনপুট − আনসর্টেড লিস্ট: 9 45 23 71 80 55 আউটপুট − সর্টিংয়ের পর অ্যারে: 9 23 45 55 71 80
অ্যালগরিদম
insertionSort(array, size)
ইনপুট: একটি ডেটা অ্যারে, এবং অ্যারেতে মোট সংখ্যা
আউটপুট: সর্টেড অ্যারে
শুরু
i := 1 থেকে size-1 পর্যন্ত
key := array[i]
j := i
যতক্ষণ j > 0 AND array[j-1] > key
array[j] := array[j-1]
j := j - 1
শেষ
array[j] := key
শেষ
শেষ
উদাহরণ কোড
#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];
j = i;
while(j > 0 && array[j-1] > key) {
array[j] = array[j-1];
j--;
}
array[j] = key;
}
}
int main() {
int n;
cout << "এলিমেন্টের সংখ্যা দিন: ";
cin >> n;
int arr[n];
cout << "এলিমেন্টগুলো দিন:" << endl;
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "সর্টিংয়ের আগে অ্যারে: ";
display(arr, n);
insertionSort(arr, n);
cout << "সর্টিংয়ের পর অ্যারে: ";
display(arr, n);
}
আউটপুট
এলিমেন্টের সংখ্যা দিন: 6 এলিমেন্টগুলো দিন: 9 45 23 71 80 55 সর্টিংয়ের আগে অ্যারে: 9 45 23 71 80 55 সর্টিংয়ের পর অ্যারে: 9 23 45 55 71 80
