初めて学ぶソートアルゴリズムは何がいい? 147
タレコミ by saitoh
saitoh 曰く、
ソートについて学ぶといえばまずストレートインサーションあたりから入り、バブルソートが出てくるのはソートの章の中頃、というのが昔の定番だったように思います。
ところが最近では、定番としてバブルソートを出してくる解説WEBページや、 ソートの章の最初の事例がバブルソート(単純交換ソート)を出してくるアルゴリズムとデータ構造の書籍があるのを発見し、びっくりした。
はたしてソートについて学び始めるときに、最初に取り組むあるごり図はどれが適切なのでしょうか。 バブルソートははたして適任でしょうか?
ボゴソートで「遅さ」を感じてもらったらどうか (スコア:4, おもしろおかしい)
遅さを体感できないケースが増えていると思います。
やっぱり、速いソートのメリットを理解するためには、
まずとんでもなく遅いソートを知らないといけないんじゃ・・・
というわけで ボゴソート [wikipedia.org] などはいかがでしょうか。
教わる側が「そんなの実用的じゃないよwww」と食いついてくれれば、
より速いソートを教えるのも楽に・・・なってくれたらいいなあ。
Re:ボゴソートで「遅さ」を感じてもらったらどうか (スコア:2, 参考になる)
100万要素くらい与えてやると O(N 2)-time のソートは撃沈してくれるかと思いますよ。
Re:ボゴソートで「遅さ」を感じてもらったらどうか (スコア:2, 興味深い)
> まずとんでもなく遅いソートを知らないといけないんじゃ・・・
>
> というわけで ボゴソート などはいかがでしょうか。
私が後輩から受けた質問
「どうやれば効率よくシャッフルできますか?」
お題:メモリ消費が『多い』ソート (スコア:1)
単純な好奇心なんですが
「とんでもなくメモリ消費が多いソート」
というのは、あるんでしょうか。
ただし「無駄な途中経過を全部メモリに置いておく」と
いうようなのは無しの方向で。
やっぱりバブルソート (スコア:4, 興味深い)
・何も教えない段階で生徒にソートプログラムを宿題として出す。
・真面目に宿題やってきた生徒に発表させる。大抵がバブルソートだった。
・バブルソートが O(n^2)であることを教える。
・もっと早いソート方法はということで、いろんなソートアルゴリズムを教える。
・安定ソートかどうかといったことも教える。
・生徒が「マージソート最高!」と思いはじめたところでクイックソートを教える。
この順序で教えてもらったおかげで計算量の概念がすんなり身に付いたし、アルゴリズムを学ぶ面白さにも目覚めました。
Re:やっぱりバブルソート (スコア:1)
どういう順序で学んでいくと(どういう目的に対して)よいのか、と考えるとき
最初が何ソートかというだけでなく次、その次、も併せて考えたほうがいいですよね。
元記事で挙げておられる「定番としてバブルソートを出してくる解説WEBページ [codezine.jp]」もメモリに置ききれない大量のデータを処理するのに適したソート方法として次にマージソートを説明してますね。というかマージソートを説明するための枕にバブルソートを出したんでしょう。
=^..^=
Enjoy Computing, Skiing, as much as Horse Racing.
レポートのコピペ対策 (スコア:1, 興味深い)
それに対する対策として、
1、そのアルゴリズムを実装したプログラムの速度を競わせて、上位数名に高得点を与える。
2、速度や安定性は無視して良いので、独創的なアイデアに高得点を与える。
同じアイデアのレポートが少なければ少ないほど高得点。
などがありました。
後者はソートのような単純なアルゴリズムの場合にはあまり適さないけれど、すこし
複雑なアルゴリズムの場合には非常に効果的でした。他人のアイデアをパクッただけの
人は絶対に高得点はもらえません。高得点がもらえるのは、自分でアイデアを出して、
且つそれを人に見せなかった人だけです。
セレクション・ソート (スコア:2, すばらしい洞察)
The Art of Computer Programming 第2版 (スコア:2, 興味深い)
だと第3巻で, 最初に挿入ソートについて述べられています.
Re:The Art of Computer Programming 第2版 (スコア:1)
で, 学ぶ前に自分で考えてみることを強く勧めるとも書かれています.
Re:The Art of Computer Programming 第2版 (スコア:2, おもしろおかしい)
順序の問題? (スコア:2, 参考になる)
どのアルゴリズムをどういう順で学ぶかという事よりも
ソートのように一見単純に思える処理にも複数の解決方法があって
実装/テスト/実行のコストも違ってくる、という事が分かるのが
大事なんじゃないでしょうか?
#ソートアルゴリズムをソートしてみる試みはソートマニア的には正しいかも
そんなことよりも、 (スコア:2, おもしろおかしい)
-------- tear straight across --------
Re:そんなことよりも、 (スコア:1)
いろいろ習ったけど、それしか理解できんかったとか。
単純挿入法 (スコア:2, 参考になる)
こんな簡単なソート方法でも、与えるデータによって比較回数が劇的に変化する事が判る。
次に実用品としてヒープソート、マージソートを。 速い上に安定した手法を教える。
あまった時間で、運任せの方法として、クィックソートと、特殊ケースで有効な方法として、分布数えソートを教える。
で、最後に、これらを「実装するな」と言って締めます。
通常は、ライブラリにソートロジックがあるので、それを使え。
件数が多く、メモリに載らない場合は、DBMSに突っ込んで処理しろ。
コーディング/デバッグの時間を考えたら、自力実装するのは無駄ですから。
notice : I ignore an anonymous contribution.
Unpluggedということで,ちょっとはずれますが (スコア:2, 興味深い)
バブルの次がコムなら (スコア:1)
古典的かつ実用性のあるソートを選ぶなら、挿入→クイック→マージ→あと適当に追加のメモリ使用量が少なくて比較の計算量が最悪でもO(n log n)なアルゴリズムを一つ、の順でしょうね。
Re:バブルの次がコムなら (スコア:4, すばらしい洞察)
汎用ソートなら普通は組まないでしょうね。
でも「組まない」と「組めない」じゃ天地の開きがあるんですよ。
たかがソート一つ満足に組めない人が書いたプログラムって見るに耐えないし、
現実問題としてもアルゴリズムの考え方が理解できてないから、ちょっとした
文字列処理やfizz-buzz問題だって自力では解きかたを考えられなかったりします。
Re:バブルの次がコムなら (スコア:1)
# あれはバブルソートっていうのか…
# これ一つしか組めないやw
Re:バブルの次がコムなら (スコア:2, 興味深い)
おっと、それが奇偶転置ソート [wikipedia.org]かっ!
マージソート (スコア:1)
意外と判りやすく、すっきりしていて、その癖早い。
Divide and Concur の原理も踏襲している。
計算量も安定している。
実は並列処理もしやすい(特に部分ソートが完全に終わらなくても、次のマージが始められるところとか)
選択ソートと比べてどちらが早いのか、どうして早いのか、の説明を開始して計算量とかの説明へと移行するのもやりやすい。
fjの教祖様
Re:マージソート (スコア:2, すばらしい洞察)
何も教わらない人がカード(1-13と範囲が決まってることが自明)をソートしてと言われると机が使える限り絶対にbin sortをすると思うんだが.
そうだ! (スコア:1, おもしろおかしい)
Re:そうだ! (スコア:1)
アルゴリズムも大事だけど (スコア:1)
--
#バカ正直にソートして終了予定時間が12000時間後とかってね・・・
Re:アルゴリズムも大事だけど (スコア:2, おもしろおかしい)
ちゃんと終了時に「オカエリナサイ」と表示されるので問題ありません。
# 12000に引っかかっただけだけど。
Your 金銭的 potential. Our passion - Micro$oft
Tsukitomo(月友)
見落としがちなビンソート (スコア:1)
# 実用例として有名なところでは初代PSのポリゴン描画はビンソートベース。
スパゲッティソート (スコア:1)
O(N)なんだぜ?
love && peace && free_software
t-nissie
Re:スパゲッティソート (スコア:1)
メカニカルな実装のほうが向いているアルゴリズムのような気がします。
ハードウェア(半導体素子)で実装することを考えると、バブルソートは結構良いアルゴリズムですね。
シカケが単純で実装規模もコンパクトだし、何回回せば完全にソートが終わるか確実に分かるから、
終了条件もカウンタをチェックするだけの処理に単純化できる。ハードウェアの場合には、
処理が終了するまでの「時間」がどれくらいなのか確実に分かるほうが大事な場合も結構ある。
ビーズソートすごい (スコア:1)
知りませんでした。
リンク先のさらにリンク先のアニメーションを見れば一発で理解できます。
love && peace && free_software
t-nissie
Re:ビーズソートすごい (スコア:1)
http://mgs.ibisc.univ-evry.fr/ImageGallery/EXEMPLES/BeadSort/index.html [univ-evry.fr]
ソートの後はまたソート(オフトピ) (スコア:1)
ソートを学ぶということに単にデータを並べ替えるだけじゃなくて、データを並べ替える、データに順位をつけるということの意味に気づいたのは結構あとになってから。
計算幾何周辺の話かな。
かなり独学で学んでるんで気づくのに遅れた感があるけど、真っ当な教育を受けている人はソートの講義を受けた後にそういう点も教わるんだろうか。
妖精哲学の三信
「だらしねぇ」という戒めの心、「歪みねぇ」という賛美の心、「仕方ない」という許容の心
Re:ソートの後はまたソート(オフトピ) (スコア:1)
えぇ、「結構あと」にならないと判らない事なので、普通は授業では教えてもらえません。
それは、卒論で地獄を見ている最中に降ってくる天使のささやきの一つです。
fjの教祖様
Re:そもそも論として (スコア:4, すばらしい洞察)
・成果を出すやり方は一通りではない
・うまいやり方を考えないと、桁違いのコストがかかってしまう
というのを実感するにはいい教材じゃないかと思いますが。
ソート以外の問題に対しても「分割統治すればいけるんじゃね?」などと問題解決のヒントになることもあるだろうし。
> 自分でソートルーチンを作りたがる子が絶対出てくるんですよ。
納得するまで作らせればいいんじゃないですかね。マルチコアに最適化されたソートルーチン作らせるとか、問題発見/解決のいい練習になると思いますよ。
#いつまでも自作ソートにこだわっているようだと問題でしょうけど。
Re:そもそも論として (スコア:2, すばらしい洞察)
ソートを学ぶのはソートプログラムを自分で書けるようになるためではない。
Re:そもそも論として (スコア:2)
>作れないなら外注しろ・外注先が見つからないならそれは誰も求めていないものだ、
といった無能な経営者の丸投げ思想こそが、SIerをITドカタとして7K職場に貶めた元凶ですよね。
Re:そもそも論として (スコア:1, おもしろおかしい)
#外注のメリットって年収?内製することで生じる固定費をカットできてそれなりキャッシュフローで会社回せればいいってポリシーなんじゃないの?
きれいに誤解していますね (スコア:1)
Re:そもそも論として (スコア:1, すばらしい洞察)
しかも創造性のない、モノを右から左へ転がす類の(ライブドアは転がしてすらいない?)、です。
私は、ライブドアはあくまで「成功」しただけであって、その存在価値は全然無いと思っています。
>自分でソートルーチンを作りたがる子が絶対出てくるんですよ
素晴らしいことじゃないですか。「製造」から「創造」に変わる瞬間ですよ。
(実際、この「創造への一線」を中々超えられない人は多い)
最初は車輪の再発明であっても、それが徐々に高じていってやがて新規性のあるものに到達していきます。
単純な製造なんてのは誰でもできるから価値は低く、創造が伴って初めて価値を生み出すものだと思います。
創造するには、発想する力が必要です。
発想するためには、思考の限界線を知ったり、約束事を学んでおく必要があります。
ソートの仕方なんてのは、その約束事の一つでしょう。
こうした積み重ねが創造性を育んでいき、「無くてはならない」存在となるための第一歩なのだと思います。
利益が上がれば有象無象でもいい、というのなら話は別ですが。
Re:そもそも論として (スコア:1, すばらしい洞察)
Re:そもそも論として (スコア:1)
ただ、自分が何になりたいのか、あるいは、どういう人材を育てたいのかによるけどね。やっぱり、自前でソートを書かなきゃいけない場面もある。クイックソート・マージソートを学ぶことで再帰呼出や分割統治法を知ることができる。これはソート以外に応用が利く。
さらに、再帰呼出のループ化とか、クイックソートをnが小さいときにインサーションソートにしたり、という考え方も、他への応用が利く。
そういう応用の利かないプログラマ(?)を集めてやるビジネスも確かにビジネスの一種だから、否定はしないけど、それとはレベルの違うビジネスもあるってことだろうね。
Re:バブルが先でいいんでないかい (スコア:1)
「最初に学ぶ」ならバブルソートでもいいと思います。
そんでバブルソートの項目は「アルゴリズムとデータ構造」の講義の
最初の5分で終わらせて、クイックソート、ヒープソート、マージソートの
ような基本的なアルゴリズムは一通り教わって、さらにそのうちの一つや二つは
自分で作ってみてスピードを競うのが普通だと思ってました。
世の中には知るべき項目は無数にあるわけで、ソートアルゴリズムは
そのほんの入り口にすぎません。
Re:バブルソートで十分だと思うなあ (スコア:1)
「アルゴリズム」っていうくらいなら、O(n log n) でなきゃ意味ないと思ってたから、その変種を幾つか組んだな。
the.ACount
Re:バブルソートで十分だと思うなあ (スコア:1, 参考になる)
私の通っていたところでもソートの最初はクイックソート(再帰処理による実装)だった記憶があります。
ただ、言語がSchemeだったのが理由ではないかと思います。
再帰を使った実装にする場合、クイックソートは理解しやすいアルゴリズムだと思います。
# 再帰を理解していることが前提ですが
Re:バブルソートで十分だと思うなあ (スコア:1)
そこから段階的に早いソートアルゴリズムを習っていったかな?
使ってたPCがクソ遅かったせいもあってソートアルゴリズムによる速度の違いが目に見えてわかった
今だとデータの件数を相当多くしないと目に見える違いが出てこない可能性があるし、クイックソートからというのもわからなくはないかなぁ
Re:バブルソートで十分だと思うなあ (スコア:1)
不思議だと思いませんでした?
ソートできるっていう証明って簡単なのかな。
Re:ソートしたいのか、ソートさせたいのか (スコア:3, おもしろおかしい)
Re:逆は? (スコア:1)
真面目に答えるとシャッフルはO(N)の処理なので、さして難しくありません。必要なのは良い乱数源だけです。
fjの教祖様
Re:そんなもの覚えて意味があるの? (スコア:1)
実際にはコードを書かないというのはわかるけど、5分でクイックソートが書けるくらいの能力はやっぱり必要だと思うよ。
車輪の再発明はいらないけど、車輪の開発演習は必要。
Re:難しい事解らないので (スコア:2)
エクセルにコピペして並び変え!
マクロの基本は検索置換(by y.mikome)