アカウント名:
パスワード:
ところで、私が通っていた大学のアルゴリズム教育では、いきなりクイックソートから入っていました。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
クラックを法規制強化で止められると思ってる奴は頭がおかしい -- あるアレゲ人
バブルソートで十分だと思うなあ (スコア:0)
私がバブルソートを学んだのは中学生の頃で、プログラミングに触りだしてから間もない頃です。
繰り返しと条件分岐さえ分かっていれば操作的にも概念的にも分かりやすいソーティングだったので、
理解するのに苦労は全くなかったように記憶しています。
ところで、私が通っていた大学のアルゴリズム教育では、いきなりクイックソートから入っていました。
受講しているのはドが付くほどの素人ばかりです。
結果、詳しい人間の所へ大勢の難民がなだれ込む形となりました。
Re:バブルソートで十分だと思うなあ (スコア:1)
「アルゴリズム」っていうくらいなら、O(n log n) でなきゃ意味ないと思ってたから、その変種を幾つか組んだな。
the.ACount
Re: (スコア:0)
nlognのアルゴリズム以外触ったことがなくて大丈夫でしたか?
Re:バブルソートで十分だと思うなあ (スコア:1, 参考になる)
私の通っていたところでもソートの最初はクイックソート(再帰処理による実装)だった記憶があります。
ただ、言語がSchemeだったのが理由ではないかと思います。
再帰を使った実装にする場合、クイックソートは理解しやすいアルゴリズムだと思います。
# 再帰を理解していることが前提ですが
Re: (スコア:0)
Re: (スコア:0)
俺はバブルソートなんて知らない小学生の頃に
配列をバブルソートで並び替えてたからな
習わなくても力作業で習得できるのがバルブソート
習うならクイックからで十分だろ
Re:バブルソートで十分だと思うなあ (スコア:1)
ここは同意しますが(というかソートなんて本読んで自学しろ、でいいよね...)、小学生の頃に教えられずとも自然に出来るのは、挿入ソートか選択ソートだと思うのですが...(私も実際そうだったし)。私がバブルソートというものを知ったのはソートを体系的に学んでからでしたし、あまり自然な発想で思い付かないと思うんですよね...。
習うべきは内部ソート(メモリに収まるデータの場合のソートを内部ソートと言います)なら
・クイックソート、マージソート、ヒープソート、計数(バケツ)ソート、基数ソート
ですかね(それぞれ「平均が高速」「安定で高速」、「最低が高速」、「データの種類により最高速(最後の2つ)」)という特長があります。
外部ソートならば d log_w d ソートというのがあります。データの種類によっては計数/基数ソートなども有効です。
数学屋(理論家)なら比較回数最小のソートである「merge insertion sort」も押さえておいた方が良いですね(非実用的なので多分Knuth本にしか載ってないと思いますが)。
他のソートは、こういうのもあるので他のアルゴリズムを考えるときや改良するときに手法を真似しましょう、という程度で良いと思います。
Best regards, でぃーすけ
Re: (スコア:0)
ちなみに、再帰を使った例としては非常に悪い物の一つ。
再帰を教えるのにクイックソートを使うのは許されるけど、
クイックソートを実装するなら再帰を使わないでやるべきだよね。
Re:バブルソートで十分だと思うなあ (スコア:1, すばらしい洞察)
Re: (スコア:0)
でも*BSDとPerlではqsortに再帰を使ってるんだよな…
しかもPerlで書き直した方が速い [drk7.jp]のにはびっくりした。
Re:バブルソートで十分だと思うなあ (スコア:1)
使ってないように見えますが [cpan.org]
Re:バブルソートで十分だと思うなあ (スコア:1)
そこから段階的に早いソートアルゴリズムを習っていったかな?
使ってたPCがクソ遅かったせいもあってソートアルゴリズムによる速度の違いが目に見えてわかった
今だとデータの件数を相当多くしないと目に見える違いが出てこない可能性があるし、クイックソートからというのもわからなくはないかなぁ
Re: (スコア:0)
不揃いの横棒を長さ順に並べ替えて見せるんだけど、ソートの方法ごとに並んでいく様子の違いが見えて楽しかった。
じりじりとそれこそ浮き上がって行くバブルソートや、ガサッガサッと一気に変わるクイックソートとかね。
Re:バブルソートで十分だと思うなあ (スコア:1, 参考になる)
http://en.wikipedia.org/wiki/Sorting_algorithm#Graphical_representations [wikipedia.org]
Re:バブルソートで十分だと思うなあ (スコア:1)
不思議だと思いませんでした?
ソートできるっていう証明って簡単なのかな。
Re:バブルソートで十分だと思うなあ (スコア:1)
Re:バブルソートで十分だと思うなあ (スコア:1)
1. ソートの状態が有限であること
2. 一度入れ替えられたペアが再度入れ替えられることがないこと
3. ソートされた状態でなければ入れ換えが発生すること
の3つを証明します。1.2.からアルゴリズムが終了することが分かり、3.から終了した状態はソートされた状態となっていることが分かります。
Best regards, でぃーすけ
Re: (スコア:0)
一番大きな(小さな)項目が一番端に来るのは明白でしょう。
次は端に寄せてしまったものを除いた残りに同じ処理をするだけ。
何が不思議なのか分かりません。