2進数字列を、整数値に変換する関数。

たとえば、2進数字列 "101011" → 数値 43。

<関数名>
  binsz2int ---- 2進数字列を整数値に変換する

<形式>
  int binsz2int(char *str);

<引数>
  str 2進数 ASCIZ文字列。先頭に符号 (+またはー) があってもOK。

<関数値>
  入力の2進数字列に対応する整数値(10進数)

<注意事項>
  整数値のオーバーフローに注意。

用例
  binsz2int("-1101");

<関数本体>
  binsz2int.c

<説明>
  2進数字列の先頭から、まずスペースを読み飛ばす。つぎに符号を処理し、2進数字の各桁を変換していく。

10進数字列を、整数値に変換する関数。

たとえば、10進数字列 "12345" → 数値 12345。

<関数名>
  sz2int ---- 10進数字列を整数値に変換する

<形式>
  int sz2int(char *str);

<引数>
  str 10進数 ASCIZ文字列。先頭に符号 (+またはー) があってもOK。

<関数値>
  入力の10進数字列に対応する整数値(10進数)

<注意事項>
  整数値のオーバーフローに注意。

用例
  sz2int("-6119");

<関数本体>
  sz2int.c

<説明>
  10進数字列の先頭から、まずスペースを読み飛ばす。つぎに符号を処理し、10進数字の各桁を変換していく。

整数値を、16進数字列への変換関数。

たとえば、値 180 が 数字列(16進数字列) "B4" に変換される。

<関数名>
  int2hexsz ---- 整数値を16進数字列へ変換する

<形式>
  void int2hexsz(char *str, int num);

<引数>
  str  (出力) 16進数ASCIZ文字列
  num (入力) 変換したい整数値(マイナスの値でもOK)

<関数値>
  なし

用例
  char str[15];
  int2hexsz(str, 12345);

<関数本体>
  int2hexsz.c

<説明>
  再帰法を使用。先行の数字については自分自身を呼出して対応し、最終桁だけを変換して処理する。その際、A-F への変換に注意すること。

整数値を、2進数文字列に変換する関数。

たとえば、値 13 が 数字列(2進数列) "1101" に変換される。

<関数名>
  int2binsz ---- 整数値を2進数字列へ変換する

<形式>
  void int2binsz(char *str, int num);

<引数>
  str  (出力) 2進数ASCIZ文字列
  num (入力) 変換したい整数値(マイナスでもOK)

<関数値>
  なし

<注意事項>
  マイナスの整数値が、マイナス記号が先頭につく2進数字列に変換される。
  例: -100 → "-1100100"

用例
  char str[50];
  int2binsz(str, 12345);

<関数本体>
  int2binsz.c

<説明>
  再帰法を使用。先行の数字については自分自身を呼出して対応し、最終桁だけを変換して処理する。
  なお、ASCIZ文字列とは、最後にヌル(Null) コードで終了する文字列のこと。

整数値を、10進数字列に変換する関数。

たとえば、値 13 が 数字列 "13" に変換される。

文字(数字)と数値、われわれ人間には、それらの表現はともにシンボル(記号的意味)でしかないので、全く同じにみえる。しかし、コンピュータの世界では違う。

文字(数字)と数値が、コンピュータの内部では異なる表現になっているから。

コンピュータ内部での文字表現を、文字コードという。もっともよく使われている文字コードはアスキーコード。プログラマを目指すひとなら、真剣にアスキーコード表を見てほしい。

アスキーコードでは、たとえば、文字の 1 は、16進数値 31、つまり2進数値の 110001 で表現される。すなわち、コンピュータの内部では、文字の 1 は 10進数値の 49 と同じ。

こんなわけで、「文字、文字列、数字、数字列」 と 「値、数値、整数値」とは混同しないでほしい。

<関数名>
  int2sz ---- 整数値を10進数字列へ変換する

<形式>
  void int2sz(char *str, int num);

<引数>
  str  (出力) 10進数ASCIZ文字列
  num (入力) 変換したい整数値(マイナスでもOK)

<関数値>
  なし

<注意事項>
  マイナスの整数値が、マイナス記号が先頭につく数字列に変換される。
  例: -100 → "-100"

用例
  char str[15];
  int2sz(str, 12345);

<関数本体>
  int2sz.c

<説明>
 再帰法を使用。先行の数字については自分自身を呼出して対応し、最終桁だけを変換して処理する。
 なお、ASCIZ文字列とは、最後にヌル(Null) コードで終了する文字列のこと。

C言語の標準関数 sprintf() が使える環境であれば、本関数と同じことを
    sprintf(str, "%d", num);
で書くのはふつうだね。ただ、マイコンへの組込み等、プログラムの容量を少しでも減らしたいならば本関数も有用かな。

16進数字列を整数値に変換する関数。

たとえば、16進数字列 "A4C" → 値 2636。

<関数名>
  hexsz2int ---- 16進数字列を整数値に変換する

<形式>
  int hexsz2int(char *str);

<引数>
  str 16進数ASCIZ文字列
  先頭に符号(+/-)が入ってもOK。各桁は0〜9、A〜F、または、a〜f。

<関数値>
  16進数字列に相当する整数値(10進数)

<注意事項>
  整数のオーバーフローに注意。

用例
  hexsz2int("B6119");

<関数本体>
  hexsz2int.c

<説明>
  16進数字列の先頭から、まずホワイトスペースを読み飛ばす。つぎに符号を処理し、16進数字の各桁を変換していく。各桁の 変換においては、0-9、A-F、a-fのような場合分けを考慮する。

多くのデータから、最大値、または、最小値を求める関数。

たとえば、5個のデータ 1 6 3 8 7 では、最大値は 8、最小値は 1、といった具合。

<関数名>
  maxmin ---- n個のデータから最大値および最小値を求める

<形式>
  void maxmin(int *max, int *min, DATA *data, int nmem);

<引数>
  typedef struct {
    int key;    /* 比較のキーとなるフィールド */
    int info;    /* その他のフィールド */
  } DATA;
  max  (出力) キーの値が最大のレコード配列の番号(先頭番号は 0)
  min  (出力) キーの値が最小のレコード配列の番号(先頭番号は 0)
  data  (入力) レコード配列
  nmem (入力) レコード配列の大きさ

<関数値>
  なし

<用例>
  maxmin-test.c

<関数本体>
  maxmin.c

<説明>
  最も簡単なやり方は、最初 n-1 回の比較で最大値 max を見つけ、つぎに残りの n-1 個のデータから n-2 回の比較で最小値 min を見つける方法だ。この場合、計 2n-3 回の比較が必要。
  一方、関数のように、n 個のデータを半分ずつに分け、その各々のグループより最大最小を見つけたとすると、全体の最大値は2つの最大の大きいほう、全体の最小値は2つの最小の小さいほうとなる。この操作を再帰的に各グループの要素が2つになるまで行う。この場合、比較回数は 3/2n - 2 であり、上記の単純比較法のそれよりも小さい。
  ご利用には、データ構造を実際の問題に合わせて修正してほしい。

必ず知らないといけない、ソート・アルゴリズムのひとつ。

最悪の計算時間はO(n2)だが、平均計算時間はO(n log n)。他のソート法と比べて、最も高速だといわれているが、安定ソートではない。また、クイックソートの欠点は、順序よく並んだデータでは極端に遅くなってしまう。

<関数名>
  quickSort ---- クイックソート

<形式>
  void quickSort(DATA *data, int nmem, int asdes);

<引数>
  typedef struct {
    int key;    /* 比較のキーとなるフィールド */
    int info;    /* その他のフィールド */
  } DATA;
  data  (入出力) データレコードの配列
  nmem (入力) レコード配列の大きさ
  asdes (入力) 昇順・降順別、0:昇順, 1:降順

<関数値>
  なし

<用例>
  quickSort-test.c

<関数本体>
  quickSort.c

<説明>
  C. A. R. Hoare (ホア) によるクイックソート(quick sort)は、平均的に最も速いソートアルゴリズムだといわれている。クイックソートでは、昇順ソートの場合、
  1. 適当な値 x を選ぶ。その際、配列の x 以下の要素の数と x 以上の 要素の数とはなるべく同程度になるようにする。
  2. x 以下の要素を配列の前半に、x 以上の要素を配列の後半に集める。
  3. 配列の前半が要素数が2以上なら、配列の前半を再帰的にクイック ソートする。
  4. 配列の後半が要素数が2以上なら、配列の後半を再帰的にクイック ソートする。
  このように、配列をつぎつぎに2つにして、それぞれについてソートを行う。
  ご利用の際、データ構造を実際の問題に合わせて修正して欲しい。

ソート・アルゴリズムの一つで、挿入ソートを改良したもの。

データを数個とびに拾い集めて挿入ソートをかけ、次第にソートする要素の間隔を詰めていき、最後に単純な挿入ソートで完全にソートさせる。

大幅に離れた2つのデータを一気に交換することで交換回数を減らし、高速化をはかったアルゴリズムだが、クイックソートなどに比べると若干速度は落ちる。

ちなみに、シェルの名はアルゴリズムの考案者 D.L.Shell の名前に由来する。

<関数名>
  shellSort ---- シェルソート

<形式>
  void shellSort(DATA *data, int nmem, int asdes);

<引数>
  typedef struct {
    int key;    /* 比較のキーとなるフィールド */
    int info;    /* その他のフィールド */
  } DATA;
  data  (入出力) データレコードの配列
  nmem (入力) レコード配列の大きさ
  asdes (入力) 昇順・降順別、0:昇順, 1:降順

<関数値>
  なし

<用例>
  shellSort-test.c

<関数本体>
  shellSort.c

<説明>
  挿入ソートが遅いのは、隣の要素同士しか交換しないからである。たとえば、最小の要素がたまたま最後にあった場合は、それを最初に移動させるにはN回の比較と交換かかる。シェルソートは、挿入ソートのの拡張として、遠く離れている要素の間でも交換するように高速化をはかったものだ。
  そのアイデアとしては、h要素分だけ離れた要素同士をまずソートし、h の値をだんだん小さくしながらソートを繰り返す。最後には、h=1でソート。

もっとも基本的なソート・アルゴリズムの一つ。別名 インサーションソート (Insersion Sort)。

まず、並んだデータのうち最初の2つを取り出し比較し、望む順序(昇順か降順)に並べる。次に、3つ目のデータをソートした2つと順に比較し、適切な位置に挿入する。4つ目以降も同様にして、ソート済みの列の適切な位置に一つずつ挿入していく。

与えられたデータがソート済み状態に近ければ比較的高速だが、要素が逆順に並んでいると遅くなってしまう。この欠点をある程度緩和した改良版に、これから紹介する シェルソート がある。

ちなみに、挿入ソートは人間がもっとも簡単に行えるソート方法だといわれている。

<関数名>
  insertSort ---- 挿入法によるソート

<形式>
  void insertSort(DATA *data, int nmem, int asdes);

<引数>
  typedef struct {
    int key;    /* 比較のキーとなるフィールド */
    int info;    /* その他のフィールド */
  } DATA;
  data  (入出力) データレコードの配列
  nmem (入力) レコード配列の大きさ
  asdes (入力) 昇順・降順別、0:昇順, 1:降順

<関数値>
  なし

<用例>
  insertSort-test.c

<関数本体>
  insertSort.c

<説明>
  挿入ソートでは、すでにソート済のレコードに新しいレコードを正しい場所に挿入する。つまり、最初の2つのレコードについてまず入れ換えにより正しい順序にする。つぎに、3つ目のレコードを前の2つのレコードと比較して、必要に応じて入れ換えを行う。これで、3つのレコードが正しい順序になる。このように最後のレコードまで繰り返す。
  挿入ソートは人間のよくやるソート法であり、ブリッジでカードを並べるときにもよく使う方法。
  本関数を利用するには、データ構造を実際の問題に合わせて修正して欲しい。