目次
はじめに
基本情報技術者試験や応用情報技術者試験でよく出題される整列アルゴリズムの問題。
基本的な整列アルゴリズムには「バブルソート」「選択ソート」「挿入ソート」があり、より高速な整列アルゴリズムには「シェルソート」「クイックソート」「ヒープソート」「マージソート」があります。
スポンサーリンク
本記事では、一定間隔で要素を取り出し並び替えを繰り返していく「シェルソート」について図解を利用して分かりやすく解説しています。
シェルソートとは
シェルソートとは、ある一定間隔おきに取り出した要素内でソートを繰り返していく手法です。
シェルソートのな流れ
- 一定間隔起きに要素を取り出し並び替え
- 一定間隔を縮めて要素を取り出し並び替え
- 処理1と2の流れを一定間隔が１になるまで繰り返す
暗記ポイント
シェルソートは一定間隔のおきに取り出した要素内でソートを繰り返す整列アルゴリズム
それでは、図解を利用してシェルソートの流れを説明していきます。
【手順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になったので、グループ分けは行わず、残りのデータを挿入ソートで並び替えをしていきます。これでシェルソートによる並び替えは完了です。
[基本整列アルゴリズム]
[高速整列アルゴリズム]
この記事は役に立ちましたか？
