C++ এ সাজানো অ্যারে

এখানে আমরা সাজানো অ্যারের কিছু মৌলিক ধারণা দেখব। কিছু পরপর মেমরি অবস্থানে একই ধরণের ডেটা ধরে রাখার জন্য অ্যারেগুলি একজাতীয় ডেটা কাঠামো। কখনও কখনও আমাদের উপাদানগুলিকে ব্যবহার করার জন্য সাজাতে হবে। তা ছাড়া আমরা একটি সাজানো অ্যারে তৈরি করতে পারি। এটি সর্বদা বাছাই করা হবে।

এই ক্ষেত্রে আমরা সাজানো অ্যারেতে সন্নিবেশ এবং মুছে ফেলার জন্য অ্যালগরিদমগুলি দেখতে পাব। যদি আমরা এটিতে কিছু উপাদান সন্নিবেশ করি তবে এটি স্বয়ংক্রিয়ভাবে সাজানো অবস্থানে স্থাপন করা হবে। তাই সন্নিবেশ করার পরে আমাদের এটিকে আবার সাজানোর দরকার নেই। যখন আমরা মুছে ফেলি, এটি উপাদানগুলিকে মুছে ফেলবে এবং উপাদানগুলিকে ডানদিকে স্থানান্তর করে খালি স্থান পূরণ করবে। যেহেতু আমরা সাজানো অ্যারে ব্যবহার করছি, আমরা বাইনারি সার্চ অ্যালগরিদম ব্যবহার করব উপাদানটি মুছে ফেলার আগে খুঁজে বের করার জন্য৷

অ্যালগরিদম

insertSorted(arr, n, key):
Begin
   if n >= max size of the array, then return
   otherwise i := n – 1
   while i >= 0 and arr[i] > key, do
      arr[i + 1] := arr[i]
      i := i - 1
   done
   arr[i + 1] := key
   n := n + 1
End
deleteSorted(arr, n, key):
Begin
   pos := search key into arr
   if pos is -1, then item is not found, and return
   otherwise i := pos
   while i < n – 1, do
      arr[i] := arr[i + 1]
      i := i + 1
   done
   n := n + 1
End

উদাহরণ

#include <iostream>
#define MAX 10
using namespace std;
void display(int arr[], int n){
   for(int i = 0; i <n; i++){
      cout << arr[i] << " ";
   }
   cout << endl;
}
int search(int arr[], int low, int high, int key){
   if (high < low)
      return -1;
   int mid = (low + high) / 2; /*low + (high - low)/2;*/
   if (key == arr[mid])
      return mid;
   if (key > arr[mid])
      return search(arr, (mid + 1), high, key);
   return search(arr, low, (mid - 1), key);
}
void insertSorted(int arr[], int &n, int key){
   if (n >= MAX){
      cout << "No place to insert";
      return;
   }
   int i;
   for (i = n - 1; (i >= 0 && arr[i] > key); i--)
      arr[i + 1] = arr[i];
   arr[i + 1] = key;
   n = n + 1;
}
void deleteSorted(int arr[], int &n, int key){
   int key_pos = search(arr, 0, n, key);
   if(key_pos == -1){
      cout << "Element is not present." << endl;
      return;
   }
   int i;
   for (i = key_pos; i < n - 1; i++)
      arr[i] = arr[i + 1];
   n = n - 1;
}
int main() {
   int arr[MAX];
   int n = 0;
   insertSorted(arr, n, 10);
   insertSorted(arr, n, 20);
   insertSorted(arr, n, 30);
   insertSorted(arr, n, 40);
   insertSorted(arr, n, 50);
   insertSorted(arr, n, 60);
   insertSorted(arr, n, 70);
   display(arr, n);
   deleteSorted(arr, n, 35);
   deleteSorted(arr, n, 40);
   deleteSorted(arr, n, 60);
   display(arr, n);
}

আউটপুট

10 20 30 40 50 60 70
Element is not present.
10 20 30 50 70