C++でのバイナリ挿入ソート

バイナリ挿入ソート は、バイナリ検索アルゴリズムを使用して配列内の挿入された要素の正しい位置を見つける挿入ソートの特殊なタイプアップです。

挿入ソートは、配列内の要素の正しい位置を見つけて、それを正しい位置に挿入することによって機能するソート手法です。

二分探索 要素を見つけるために配列の中央を見つけることによって機能する検索手法です。

二分探索の複雑さは対数の順序であるため、検索アルゴリズムの時間計算量も対数の順序に減少します。

バイナリ挿入ソートの実装。このプログラムは単純な挿入ソートプログラムですが、標準の検索手法の代わりにバイナリ検索が使用されます。

例

#include <iostream>
using namespace std;
int binarySearch(int arr[], int item, int low, int high) {
   if (high <= low)
      return (item > arr[low])? (low + 1): low;
      int mid = (low + high)/2;
   if(item == arr[mid])
      return mid+1;
   if(item > arr[mid])
      return binarySearch(arr, item, mid+1, high);
      return binarySearch(arr, item, low, mid-1);
}
void BinaryInsertionSort(int arr[], int n) {
   int i, loc, j, k, selected;
   for (i = 1; i < n; ++i) {
      j = i - 1;
      selected = arr[i];
      loc = binarySearch(arr, selected, 0, j);
      while (j >= loc) {
         arr[j+1] = arr[j];
         j--;
      }
      arr[j+1] = selected;
   }
}
int main() {
   int arr[] = {12, 56, 1, 67, 45, 8, 82, 16, 63, 23};
   int n = sizeof(arr)/sizeof(arr[0]), i;
   BinaryInsertionSort(arr, n);
      cout<<"Sorted array is : \n";
   for (i = 0; i < n; i++)
      cout<<arr[i]<<"\t";
   return 0;
}

出力

Sorted array is :
1 8 12 16 23 45 56 63 67 82