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

たとえば、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つのレコードが正しい順序になる。このように最後のレコードまで繰り返す。
  挿入ソートは人間のよくやるソート法であり、ブリッジでカードを並べるときにもよく使う方法。
  本関数を利用するには、データ構造を実際の問題に合わせて修正して欲しい。

多くのソートアルゴリズムの中で、直感的に最も理解しやすいのは、バブルソートといわれている。バブルとは「泡」のことで、並べ替えの過程でデータが下から上へ移動する様子が、泡が浮かんでいくように見えることからこの名前がついたらしい。

<関数名>
  bubbleSort —- バブル法によるソート

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

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

<関数値>
  なし

<用例>
  bubbleSort-test.c

<関数本体>
  bubbleSort.c

<説明>
  縦方向一列に並んだレコードの中で、値の小さいレコード(昇進の場合)は軽く、泡(バブル)のように上に浮かんでいく、というようにイメージすれば分かりやすい。
  まず下から全体を走査して、隣接する2つのレコードの大小順序が狂ったとき、2つを入れ換える。この走査で、一番値の小さい(軽い)レコードが1番上に浮かびあがる。つぎに下から上2つ目のレコードまで走査して隣り同士を必要に応じて入れ換えることにより、その中の最小のものが上から2つ目のレコードに浮かびあがる。このように最後のレコードまで繰り返して終了。
  ご利用の際、データ構造を実際の問題に合わせて修正してほしい。

ソート (sort、整列) とは、データをある規則に従って並び替えることをいう。例えば、英語辞書は頭文字のアルファベット順にソートされている。

また数字を小さいものから大きいものに並べることを、昇順という。例: 1, 2, 3, 4, 5。
逆に、大きいものから小さいものまでの並び方を、 降順という。例: 5, 4, 3, 2, 1。

文字になるとややこしくなる。考え方としては、文字の内部コード(コンピュータ内の文字コード、例えばアスキーコードとか)を基準にソートすることが多いが、必ずしも常識と一致しないこともあるので、ご注意を。

なお、漢字のソートとなると、読み方が複数あるので、漢字の代わりに読み方でソートすることがほとんど。ということで、実際のソートは数字以外だと、結構大変。現場のひとによく聞いて、そこのルールに従うしかないかも。

ソートのプログラムに、速度の遅いもの、複雑ですが高速なもの、動きの安定するもの、色々なアルゴリズムが考え出されている。アルゴリズムの良し悪しを考えるのにいい素材になると思う。

プログラマとして食っていくには、多くのアルゴリズムを習得しないといけないし、アルゴリズムの良し悪しをご自分で判断できることも大切。判りやすくて高速なものがあれば万万歳だが、世の中はそうはあまくない。

さて、まずは選択ソートの関数。別名 セレクションソート(Selection Sort)。

<関数名>
  selectSort —- 選択法によるソート

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

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

<関数値>
  なし

<用例>
  selectSort-test.c

<関数本体>
  selectSort.c

<説明>
  選択ソートでは、まず全体を走査して最小のレコード(昇順の場合) を見つけ、それを最初のレコードと入れ換える。つぎに2つ目のレコードから最後まで走査してその中の最小のものを見つけ、2つ目のレコードと入れ換える。このように最後のレコードまで繰り返して終了。
  ご利用の際、データ構造を実際の問題に合わせて修正してほしい。