2021-04-10ある程度プログラミングに慣れた人向けの練習問題の一つとして、整列アルゴリズム(ソート)の実装があります。この記事では、シェルソートを用いた配列データの整列をプログラムに実装する方法について解説しています。シェルソートの概要プログラムを作成する前に、シェルソートについての簡単な説明を行います。シェルソートとは、配列データの要素を整列させる整列アルゴリズム(ソート)の一つです。アルゴリズムシェルソートのアルゴリズムは挿入ソートという別の整列アルゴリズムが基になっています。挿入ソートについては以下の記事で解説しているので参考にして下さい。挿入ソートでは、「各要素を整列が完了した領域の適切な位置に挿入する」という操作を行い、対象の配列が整列された状態に近い時に効率が良くなるという特徴があります。シェルソートはこの特徴を利用し、対象の配列を大まかに整列された状態にしてから徐々に完全な整列状態に近づいていきます。具体的には、対象の配列から一定間隔で抜き出した要素間で挿入ソートによる整列を行い、要素を抜き出す間隔を狭めながらこれを繰り返します。要素を抜き出す間隔stepは互いに素であると効率が良いとされており、一般的にstep=step*3+1の式が用いられるケースが多いです。計算量シェルソートの計算量は配列から要素を抜き出す間隔stepの決め方に依存しています。stepの値をstep=step*2+1の式で求める場合はO記法で計算量がO(N^1.5)程度、step=step*3+1の場合はO記法で計算量がO(N^1.2)程度です。実際にプログラムを作成してみる前述のアルゴリズムに従ってプログラムを作成します。プログラム作成の手順プログラム作成の手順は以下の通りです。上記の手順に従ってプログラムを作成します。使用する言語はC言語です。0;}このプログラムを実行すると以下の出力結果が得られます。9この出力結果から無事にシェルソートが実装できていることがわかります。本記事を読まれた方には、以下の記事もおすすめします。@htt_mdk・ITエンジニア・プログラミング関連の情報をメインに発信していきます。ProDesigns。