No.5ベストアンサー
- 回答日時:
ymmasayanです。
補足します。>5→2→1より5→3→2→1が時間はかかっているというのもたぶん予想ですよね?
>5→2→1より5→3→2→1が速いということも考えられますよね。
その通りです。失礼しました。
>そのサイトでは約半分ずつにしていたけど、この数値をどのように変化させていくかが
>シェルソートの高速化の重要な部分だと思いました。
その通りです。一応2分木やクイックソートと同じように2分割ずつにするのが
早いといわれています。
余談になりますが理論的には2進法の計算機よりも2.7進法の計算機が最も効率が良く、
クイックソートや二分木も2.7(=e:自然対数の底)を使うともっと効率が
よくなるそうです。(実際には不可能ですが)
シェルソートもそうなのかも知れません。
No.4
- 回答日時:
No.2、No.3のymmasayanです。
補足にお答えします。まず最初にいくつかお断りしておきますが、
(1)シェルソートは数あるソートの中でも、理解するのが最も難しい部類のソートです。
専門家の中でもきちんと理解していない人がいるくらいです。
(2)シェルソートは最初から最後まで、挿入ソートをしています。
5・3・2・1でやる場合5組の挿入ソートを同時並行で行い、
次にグループを組替えて3組の挿入ソートを同時並行的に行い、
次に2組、最後に1組で総仕上げを行います。
ここのところは言葉で説明してもなかなかわかりません。
挿入ソートに見えず隣接交換の変形に見えてしまうのです。
(3)シェルソートは原理的にも、又実際上も早いことはわかっています。
しかし本当にどれだけ速いのか研究され尽くしていません。
それではお答えです。
>僕はまだ終了直前までは適当に思えしてまいます。
>ソートの完成は全てが最後の挿入ソートに任されていて、
>それまでの処理は適当なソートだとしか思えません。
最後のソートが歯止めになっていることは間違いありません。
しかし途中のソートががんばってスピードを稼いでいるのです。
つまり遠く離れた数値を交換しておくことによって、最後のソートが
何回も1個ずつデータ移動しなくても済むようにしています。
適当に見えるのは、グループの合体やグループの組みなおしをしたときに
整列がくずれるのでそう見えるのだと思います。
>もし、最後のループ処理が
>while ( ... ) {
> 2つを比較し、右が大きければ交換し、そうでないなら>何もしない;
> ポインタを2つすすめる;
>}
>で済むなら、それまでのソートは質のいいものだと思い>ます。
何度もいうように前の方のソートには粗く大きく入れ替えて最後にスピードが
上がるようにするという使命があります。
もし前できちんと並べてしまったら計算量がn^2型になって意味がありません。
>5→2→1より5→3→2→1が、見た感じが完成に近いです。
>それは、適当なソートを行った回数が多いからだと思うので、
>見た感じが完成に近いというのは予想できたことでした。
その代わり時間はかかっているはずです。
>シェルは、挿入よりもかなり速かったです。
>速くなるというのが予想できなかったのが悔しいです。
途中で書きましたが大きく飛ばしておいてあとできちんと整列することで
スピードと正確さを保っているのです。
>もしかして、適当にソートと書いたのが、ランダムに並べ直すに見えましたか?
いえ、そんなことは有りません。適当に見えるのは2つ理由があって
遠くへ放り投げるのと、グループの組みなおし(統合)の判りにくさでしょう。
5→2→1より5→3→2→1が時間はかかっているというのもたぶん予想ですよね?
僕も5→2→1の方が速そうに思えますが、1より5→2→1が速いことから
5→2→1より5→3→2→1が速いということも考えられますよね。
そのサイトでは約半分ずつにしていたけど、この数値をどのように変化させていくかが
シェルソートの高速化の重要な部分だと思いました。
ヒープソートの木について少し分かってきました。
ありがとうございました。
No.3
- 回答日時:
No.2のymmasayanです。
補足します。>シェルは、途中まで適当に並べて、最後のところで挿入ソートで正確に並べるんですね。
>その最後の部分までは本当に適当でいいみたいですね。
適当という風に見えましたか。それは例が悪かったのですね。
データが16個だときれいに行くのですが。
8→4→2→1という風にグループの数が減っていきます。
それぞれのグループの中でそれぞれ同時並行的に挿入ソートをやっています。
ここがなかなか判りにくいところです。じっくり考えてみてください。
決して適当にやっているわけではありません。
>参考サイトで、なぜ5/2が3でなく2を採用したのか分からなかったけど、
5/2の件ですが、5→3→2→1という系列と
5→2→1という系列の2つが考えられますが、
本当はどちらでもいいのです。
ここでは効率のよさを考えて2を使ったのだと思います。
>最後のソートが全てきちんとやってくれているんだと分かりました。
これは違います。確かに前でどんなことが有っても最後のソートできちんとしてくれます。
でもソートのスピードという点を考えると前の方も適当では困るのです。
実際に前の方もまじめに挿入ソートをやっています。
次にヒープソートです。木になれていないと少しとっつきにくいでしょう。
参考URLがわかりにくかったですね。
http://www.heppoko-online.com/it/kiso.html
に変えましょう。
まずヒープを作る話です。上ほど小さい数字になるように並べます。
生年月日の若い人が上にくるようなものです。
次にソートです。
全部並べ終わると一番上を抜きます。すると出世競争が起こって
ヒープの並べ替えが起こります。
落ち着くと又一番上を抜きます。これを繰り返すと小さい順にデータが取り出せます。
つまり整列です。これがヒープソートです。
実際のヒープソートはやり方が少し違いますが、基本原理だけしっかり理解してください。
ありがとうございます。
http://www5d.biglobe.ne.jp/~tomoya03/shtml/algor …
について、僕はまだ終了直前までは適当に思えしてまいます。
5→3→2→1と5→2→1が考えられます。
実際に、そのサイトのサンプル値でやりました。
5→2→1
[20] (88) [32] (62) [18] (12) [15] (30) [52] (8)【2-処理前】
[52] (88) [32] (62) [20] (30) [18] (12) [15] (8)【2-処理後】
5→3→2→1
[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-処理後】
どっちの方法でも、この後、挿入ソートによってどんな並びであっても
完成することができます。
その最後の挿入ソートをする直前の値は、上に書いたように
5/2で、3を適用した場合と2を適用した場合で異なっています。
そのことから、ソートの完成は全てが最後の挿入ソートに任されていて、
それまでの処理は適当なソートだとしか思えません。
もし、最後のループ処理が
while ( ... ) {
2つを比較し、右が大きければ交換し、そうでないなら何もしない;
ポインタを2つすすめる;
}
で済むなら、それまでのソートは質のいいものだと思います。
5→2→1より5→3→2→1が、見た感じが完成に近いです。
それは、適当なソートを行った回数が多いからだと思うので、
見た感じが完成に近いというのは予想できたことでした。
シェルは、挿入よりもかなり速かったです。
シェルのまばらな2値の抽出は、既にソートされた配列への対策だけ
のように見えるんだけど、速くなるというのが予想できなかったのが
悔しいです。
もしかして、適当にソートと書いたのが、ランダムに並べ直すに見えましたか?
No.2
- 回答日時:
シェルソート・・隣接交換法の改良版と思われ勝ちですが、実は基本挿入法の改良版です。
http://www5d.biglobe.ne.jp/~tomoya03/shtml/algor …
ヒープソート・・ヒープは2分木ですが関係付けにポインターが要りません。
したがって配列で表すことが出来ます。高速のソートです。
http://www.heppoko-online.com/it/kiso.html
シェルのシステムを初めて知ることができました。
ありがとうございました。
シェルは、途中まで適当に並べて、最後のところで挿入ートで正確に並べるんですね。
その最後の部分までは本当に適当でいいみたいですね。
参考サイトで、なぜ5/2が3でなく2を採用したのか分からなかったけど、
最後のソートが全てきちんとやってくれているんだと分かりました。
下の参考サイトは画像はあったけど、文章が理解できませんでした。
No.1
- 回答日時:
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・【お題】絵本のタイトル
- ・【大喜利】世界最古のコンビニについて知ってる事を教えてください【投稿~10/10(木)】
- ・メモのコツを教えてください!
- ・CDの保有枚数を教えてください
- ・ホテルを選ぶとき、これだけは譲れない条件TOP3は?
- ・家・車以外で、人生で一番奮発した買い物
- ・人生最悪の忘れ物
- ・【コナン30周年】嘘でしょ!?と思った○○周年を教えて【ハルヒ20周年】
- ・ハマっている「お菓子」を教えて!
- ・最近、いつ泣きましたか?
- ・夏が終わったと感じる瞬間って、どんな時?
- ・10秒目をつむったら…
- ・人生のプチ美学を教えてください!!
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・都道府県穴埋めゲーム
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
10個の整数を入力して小さい順...
-
listboxの並び替え
-
System.IO.Directory.GetFiles...
-
VB6 任意の順番でのソート
-
あるディレクトリ内のファイル...
-
選択された範囲の中からx番目に...
-
構造体配列の並べ替え
-
ファイル名「1.jpg ~10.jpg~...
-
Excelですべての組合せ(重複組...
-
文字列をソートする方法
-
配列の問題
-
VBScriptで重複レコードを削除...
-
VBA基本構文の作り方 2列の...
-
qsort/クイックソートについて
-
C# DataGridView のヘッダーセ...
-
関数から配列を返すには?
-
C言語 配列の長さの上限
-
init関数の意味
-
配列を使わずに、変数名を動的...
-
C言語にて構造体のメンバがNULL...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
System.IO.Directory.GetFiles...
-
VB.NETでファイル名順にファイ...
-
C# DataGridView のヘッダーセ...
-
ファイル名「1.jpg ~10.jpg~...
-
構造体配列のソート
-
C# DataTableの行をソートしてD...
-
C言語・要素除去
-
Excelですべての組合せ(重複組...
-
あるディレクトリ内のファイル...
-
DataGridViewの昇順降順。
-
2次元配列を複数項目でソートし...
-
DataGridViewの複数列を連動し...
-
文字列をソートする方法
-
VBA基本構文の作り方 2列の...
-
n番目に大きい数を求めるアル...
-
DataGridViewでのソート制御
-
DataGridViewソート時に先頭行...
-
excel VBA リストビューの行...
-
Excel2010 /VBA ユーザー設定リ...
-
数字文字列のソート方法
おすすめ情報