提出課題

目次 <hide>

バイナリサーチ関数
クイックソート関数
リニアサーチ関数

バイナリサーチ（二分探索）

説明

データ構造から目的の値を見つけ出すサーチアルゴリズムです。
但し、データは昇順または降順でソートされている必要があります。

中央要素の値と探索値を比較し、中央値が探索値よりも大きかったら中央値より前を探索し、
中央値が探索値よりも小さかったら中央値より後を探索します。

バイナリサーチを行うには、C言語標準ライブラリである bsearch 関数を使います。

コード

				
//***************************************************************************
/// @param  _Key             探索値のポインタ
/// @param  _Base            先頭要素のポインタ
/// @param  _NumOfElms       要素数
/// @param  _SizeOfElms      要素のサイズ
/// @param  _CompareFunction 比較関数のポインタ
/// @return void*            探索値と一致した要素のポインタ、
///                          見つからなければ NULL
//***************************************************************************
/// void* bsearch(
///	 const void* _Key       ,
///	 const void* _Base      ,
///	 size_t      _NumOfElms ,
///	 size_t      _SizeOfElms,
///	 int         (*_CompareFunction)(const void* _Key, const void* _Elm)
/// );
//***************************************************************************

// ここから
#include <stdlib.h> // bsearch
#include <stdio.h >

int CompareFunction(const void* _Key, const void* _Elm);

int main()
{
	int    Key        = 90                                              ;
	int    Base[]     = { 12, 67, 87, 90, 125, 153, 214, 234, 653, 804 };
	size_t NumOfElms  = sizeof(Base   ) / sizeof(Base[0])               ;
	size_t SizeOfElms = sizeof(Base[0])                                 ;

	int* Result = (int*)bsearch(&Key, Base, NumOfElms, SizeOfElms, CompareFunction);

	if   (Result) printf("Found: %d\n", *Result);
	else          printf("Not found\n"         );

	return 0;
}

int CompareFunction(const void* _Key, const void* _Elm)
{
	int* key = (int*)_Key;
	int* elm = (int*)_Elm;

	if      (*key > *elm) return  1;
	else if (*key < *elm) return -1;
	else                  return  0;
}

クイックソート

説明

データ構造中のデータを並べ替えるソートアルゴリズムです。

ピボット（基準値）を決め、それより小さいグループと大きいグループに分割します。
同じことを分割したそれぞれのグループでも行い、要素数が 1 になるまで繰り返します。

クイックソートを行うには、C言語標準ライブラリである qsort 関数を使います。

コード

				
//***************************************************************************
/// @param  _Base            先頭要素のポインタ
/// @param  _NumOfElms       要素数
/// @param  _SizeOfElms      要素のサイズ
/// @param  _CompareFunction 比較関数のポインタ
//***************************************************************************
/// void qsort(
///	 const void* _Base      ,
///	 size_t      _NumOfElms ,
///	 size_t      _SizeOfElms,
///	 int         (*_CompareFunction)(const void* _Key, const void* _Elm)
/// );
//***************************************************************************

// ここから
#include <stdlib.h> // qsort
#include <stdio.h >

int CompareFunction(const void* _Key, const void* _Elm);

int main()
{
	int    Base[]     = { 653, 67, 214, 87, 804, 125, 12, 153, 234, 90 };
	size_t NumOfElms  = sizeof(Base   ) / sizeof(Base[0])               ;
	size_t SizeOfElms = sizeof(Base[0])                                 ;

	printf("--- Before ---\n");
	for (int i = 0; i < NumOfElms; i++)
		printf("%d, ", Base[i]);
	printf("\n");

	qsort(Base, NumOfElms, SizeOfElms, CompareFunction);

	printf("--- After ---\n" );
	for (int i = 0; i < NumOfElms; i++)
		printf("%d, ", Base[i]);
	printf("\n");

	return 0;
}

int CompareFunction(const void* _Key, const void* _Elm)
{
	int* key = (int*)_Key;
	int* elm = (int*)_Elm;

	if      (*key > *elm) return  1;
	else if (*key < *elm) return -1;
	else                  return  0;
}

リニアサーチ（線形探索）

説明

データ構造から目的の値を見つけ出すサーチアルゴリズムです。
バイナリサーチとは異なり、データはソートされている必要はありません。

先頭要素から順番に探索し、探索値と一致または終端要素到達で終了します。

リニアサーチを行う MyLSearch 関数を作りました。

コード

				
//***************************************************************************
/// @param  _Key             探索値のポインタ
/// @param  _Base            先頭要素のポインタ
/// @param  _NumOfElms       要素数
/// @param  _SizeOfElms      要素のサイズ
/// @param  _CompareFunction 比較関数のポインタ
/// @return int              探索値と一致した要素のインデックス、
///                          見つからなければ -1
//***************************************************************************
/// int MyLSearch(
///	 const void* _Key       ,
///	 const void* _Base      ,
///	 size_t      _NumOfElms ,
///	 size_t      _SizeOfElms,
///	 int         (*_CompareFunction)(const void* _Key, const void* _Elm)
/// );
//***************************************************************************

// ここから
#include <stdio.h >

int CompareFunction(const void* _Key, const void* _Elm);
int MyLSearch(
	const void* _Key      ,
	const void* _Base     ,
	size_t      NumOfElms ,
	size_t      SizeOfElms,
	int         (*_CompareFunction)(const void* _Key, const void* _Elm)
);

int main()
{
	int    Key        = 87                                              ;
	int    Base[]     = { 653, 67, 214, 87, 804, 125, 12, 153, 234, 90 };
	size_t NumOfElms  = sizeof(Base   ) / sizeof(Base[0])               ;
	size_t SizeOfElms = sizeof(Base[0])                                 ;

	int Result = MyLSearch(&Key, Base, NumOfElms, SizeOfElms, CompareFunction);

	if (Result != -1)
		printf("Found at: %d\n", Result);
	else
		printf("Not found\n"           );

	return 0;
}

int CompareFunction(const void* _Key, const void* _Elm)
{
	int* key = (int*)_Key;
	int* elm = (int*)_Elm;

	if      (*key > *elm) return  1;
	else if (*key < *elm) return -1;
	else                  return  0;
}

int MyLSearch(
	const void* _Key      ,
	const void* _Base     ,
	size_t      NumOfElms ,
	size_t      SizeOfElms,
	int         (*_CompareFunction)(const void* _Key, const void* _Elm)
)
{
	for (int i = 0; i < NumOfElms; i++)
		if (!_CompareFunction(_Key, (int*)_Base + i)) return i;

	return -1;
}