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

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

大幅に離れた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でソート。

Comments are closed.

Post Navigation