シェルソートとは

プログラム

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

はじめに

情報処理試験問題でよく登場する整列アルゴリズムの問題。

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

スポンサーリンク

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

シェルソートとは

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

  1. 一定間隔起きに要素を取り出し並び替え
  2. 一定間隔を縮めて要素を取り出し並び替え
  3. この流れを一定間隔が1になるまで繰り返していきます

 

それでは具体的に図解でシェルソートの流れを説明していきます。

 

暗記ポイント:シェルソートは一定間隔のおきに取り出した要素内でソートを繰り返す、整列アルゴリズム

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

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

  • 青グループ:4、1
  • オレンジグループ:3、8
  • 緑グループ:5、6
  • 灰色グループ:7、2

シェルソート手順1

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

次にグループ内で並び替えを行います。グループ内での並び替えの方法は、挿入ソート(基本挿入法)と同じです。

※挿入ソートとは「整列済み」と「未整列」にデータを分け、「未整列」データをひとつずつ「整列済み」データの中に挿入していく方法

  1. 青色グループの4と1を入れ替えます。
  2. 灰色グループの7と2を入れ替えます。

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

シェルソート手順2

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

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

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

シェルソートの流れ3

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

グループ内で並び替えを行います。

  1. 青色グループの5と4を入れ替えます。
  2. 橙色グループの3と2を入れ替えます。
  3. 橙色グループの8と7を入れ替えます。

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

シェルソートの手順4

スポンサーリンク

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

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

シェルソートの流れ5

 

 

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

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

\  いいね!フォローをお願いします /

© 2020 ITを分かりやすく解説