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