shell sort

デジタル大辞泉

シェル‐ソート【shell sort】

読み方：しぇるそーと

コンピューターでデータをある基準によって並べかえるソートで使われるアルゴリズムの一。挿入ソートを改良し、隣り合った要素だけを比較するのではなく、ある適当な間隔で取り出した要素列に対し、挿入ソートを行い、徐々にその間隔を詰めて同じ走査を繰り返す。

IT用語辞典バイナリ

シェルソート

【英】shell sort

シェルソートとは、ソート（整列）のアルゴリズムの一種で、挿入ソートを改良したアルゴリズムのことである。アメリカのコンピュータ科学者ドナルド・シェル（Donald Shell）によって考案された。

シェルソートの原型となっている挿入ソートは、もっとも単純なアルゴリズムの一つで、原理上ランダムな並びのデータを整列させるには効率が悪いという欠点がある。シェルソートでは、初めに大きなデータと小さなデータとを大まかに分け、その後に挿入ソートを行う、という手順を踏むことで、挿入ソートの効率化を図ろうとするものである。

シェルソートでは、まず一定間隔の全てのデータの組み合わせに対して小さなデータが前にくるよう交換処理を行う。これを、間隔を小さくしながら隣同士の交換になるまで同じことを繰り返し、最後には挿入ソートを行う。

なお、同じデータの順番がソート前後によって変化しないソート手法を「安定なソート」と言うが、挿入ソートとは違い、シェルソートは安定なソートではない。

情報処理のほかの用語一覧

アルゴリズム：

整列  セレクションソート  選択ソート  シェルソート  識別子  巡回セールスマン問題  昇順

>>アルゴリズムカテゴリの他の用語