সন্নিবেশ বাছাই

এই সাজানোর কৌশলটি কার্ড সাজানোর কৌশলের সাথে একই রকম, অন্য কথায়, আমরা সন্নিবেশ বাছাই পদ্ধতি ব্যবহার করে কার্ডগুলি সাজাই। এই কৌশলটির জন্য, আমরা ডেটা সেট থেকে একটি উপাদান বাছাই করি এবং ডেটা সেটে বাছাই করা উপাদানটিকে ফেরত ঢোকানোর জন্য একটি জায়গা তৈরি করতে ডেটা উপাদানগুলিকে স্থানান্তরিত করি৷

সন্নিবেশ সাজানোর কৌশলের জটিলতা

• সময়ের জটিলতা:সেরা ক্ষেত্রে O(n), গড় এবং সবচেয়ে খারাপ ক্ষেত্রে O(n^2)
• স্পেস জটিলতা: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)

ইনপুট - ডেটার একটি অ্যারে, এবং অ্যারের মোট সংখ্যা

আউটপুট &− সাজানো অ্যারে

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