シェルソートとは | 分かりやすく図解で解説

はじめに

基本情報技術者試験や応用情報技術者試験でよく出題される整列アルゴリズムの問題。

基本的な整列アルゴリズムには「バブルソート」「選択ソート」「挿入ソート」があり、より高速な整列アルゴリズムには「シェルソート」「クイックソート」「ヒープソート」「マージソート」があります。

スポンサーリンク

本記事では、一定間隔で要素を取り出し並び替えを繰り返していく「シェルソート」について図解を利用して分かりやすく解説しています。

シェルソートとは

シェルソートとは、ある一定間隔おきに取り出した要素内でソートを繰り返していく手法です。

それでは、図解を利用してシェルソートの流れを説明していきます。

【手順1】一定間隔おきにグループ分けを行う

まずは一定間隔でグループ分けをしていきます。例では間隔4でグループ分けしています。

• 青色グループ：4、1
• 橙色グループ：3、8
• 緑色グループ：5、6
• 灰色グループ：7、2

【手順2】グループ内で並び替えを行う

次にグループ内で並び替えを行います。グループ内での並び替え方法は、挿入ソート（基本挿入法）を使用します。※挿入ソートの説明は省略します。

挿入ソートとは「整列済み」と「未整列」に分け、「未整列」データを順番に「整列済み」データの中に挿入しながら並び替えしていく方法です。

詳しくは「挿入ソート（基本挿入法）」をご覧ください。

これで一定間隔が"4"の時の並び替えは終了です。

【手順3】一定間隔を縮めて再度グループ分け行う

一定間隔を4→2に縮めて、グループ分けをしていきます。

• 青色グループ：1、5、4、6
• 橙色グループ：3、2、8、7

【手順4】再びグループ内で並び替えを行う

再びグループ内で並び替えを行います。グループ内での並び替え方法は、挿入ソート（基本挿入法）を使用します。※挿入ソートの説明は省略します。

これで一定間隔が"2"の時の並び替えは終了です。

スポンサーリンク

【手順5】間隔1になったら残りの要素の並び替えを行う

一定間隔が1になったのでグループ分けは行わず、残りのデータを挿入ソートで並び替えをしていきます。これでシェルソートによる並び替えは完了です。※挿入ソートの説明は省略します。

[基本整列アルゴリズム]

• バブルソート（基本交換法）とは
• 選択ソート（基本選択法）とは
• 挿入ソート（基本挿入法）とは

[高速整列アルゴリズム]

• クイックソートとは
• ヒープソートとは
• マージソートとは