C++でソート済み配列を実装する方法：挿入・削除アルゴリズムを解説

この記事では、ソート済み配列（整列配列）に関する基本的な概念を解説します。配列は、同種のデータを連続したメモリ領域に格納するための均質なデータ構造です。データを利用する際に要素をソートする必要があるケースは多くありますが、最初から常にソートされた状態を保つ「ソート済み配列」を作成することも可能です。

ここでは、ソート済み配列への要素の挿入（insert）と削除（delete）を行うアルゴリズムを紹介します。ソート済み配列に要素を挿入すると、その要素は自動的に適切なソート位置へ配置されます。そのため、挿入後に再度ソートを実行する必要はありません。また、削除を行う際は、まずバイナリサーチ（二分探索）アルゴリズムを使って削除対象の要素を効率的に検索し、見つかった要素を削除した後、右側の要素を左にずらして空いた隙間を埋めます。

アルゴリズム

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

挿入処理では、配列の末尾から比較を始め、挿入するキー（key）より大きい要素を順次後ろへずらしていきます。そして、適切な位置が見つかった時点でキーを挿入し、要素数nを1増やします。

削除処理では、まずバイナリサーチによってキーの位置（pos）を特定します。posが-1の場合は要素が存在しないため処理を終了します。要素が見つかった場合は、その位置以降の要素を前へずらし、最後に要素数nを1減らします。

C++での実装例

#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

このプログラムでは、まず10から70までの値を昇順に挿入し、ソートされた状態を確認できます。次に、存在しない値35を削除しようとした際には「Element is not present.」というメッセージが表示されます。その後、40と60を削除すると、残りの要素が正しく詰められて順序が維持されていることがわかります。

このように、ソート済み配列を利用することで、挿入時の再ソートが不要になり、検索もバイナリサーチによってO(log n)の計算量で高速に行えるというメリットがあります。ただし、挿入や削除の際に要素のシフトが必要となるため、これらの操作はO(n)の計算量がかかる点には注意が必要です。