シェル‐ソート【shell sort】
シェルソート
【英】shell sort
シェルソートとは、ソート（整列）のアルゴリズムの一種で、挿入ソートを改良したアルゴリズムのことである。アメリカのコンピュータ科学者ドナルド・シェル（Donald Shell）によって考案された。
シェルソートの原型となっている挿入ソートは、もっとも単純なアルゴリズムの一つで、原理上ランダムな並びのデータを整列させるには効率が悪いという欠点がある。シェルソートでは、初めに大きなデータと小さなデータとを大まかに分け、その後に挿入ソートを行う、という手順を踏むことで、挿入ソートの効率化を図ろうとするものである。
シェルソートでは、まず一定間隔の全てのデータの組み合わせに対して小さなデータが前にくるよう交換処理を行う。これを、間隔を小さくしながら隣同士の交換になるまで同じことを繰り返し、最後には挿入ソートを行う。
なお、同じデータの順番がソート前後によって変化しないソート手法を「安定なソート」と言うが、挿入ソートとは違い、シェルソートは安定なソートではない。
シェルソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/06 14:29 UTC 版)
シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell's method）は、1959年にドナルド・シェルが開発した[2]ソートのアルゴリズム。挿入ソートの一般化[3]であり、配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムである。ただし、挿入ソートと異なり、安定ソートではなくなる。
- ^ “Shellsort & Comparisons”. 2016年3月20日閲覧。
- ^ a b c Shell, D. L. (1959). “A High-Speed Sorting Procedure”. Communications of the ACM 2 (7): 30–32. doi:10.1145/368370.368387.
- ^ a b c Knuth, Donald E. (1997). “Shell's method”. The Art of Computer Programming. Volume 3: Sorting and Searching (2nd ed.). Reading, Massachusetts: Addison-Wesley. pp. 83–95. ISBN 0-201-89685-0
- ^ a b 渡部有隆、 秋葉拓哉 (2015). プログラミングコンテスト攻略のためのアルゴリズムとデータ構造. マイナビ. p. 77. ISBN 978-4-83995-295-2
- ^ a b c Sedgewick, Robert (1996年). “Analysis of Shellsort and Related Algorithms”. 2021年8月5日閲覧。
- ^ a b Pratt, Vaughan Ronald (1979). Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences). Garland. ISBN 978-0-8240-4406-0
- ^ Sedgewick, Robert (1998). Algorithms in C. 1 (3rd ed.). Addison-Wesley. pp. 273–281. ISBN 978-0-201-31452-6
[続きの解説]
「シェルソート」の続きの解説一覧
- 1 シェルソートとは
- 2 シェルソートの概要
- 3 C++による実装例
- 4 脚注
シェルソートと同じ種類の言葉
- シェルソートのページへのリンク
