シェルソートとヒープソート

質問

シェルソートとヒープソートの意味が分かりません。
他の有名なソートの考え方は分かりました。
考え方についての画像や動画があって、考え方について
説明されているサイトを紹介してください。

回答No.5

ymmasayan · ベストアンサー

ymmasayanです。補足します。

＞５→２→１より５→３→２→１が時間はかかっているというのもたぶん予想ですよね？
＞５→２→１より５→３→２→１が速いということも考えられますよね。

その通りです。失礼しました。

＞そのサイトでは約半分ずつにしていたけど、この数値をどのように変化させていくかが
＞シェルソートの高速化の重要な部分だと思いました。

その通りです。一応２分木やクイックソートと同じように２分割ずつにするのが
早いといわれています。

余談になりますが理論的には２進法の計算機よりも２.７進法の計算機が最も効率が良く、
クイックソートや二分木も２．７（＝ｅ：自然対数の底）を使うともっと効率が
よくなるそうです。（実際には不可能ですが）
シェルソートもそうなのかも知れません。

お礼

ありがとうごさいました。
ソートのアルゴリズムは置くが深くて面白そうですね。
少しずつ理解を深めていきたいです。

回答No.4

ymmasayan

No.2、No.3のymmasayanです。補足にお答えします。

まず最初にいくつかお断りしておきますが、
（１）シェルソートは数あるソートの中でも、理解するのが最も難しい部類のソートです。
　　専門家の中でもきちんと理解していない人がいるくらいです。
（２）シェルソートは最初から最後まで、挿入ソートをしています。
５・３・２・１でやる場合５組の挿入ソートを同時並行で行い、
次にグループを組替えて３組の挿入ソートを同時並行的に行い、
次に２組、最後に１組で総仕上げを行います。
ここのところは言葉で説明してもなかなかわかりません。
挿入ソートに見えず隣接交換の変形に見えてしまうのです。
（３）シェルソートは原理的にも、又実際上も早いことはわかっています。
しかし本当にどれだけ速いのか研究され尽くしていません。

それではお答えです。

＞僕はまだ終了直前までは適当に思えしてまいます。
＞ソートの完成は全てが最後の挿入ソートに任されていて、
＞それまでの処理は適当なソートだとしか思えません。

最後のソートが歯止めになっていることは間違いありません。
しかし途中のソートががんばってスピードを稼いでいるのです。
つまり遠く離れた数値を交換しておくことによって、最後のソートが
何回も１個ずつデータ移動しなくても済むようにしています。

適当に見えるのは、グループの合体やグループの組みなおしをしたときに
整列がくずれるのでそう見えるのだと思います。

＞もし、最後のループ処理が
＞while ( ... ) {
＞　2つを比較し、右が大きければ交換し、そうでないなら＞何もしない;
＞　ポインタを2つすすめる;
＞}
＞で済むなら、それまでのソートは質のいいものだと思い＞ます。

何度もいうように前の方のソートには粗く大きく入れ替えて最後にスピードが
上がるようにするという使命があります。
もし前できちんと並べてしまったら計算量がｎ＾２型になって意味がありません。

＞５→２→１より５→３→２→１が、見た感じが完成に近いです。
＞それは、適当なソートを行った回数が多いからだと思うので、
＞見た感じが完成に近いというのは予想できたことでした。

その代わり時間はかかっているはずです。

＞シェルは、挿入よりもかなり速かったです。
＞速くなるというのが予想できなかったのが悔しいです。

途中で書きましたが大きく飛ばしておいてあとできちんと整列することで
スピードと正確さを保っているのです。

＞もしかして、適当にソートと書いたのが、ランダムに並べ直すに見えましたか？

いえ、そんなことは有りません。適当に見えるのは２つ理由があって
遠くへ放り投げるのと、グループの組みなおし（統合）の判りにくさでしょう。

お礼

５→２→１より５→３→２→１が時間はかかっているというのもたぶん予想ですよね？
僕も５→２→１の方が速そうに思えますが、１より５→２→１が速いことから
５→２→１より５→３→２→１が速いということも考えられますよね。
そのサイトでは約半分ずつにしていたけど、この数値をどのように変化させていくかが
シェルソートの高速化の重要な部分だと思いました。

ヒープソートの木について少し分かってきました。
ありがとうございました。

回答No.3

ymmasayan

No.2のymmasayanです。補足します。

＞シェルは、途中まで適当に並べて、最後のところで挿入ソートで正確に並べるんですね。
＞その最後の部分までは本当に適当でいいみたいですね。

適当という風に見えましたか。それは例が悪かったのですね。
データが１６個だときれいに行くのですが。
８→４→２→１という風にグループの数が減っていきます。
それぞれのグループの中でそれぞれ同時並行的に挿入ソートをやっています。
ここがなかなか判りにくいところです。じっくり考えてみてください。
決して適当にやっているわけではありません。

＞参考サイトで、なぜ5/2が3でなく2を採用したのか分からなかったけど、

５／２の件ですが、５→３→２→１という系列と
５→２→１という系列の２つが考えられますが、
本当はどちらでもいいのです。
ここでは効率のよさを考えて２を使ったのだと思います。

＞最後のソートが全てきちんとやってくれているんだと分かりました。

これは違います。確かに前でどんなことが有っても最後のソートできちんとしてくれます。
でもソートのスピードという点を考えると前の方も適当では困るのです。
実際に前の方もまじめに挿入ソートをやっています。

次にヒープソートです。木になれていないと少しとっつきにくいでしょう。
参考ＵＲＬがわかりにくかったですね。
http://www.heppoko-online.com/it/kiso.html
に変えましょう。

まずヒープを作る話です。上ほど小さい数字になるように並べます。
生年月日の若い人が上にくるようなものです。

次にソートです。
全部並べ終わると一番上を抜きます。すると出世競争が起こって
ヒープの並べ替えが起こります。
落ち着くと又一番上を抜きます。これを繰り返すと小さい順にデータが取り出せます。
つまり整列です。これがヒープソートです。

実際のヒープソートはやり方が少し違いますが、基本原理だけしっかり理解してください。

お礼

ありがとうございます。
http://www5d.biglobe.ne.jp/~tomoya03/shtml/algorithm/SSort.htm
について、僕はまだ終了直前までは適当に思えしてまいます。

５→３→２→１と５→２→１が考えられます。

実際に、そのサイトのサンプル値でやりました。

５→２→１
[20] (88) [32] (62) [18] (12) [15] (30) [52] (8)【2-処理前】
[52] (88) [32] (62) [20] (30) [18] (12) [15] (8)【2-処理後】

５→３→２→１
[20] (88) {32} [62] (18) {12} [15] (30) {52} [8]【3-処理前】
[62] (88) {52} [20] (30) {32} [15] (18) {12} [8]【3-処理後】
[62] (88) [52] (20) [30] (32) [15] (18) [12] (8)【2-処理前】
[62] (88) [52] (62) [30] (30) [15] (12) [12] (8)【2-処理後】

どっちの方法でも、この後、挿入ソートによってどんな並びであっても
完成することができます。
その最後の挿入ソートをする直前の値は、上に書いたように
５／２で、３を適用した場合と２を適用した場合で異なっています。
そのことから、ソートの完成は全てが最後の挿入ソートに任されていて、
それまでの処理は適当なソートだとしか思えません。
もし、最後のループ処理が
while ( ... ) {
　2つを比較し、右が大きければ交換し、そうでないなら何もしない;
　ポインタを2つすすめる;
}
で済むなら、それまでのソートは質のいいものだと思います。

５→２→１より５→３→２→１が、見た感じが完成に近いです。
それは、適当なソートを行った回数が多いからだと思うので、
見た感じが完成に近いというのは予想できたことでした。

シェルは、挿入よりもかなり速かったです。
シェルのまばらな2値の抽出は、既にソートされた配列への対策だけ
のように見えるんだけど、速くなるというのが予想できなかったのが
悔しいです。

もしかして、適当にソートと書いたのが、ランダムに並べ直すに見えましたか？

回答No.2

ymmasayan

シェルソート・・隣接交換法の改良版と思われ勝ちですが、実は基本挿入法の改良版です。
http://www5d.biglobe.ne.jp/~tomoya03/shtml/algorithm/SSort.htm

ヒープソート・・ヒープは２分木ですが関係付けにポインターが要りません。
したがって配列で表すことが出来ます。高速のソートです。
http://www.heppoko-online.com/it/kiso.html

お礼

シェルのシステムを初めて知ることができました。
ありがとうございました。
シェルは、途中まで適当に並べて、最後のところで挿入ートで正確に並べるんですね。
その最後の部分までは本当に適当でいいみたいですね。
参考サイトで、なぜ5/2が3でなく2を採用したのか分からなかったけど、
最後のソートが全てきちんとやってくれているんだと分かりました。

下の参考サイトは画像はあったけど、文章が理解できませんでした。

回答No.1

asuca

参考URL何かどうですか？

参考URL：

http://www.inet-lab.org/ted/program/progcontents04.html

お礼

ありがとうございました。
木を知らなかったので役立ちました。