ইনসারশন সোর্ট কার্ড সোর্টিং টেকনিকের মতো। আমরা ডেটাসেট থেকে একটা এলিমেন্ট পিক করি এবং বাকি এলিমেন্টগুলো শিফট করে সেটার জন্য জায়গা বানাই, তারপর পিক করা এলিমেন্টটি সঠিক জায়গায় ইনসার্ট করি।
ইনসারশন সোর্টের জটিলতা
- টাইম কমপ্লেক্সিটি: বেস্ট কেস O(n), এভারেজ ও ওয়ার্স্ট কেস O(n²)
- স্পেস কমপ্লেক্সিটি: O(1)
ইনপুট এবং আউটপুট
Input: The unsorted list: 9 45 23 71 80 55
Output: Array before Sorting: 9 45 23 71 80 55
Array after Sorting: 9 23 45 55 71 80
অ্যালগরিদম
insertionSort(array, size)
Input: ডেটার অ্যারে, মোট এলিমেন্ট
Output: সর্ট করা অ্যারে
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
C++ উদাহরণ
#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 << "Enter the number of elements: "; cin >> n;
int arr[n];
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
