algorithm


関数

void Containor_sort (Containor *self, size_t idx, size_t n, int(*comp)(const void *p1, const void *p2))
 ソート
void Containor_stable_sort (Containor *self, size_t idx, size_t n, int(*comp)(const void *p1, const void *p2))
 安定ソート
void Containor_partial_sort (Containor *self, size_t idx, size_t sort_n, size_t n, int(*comp)(const void *p1, const void *p2))
 部分ソート
size_t Containor_binary_search (Containor *self, size_t idx, size_t n, T value, int(*comp)(const void *p1, const void *p2))
 二分探索
size_t Containor_lower_bound (Containor *self, size_t idx, size_t n, T value, int(*comp)(const void *p1, const void *p2))
 最初の位置の検索
size_t Containor_upper_bound (Containor *self, size_t idx, size_t n, T value, int(*comp)(const void *p1, const void *p2))
 最後の位置の検索
void Containor_reverse (Containor *self, size_t idx, size_t n)
 逆順に並べ替え
void Containor_rotate (Containor *self, size_t first, size_t middle, size_t last)
 回転
int Containor_merge (Containor *self, size_t idx, Containor *x, size_t xidx, size_t xn, Containor *y, size_t yidx, size_t yn, int(*comp)(const void *p1, const void *p2))
 マージ
void Containor_inplace_merge (Containor *self, size_t first, size_t middle, size_t last, int(*comp)(const void *p1, const void *p2))
 連続する範囲のマージ
void Containor_make_heap (Containor *self, size_t idx, size_t n, int(*comp)(const void *p1, const void *p2))
 ヒープに変換
void Containor_sort_heap (Containor *self, size_t idx, size_t n, int(*comp)(const void *p1, const void *p2))
 ヒープソート
void Containor_push_heap (Containor *self, size_t idx, size_t n, int(*comp)(const void *p1, const void *p2))
 ヒープに追加
void Containor_pop_heap (Containor *self, size_t idx, size_t n, int(*comp)(const void *p1, const void *p2))
 ヒープから削除

説明

vector, deque, string において、共通なアルゴリズムを提供する。

アルゴリズムを使うには、CSTL_XXX_INTERFACE() (XXXは、VECTOR, DEQUE, STRINGのいずれか)を展開する前に、 <cstl/algorithm.h>というヘッダファイルをインクルードする必要がある。

#include <cstl/algorithm.h>

使用例:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <cstl/vector.h>
#include <cstl/algorithm.h> /* CSTL_VECTOR_INTERFACE()の前にインクルード */

/* vectorのインターフェイスと実装を展開 */
CSTL_VECTOR_INTERFACE(IntVector, int)
CSTL_VECTOR_IMPLEMENT(IntVector, int)

/* intの比較関数 */
int int_less(const void *p1, const void *p2)
{
    if (*(int*)p1 < *(int*)p2) {
        return -1;
    } else if (*(int*)p1 > *(int*)p2) {
        return 1;
    } else {
        return 0;
    }
}

int main(void)
{
    int i;
    size_t idx;
    /* intのvectorを生成。
     * 型名・関数のプレフィックスはIntVectorとなる。 */
    IntVector *vec = IntVector_new();

    srand(time(0));
    for (i = 0; i < 64; i++) {
        /* 末尾から100未満のランダムな値の要素を追加 */
        IntVector_push_back(vec, rand() % 100);
    }
    /* ソート */
    IntVector_sort(vec, 0, IntVector_size(vec), int_less);
    for (i = 0; i < IntVector_size(vec); i++) {
        printf("%d, ", *IntVector_at(vec, i));
    }
    printf("\n");
    /* 50以上の最初の要素のインデックス */
    idx = IntVector_lower_bound(vec, 0, IntVector_size(vec), 50, int_less);
    /* 先頭から50未満の要素までを逆順に並べ替え */
    IntVector_reverse(vec, 0, idx);
    for (i = 0; i < IntVector_size(vec); i++) {
        printf("%d, ", *IntVector_at(vec, i));
    }

    /* 使い終わったら破棄 */
    IntVector_delete(vec);
    return 0;
}
注意:
以下に説明する関数は、 CSTL_XXX_INTERFACE(Name, Type)NameContainer , TypeT を仮に指定した場合のものである。 実際に使用する際には、使用例のように適切な引数を指定すること。
覚え書き:
コンパイラオプションによって、NDEBUGマクロが未定義かつCSTL_DEBUGマクロが定義されているならば、 assertマクロが有効になり、関数の事前条件に違反するとプログラムの実行を停止する。

関数

void Containor_sort ( Containor *  self,
size_t  idx,
size_t  n,
int(*)(const void *p1, const void *p2)  comp 
)

ソート

selfidx 番目からn 個の要素を比較関数comp に従ってソートする。 このソートは安定でない。

引数:
self オブジェクト
idx ソート開始インデックス
n ソートする要素数
comp 比較関数
事前条件:
idx + nself の要素数以下の値であること。

comp には、*p1 == *p2ならば0を、*p1 < *p2ならば正または負の整数を、*p1 > *p2ならば*p1 < *p2の場合と逆の符号の整数を返す関数を指定すること。 (C標準関数のqsort(), bsearch()に使用する関数ポインタと同じ仕様)

覚え書き:
計算量は平均的にはO(N * log N)である。最悪な場合はO(N^2)となる。

void Containor_stable_sort ( Containor *  self,
size_t  idx,
size_t  n,
int(*)(const void *p1, const void *p2)  comp 
)

安定ソート

selfidx 番目からn 個の要素を比較関数comp に従ってソートする。 このソートは安定である。

引数:
self オブジェクト
idx ソート開始インデックス
n ソートする要素数
comp 比較関数
事前条件:
idx + nself の要素数以下の値であること。

comp には、*p1 == *p2ならば0を、*p1 < *p2ならば正または負の整数を、*p1 > *p2ならば*p1 < *p2の場合と逆の符号の整数を返す関数を指定すること。 (C標準関数のqsort(), bsearch()に使用する関数ポインタと同じ仕様)

覚え書き:
計算量はメモリに十分な空き領域がある場合はO(N * log N)である。空き領域がない場合はO(N * log N * log N)となる。

void Containor_partial_sort ( Containor *  self,
size_t  idx,
size_t  sort_n,
size_t  n,
int(*)(const void *p1, const void *p2)  comp 
)

部分ソート

selfidx 番目からn 個の要素の内、最初のsort_n 個が正しい順序になるように比較関数comp に従ってソートする。 selfidx + sort_n 番目からn - sort_n 個の要素の順序は未定義である。 このソートは安定でない。

引数:
self オブジェクト
idx ソート開始インデックス
sort_n この関数実行の結果、ソート済みになる要素数
n ソート対象の要素数
comp 比較関数
事前条件:
sort_nn 以下の値であること。

idx + nself の要素数以下の値であること。

comp には、*p1 == *p2ならば0を、*p1 < *p2ならば正または負の整数を、*p1 > *p2ならば*p1 < *p2の場合と逆の符号の整数を返す関数を指定すること。 (C標準関数のqsort(), bsearch()に使用する関数ポインタと同じ仕様)

覚え書き:
計算量はO(N * log N)である。

sort_nn に等しい場合、selfidx 番目からn 個の要素をソートする。

size_t Containor_binary_search ( Containor *  self,
size_t  idx,
size_t  n,
value,
int(*)(const void *p1, const void *p2)  comp 
)

二分探索

selfidx 番目からn 個の要素において、比較関数comp に従ってvalue一致 する要素を検索する。

引数:
self オブジェクト
idx 検索開始インデックス
n 検索する要素数
value 検索する値
comp 比較関数
戻り値:
見つかった場合、その要素のインデックスを返す。 複数見つかった場合、最初の要素のインデックスを返す。

見つからない場合、idx + n を返す。

事前条件:
idx + nself の要素数以下の値であること。

selfidx 番目からn 個の要素が比較関数comp に従ってソートされていること。

comp には、*p1 == *p2ならば0を、*p1 < *p2ならば正または負の整数を、*p1 > *p2ならば*p1 < *p2の場合と逆の符号の整数を返す関数を指定すること。 (C標準関数のqsort(), bsearch()に使用する関数ポインタと同じ仕様)

覚え書き:
計算量はO(log N)である。

size_t Containor_lower_bound ( Containor *  self,
size_t  idx,
size_t  n,
value,
int(*)(const void *p1, const void *p2)  comp 
)

最初の位置の検索

selfidx 番目からn 個の要素において、比較関数comp に従ってvalue 以上 の最初の要素を検索する。

引数:
self オブジェクト
idx 検索開始インデックス
n 検索する要素数
value 検索する値
comp 比較関数
戻り値:
見つかった場合、その要素のインデックスを返す。

見つからない場合、idx + n を返す。

事前条件:
idx + nself の要素数以下の値であること。

selfidx 番目からn 個の要素が比較関数comp に従ってソートされていること。

comp には、*p1 == *p2ならば0を、*p1 < *p2ならば正または負の整数を、*p1 > *p2ならば*p1 < *p2の場合と逆の符号の整数を返す関数を指定すること。 (C標準関数のqsort(), bsearch()に使用する関数ポインタと同じ仕様)

覚え書き:
計算量はO(log N)である。

size_t Containor_upper_bound ( Containor *  self,
size_t  idx,
size_t  n,
value,
int(*)(const void *p1, const void *p2)  comp 
)

最後の位置の検索

selfidx 番目からn 個の要素において、比較関数comp に従ってvalue より大きい 最初の要素を検索する。

引数:
self オブジェクト
idx 検索開始インデックス
n 検索する要素数
value 検索する値
comp 比較関数
戻り値:
見つかった場合、その要素のインデックスを返す。

見つからない場合、idx + n を返す。

事前条件:
idx + nself の要素数以下の値であること。

selfidx 番目からn 個の要素が比較関数comp に従ってソートされていること。

comp には、*p1 == *p2ならば0を、*p1 < *p2ならば正または負の整数を、*p1 > *p2ならば*p1 < *p2の場合と逆の符号の整数を返す関数を指定すること。 (C標準関数のqsort(), bsearch()に使用する関数ポインタと同じ仕様)

覚え書き:
計算量はO(log N)である。

void Containor_reverse ( Containor *  self,
size_t  idx,
size_t  n 
)

逆順に並べ替え

selfidx 番目からn 個の要素を逆順に並べ替える。

引数:
self オブジェクト
idx 並べ替え開始インデックス
n 並べ替える要素数
事前条件:
idx + nself の要素数以下の値であること。
覚え書き:
計算量はO(N)である。

void Containor_rotate ( Containor *  self,
size_t  first,
size_t  middle,
size_t  last 
)

回転

selfmiddle 番目からlast - 1番目までの要素をfirst 番目の位置に移動する。 first 番目からmiddle - 1番目までにあった要素は後ろにずらされる。

引数:
self オブジェクト
first middle 番目からlast - 1番目までの要素の移動先
middle 移動元の範囲の開始インデックス
last 移動元の範囲の終了インデックス
事前条件:
first <= middle <= last <= self の要素数、であること。
覚え書き:
計算量はO(N)である。

int Containor_merge ( Containor *  self,
size_t  idx,
Containor *  x,
size_t  xidx,
size_t  xn,
Containor *  y,
size_t  yidx,
size_t  yn,
int(*)(const void *p1, const void *p2)  comp 
)

マージ

xxidx 番目からxn 個の要素とyyidx 番目からyn 個の要素のコピーを比較関数comp に従ってマージし、selfidx 番目の位置に挿入する。 selfidx 番目からxn + yn 個の要素はソートされた状態になる。

引数:
self オブジェクト
idx 挿入する位置
x 1つ目のマージ元のオブジェクト
xidx x のマージ開始インデックス
xn x のマージする要素数
y 2つ目のマージ元のオブジェクト
yidx y のマージ開始インデックス
yn y のマージする要素数
comp 比較関数
戻り値:
挿入に成功した場合、非0を返す。

メモリ不足の場合、self の変更を行わず0を返す。

事前条件:
idxself の要素数以下の値であること。

xidx + xnx の要素数以下の値であること。

yidx + yny の要素数以下の値であること。

selfxselfy は同じオブジェクトでないこと。

xxidx 番目からxn 個の要素が比較関数comp に従ってソートされていること。

yyidx 番目からyn 個の要素が比較関数comp に従ってソートされていること。

comp には、*p1 == *p2ならば0を、*p1 < *p2ならば正または負の整数を、*p1 > *p2ならば*p1 < *p2の場合と逆の符号の整数を返す関数を指定すること。 (C標準関数のqsort(), bsearch()に使用する関数ポインタと同じ仕様)

覚え書き:
計算量はO(N)である。

void Containor_inplace_merge ( Containor *  self,
size_t  first,
size_t  middle,
size_t  last,
int(*)(const void *p1, const void *p2)  comp 
)

連続する範囲のマージ

self の連続する2つの範囲first 番目からmiddle - 1番目までとmiddle 番目からlast - 1番目までの要素を比較関数comp に従ってマージする。 selffirst 番目からlast - 1番目までの要素はソートされた状態になる。

引数:
self オブジェクト
first 1つ目のマージ範囲の開始インデックス
middle 1つ目のマージ範囲の終了インデックス、かつ2つ目のマージ範囲の開始インデックス
last 2つ目のマージ範囲の終了インデックス
comp 比較関数
事前条件:
first <= middle <= last <= self の要素数、であること。

selffirst 番目からmiddle - 1番目までの要素は比較関数comp に従ってソートされていること。

selfmiddle 番目からlast - 1番目までの要素は比較関数comp に従ってソートされていること。

comp には、*p1 == *p2ならば0を、*p1 < *p2ならば正または負の整数を、*p1 > *p2ならば*p1 < *p2の場合と逆の符号の整数を返す関数を指定すること。 (C標準関数のqsort(), bsearch()に使用する関数ポインタと同じ仕様)

覚え書き:
計算量はメモリに十分な空き領域がある場合はO(N)である。空き領域がない場合はO(N * log N)となる。

void Containor_make_heap ( Containor *  self,
size_t  idx,
size_t  n,
int(*)(const void *p1, const void *p2)  comp 
)

ヒープに変換

selfidx 番目からn 個の要素を比較関数comp に従ってヒープに変換する。

引数:
self オブジェクト
idx 変換開始インデックス
n 変換する要素数
comp 比較関数
事前条件:
idx + nself の要素数以下の値であること。

comp には、*p1 == *p2ならば0を、*p1 < *p2ならば正または負の整数を、*p1 > *p2ならば*p1 < *p2の場合と逆の符号の整数を返す関数を指定すること。 (C標準関数のqsort(), bsearch()に使用する関数ポインタと同じ仕様)

覚え書き:
計算量はO(N)である。

void Containor_sort_heap ( Containor *  self,
size_t  idx,
size_t  n,
int(*)(const void *p1, const void *p2)  comp 
)

ヒープソート

selfidx 番目からn 個の要素を比較関数comp に従ってソートする。 このソートは安定でない。

引数:
self オブジェクト
idx ソート開始インデックス
n ソートする要素数
comp 比較関数
事前条件:
idx + nself の要素数以下の値であること。

selfidx 番目からn 個の要素が比較関数comp に従ってヒープになっていること。

comp には、*p1 == *p2ならば0を、*p1 < *p2ならば正または負の整数を、*p1 > *p2ならば*p1 < *p2の場合と逆の符号の整数を返す関数を指定すること。 (C標準関数のqsort(), bsearch()に使用する関数ポインタと同じ仕様)

覚え書き:
計算量はO(N * log N)である。

void Containor_push_heap ( Containor *  self,
size_t  idx,
size_t  n,
int(*)(const void *p1, const void *p2)  comp 
)

ヒープに追加

selfidx + n - 1番目の要素を、selfidx 番目からn - 1個の範囲のヒープに追加して、idx 番目からn 個の要素を一つのヒープとして再構成する。

引数:
self オブジェクト
idx ヒープ開始インデックス
n この関数実行の結果、ヒープになる要素数
comp 比較関数
事前条件:
idx + nself の要素数以下の値であること。

selfidx 番目からn - 1個の要素が比較関数comp に従ってヒープになっていること。

comp には、*p1 == *p2ならば0を、*p1 < *p2ならば正または負の整数を、*p1 > *p2ならば*p1 < *p2の場合と逆の符号の整数を返す関数を指定すること。 (C標準関数のqsort(), bsearch()に使用する関数ポインタと同じ仕様)

覚え書き:
計算量はO(log N)である。

void Containor_pop_heap ( Containor *  self,
size_t  idx,
size_t  n,
int(*)(const void *p1, const void *p2)  comp 
)

ヒープから削除

selfidx 番目からn 個の範囲のヒープから、ヒープの最初の要素とヒープの最後の要素を交換し、selfidx 番目からn - 1個の要素を一つのヒープとして再構成する。

引数:
self オブジェクト
idx ヒープ開始インデックス
n ヒープの要素数
comp 比較関数
事前条件:
idx + nself の要素数以下の値であること。

selfidx 番目からn 個の要素が比較関数comp に従ってヒープになっていること。

n が1以上であること。

comp には、*p1 == *p2ならば0を、*p1 < *p2ならば正または負の整数を、*p1 > *p2ならば*p1 < *p2の場合と逆の符号の整数を返す関数を指定すること。 (C標準関数のqsort(), bsearch()に使用する関数ポインタと同じ仕様)

覚え書き:
計算量はO(log N)である。


SourceForge.JP