もっとも基本的なソート・アルゴリズムの一つ。別名 インサーションソート (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つのレコードが正しい順序になる。このように最後のレコードまで繰り返す。
  挿入ソートは人間のよくやるソート法であり、ブリッジでカードを並べるときにもよく使う方法。
  本関数を利用するには、データ構造を実際の問題に合わせて修正して欲しい。

Comments are closed.

Post Navigation