सी ++ में क्रमबद्ध सरणी

यहां हम क्रमबद्ध सरणियों की कुछ बुनियादी अवधारणाएँ देखेंगे। कुछ लगातार मेमोरी स्थानों में एक ही तरह के डेटा को रखने के लिए सरणियाँ सजातीय डेटा संरचना हैं। कभी-कभी हमें उनका उपयोग करने के लिए तत्वों को क्रमबद्ध करने की आवश्यकता होती है। इसके अलावा हम एक क्रमबद्ध सरणी बना सकते हैं। इसे हमेशा क्रमबद्ध किया जाएगा।

इस मामले में हम सॉर्ट किए गए सरणी में डालने और हटाने के लिए एल्गोरिदम देखेंगे। यदि हम इसमें कुछ तत्व डालते हैं, तो यह स्वतः ही क्रमबद्ध स्थिति में आ जाएगा। इसलिए हमें सम्मिलन के बाद इसे फिर से क्रमबद्ध करने की आवश्यकता नहीं है। जब हम हटाते हैं, तो यह तत्व को हटा देगा, और तत्वों को दाईं ओर स्थानांतरित करके खाली स्थान को भर देगा। जैसा कि हम क्रमबद्ध सरणी का उपयोग कर रहे हैं, हम इसे हटाने से पहले तत्व को खोजने के लिए बाइनरी सर्च एल्गोरिदम का उपयोग करेंगे।

एल्गोरिदम

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