バイナリソート

1. バイナリソートアルゴリズム
2. バイナリソートの例
3. バイナリソートアルゴリズムの実装
4. バイナリソートアルゴリズムの複雑さ

バイナリソートは、比較型のソートアルゴリズムです。挿入ソートアルゴリズムの改良版です。このアルゴリズムでは、ソートされた部分配列とソートされていない部分配列を 1つずつ保持しています。唯一の違いは、線形探索ではなく二分探索を使って要素の正しい位置を見つけることです。これは、必要な比較の数を減らすことで、ソートアルゴリズムを高速化するのに役立ちます。

バイナリソートアルゴリズム

ここでは、n 個の要素を含むソートされていない配列 A[] があるとします。最初の要素 A[0] は既にソートされており、ソートされた部分配列の中にあります。

バイナリソートの例

配列 （5,3,4,2,1,6）があるとします。挿入ソートアルゴリズムを用いてソートします。

• 最初のイテレーション

キー : A[1] = 3

バイナリ検索: 3 の位置をインデックス 0 として返します。ソートされた配列の残りの要素を右シフトします。

• 2 回目のイテレーション

キー : A[2] = 4

バイナリ検索: 4 の位置をインデックス 1 として返します。ソートされた配列の残りの要素を右シフトします。

• 3 回目のイテレーション

キー : A[3] = 2

バイナリ検索: 2 の位置をインデックス 0 として返します。ソートされた配列の残りの要素を右シフトします。

• 4 回目のイテレーション

キー : A[4] = 1

バイナリ検索: 1 の位置をインデックス 0 として返します。ソートされた配列の残りの要素を右シフトします。

• 5 回目のイテレーション

キー : A[5] = 6

バイナリ検索: 6 の位置をインデックス 5 として返します。右側には要素がません。

4 回目の繰り返しでソートされた配列が得られる - (1 2 3 4 5 6).

バイナリソートアルゴリズムの実装

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int a[], int x, int low, int high) {
  if (high <= low) return (x > a[low]) ? (low + 1) : low;

  int mid = (low + high) / 2;

  if (x == a[mid]) return mid + 1;

  if (x > a[mid]) return binarySearch(a, x, mid + 1, high);
  return binarySearch(a, x, low, mid - 1);
}

void binarySort(int a[], int n) {
  for (int i = 1; i < n; ++i) {
    int j = i - 1;
    int key = a[i];
    int pos = binarySearch(a, key, 0, j);
    while (j >= pos) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  binarySort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

バイナリソートアルゴリズムの複雑さ

時間複雑度

• 平均のケース

二項探索は挿入ソートで用いられる線形探索の線形探索の複雑さ n に比べて対数的な複雑さ logn を持つ。n の要素に対して二分探索を行うと、時間的な複雑さ nlogn が得られます。したがって、時間的複雑さは [Big Theta]のオーダーである: O(nlogn)。

• 最悪のケース

最悪の場合は、配列を逆に並べ替えたときに最大のシフト数が必要となります。最悪の場合の時間的複雑さは [Big O]: O(nlogn) です。

• 最良のケース

最良のケースは、配列が既にソートされていて、要素の移動が不要な場合です。最良の時間的複雑さは [Big Omega]: O(n) です。

空間計算量

バイナリソートアルゴリズムの空間複雑度は、一時変数以外に余分なメモリを必要としないため、O(n) です。