シェルソート | Programming Place Plus アルゴリズムとデータ構造編【整列アルゴリズム】 第５章

トップページ – アルゴリズムとデータ構造編 この章の概要 🔗 この章の概要です。 シェルソート 間隔の決め方 シェルソートのプログラム例 シェルソートの性能 まとめ 練習問題 参考リンク 更新履歴 シェルソート 🔗 この章では、シェルソートを取り上げます。 「シェル」は考案者 Donald L. Shell の名前から来ています。 シェルソートは、改良挿入ソート（改良挿入法）と呼ばれることもあります。その呼び名のとおり、挿入ソート（第４章）をよりうまく使うことで、効率の向上を図ります。 シェルソートでは、挿入ソートを離れた要素どうしで挿入ソートをおこなうことを何度か繰り返します。これだけ聞くと、かえって遅くなるように思えますが、挿入ソートの適用の仕方に工夫があります。 まず、適当な間隔 h を決定し、この間隔だけ離れた要素同士で挿入ソートを行います。その後、h を少し狭めて、やはりそ