目次
はじめに
情報処理試験問題でよく登場する整列アルゴリズムの問題。
基本的な整列アルゴリズムには「バブルソート」「選択ソート」「挿入ソート」があります。そしてより高速な整列アルゴリズムには「シェルソート」「クイックソート」「ヒープソート」「マージソート」などがあります。
スポンサーリンク
本記事では、一定間隔で要素を取り出し並び替えを繰り返していく「シェルソート」について図解を利用してわかりやすく解説しています。
シェルソートとは
シェルソートとは、ある一定間隔おきに取り出した要素内でソートを繰り返していく手法です。
- 一定間隔起きに要素を取り出し並び替え
- 一定間隔を縮めて要素を取り出し並び替え
- この流れを一定間隔が１になるまで繰り返す
それでは具体的に図解でシェルソートの流れを説明していきます。
暗記ポイント：シェルソートは一定間隔のおきに取り出した要素内でソートを繰り返す、整列アルゴリズム
【手順1】一定間隔おきにグループ分けを行う
まずは一定間隔でグループ分けをしていきます。例では間隔4でグループ分けしています。
- 青グループ：4、1
- オレンジグループ：3、8
- 緑グループ：5、6
- 灰色グループ：7、2
【手順2】グループ内で並び替えを行う
次にグループ内で並び替えを行います。グループ内での並び替えの方法は、挿入ソート（基本挿入法）と同じです。
※挿入ソートとは「整列済み」と「未整列」にデータを分け、「未整列」データをひとつずつ「整列済み」データの中に挿入していく方法
- 青色グループの4と1を入れ替えます。
- 灰色グループの7と2を入れ替えます。
これで一定間隔が"4"の時の並び替えは終了です。
【手順3】一定間隔を縮めて再度グループ分け行う
一定間隔を4→2に縮めて、グループ分けをしていきます。
- 青色グループ：1、5、4、6
- 橙色グループ：3、2、8、7
【手順4】再びグループ内で並び替えを行う
グループ内で並び替えを行います。
- 青色グループの５と4を入れ替えます。
- 橙色グループの3と2を入れ替えます。
- 橙色グループの8と7を入れ替えます。
これで一定間隔が"2"の時の並び替えは終了です。
スポンサーリンク
【手順5】間隔1になったら残りの要素の並び替えを行う
一定間隔が1になったので、グループ分けは行わず、残りのデータを挿入ソートで並び替えをしていきます。これでシェルソートによる並び替えは完了です。
[基本整列アルゴリズム]
[高速整列アルゴリズム]