パスワードを忘れた？ アカウント作成
Close
33209 submission
教育

初めて学ぶソートアルゴリズムは何がいい？ 147

タレコミ by saitoh
saitoh 曰く、
ソートについて学ぶといえばまずストレートインサーションあたりから入り、バブルソートが出てくるのはソートの章の中頃、というのが昔の定番だったように思います。

ところが最近では、定番としてバブルソートを出してくる解説WEBページや、 ソートの章の最初の事例がバブルソート（単純交換ソート）を出してくるアルゴリズムとデータ構造の書籍があるのを発見し、びっくりした。

はたしてソートについて学び始めるときに、最初に取り組むあるごり図はどれが適切なのでしょうか。 バブルソートははたして適任でしょうか？
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

初めて学ぶソートアルゴリズムは何がいい？ More

  • 最近のマシンは速いので、（データが少ない場合には）バブルソートでも
    遅さを体感できないケースが増えていると思います。

    やっぱり、速いソートのメリットを理解するためには、
    まずとんでもなく遅いソートを知らないといけないんじゃ・・・

    というわけで ボゴソート [wikipedia.org] などはいかがでしょうか。

    教わる側が「そんなの実用的じゃないよｗｗｗ」と食いついてくれれば、
    より速いソートを教えるのも楽に・・・なってくれたらいいなあ。

  • やっぱりバブルソート (スコア:4, 興味深い)

    by Anonymous Coward on 2008年08月23日 14時54分 (#1408470)
    15年ほど前に情報工学科で学びましたが、まずバブルソートからでした。
    ・何も教えない段階で生徒にソートプログラムを宿題として出す。
    ・真面目に宿題やってきた生徒に発表させる。大抵がバブルソートだった。
    ・バブルソートが O(n^2)であることを教える。
    ・もっと早いソート方法はということで、いろんなソートアルゴリズムを教える。
    ・安定ソートかどうかといったことも教える。
    ・生徒が「マージソート最高!」と思いはじめたところでクイックソートを教える。
    この順序で教えてもらったおかげで計算量の概念がすんなり身に付いたし、アルゴリズムを学ぶ面白さにも目覚めました。
    • 私もそう思います。
      どういう順序で学んでいくと（どういう目的に対して）よいのか、と考えるとき
      最初が何ソートかというだけでなく次、その次、も併せて考えたほうがいいですよね。

      元記事で挙げておられる「定番としてバブルソートを出してくる解説WEBページ [codezine.jp]」もメモリに置ききれない大量のデータを処理するのに適したソート方法として次にマージソートを説明してますね。というかマージソートを説明するための枕にバブルソートを出したんでしょう。
      --
      =^..^=
      Enjoy Computing, Skiing, as much as Horse Racing.
      シェア
      親コメント

  • セレクション・ソート (スコア:2, すばらしい洞察)

    by Another Coward (33409) on 2008年08月23日 13時45分 (#1408429) 日記
    直感的で理解しやすいのは、セレクション・ソート (選択ソート) だと思う。

  • The Art of Computer Programming 第2版 (スコア:2, 興味深い)

    by SteppingWind (2654) on 2008年08月23日 13時56分 (#1408437)

    だと第3巻で, 最初に挿入ソートについて述べられています.

  • 順序の問題？ (スコア:2, 参考になる)

    by myzn (1265) on 2008年08月23日 14時18分 (#1408450)
    ソートの研究家を目指すのなら話は別ですが…。

    どのアルゴリズムをどういう順で学ぶかという事よりも
    ソートのように一見単純に思える処理にも複数の解決方法があって
    実装/テスト/実行のコストも違ってくる、という事が分かるのが
    大事なんじゃないでしょうか？

    #ソートアルゴリズムをソートしてみる試みはソートマニア的には正しいかも

  • そんなことよりも、 (スコア:2, おもしろおかしい)

    by black-hole (9124) on 2008年08月23日 14時35分 (#1408462) ホームページ 日記
    qsort(3) [man.cx]の使い方がわからなくて、自前でソート処理をコーディングする奴を何とかしてください＞＜
    --
    -------- tear straight across --------

  • 単純挿入法 (スコア:2, 参考になる)

    by Dobon (7495) on 2008年08月23日 15時20分 (#1408487) 日記
    単純挿入法を最初に。
    こんな簡単なソート方法でも、与えるデータによって比較回数が劇的に変化する事が判る。

    次に実用品としてヒープソート、マージソートを。　速い上に安定した手法を教える。

    あまった時間で、運任せの方法として、クィックソートと、特殊ケースで有効な方法として、分布数えソートを教える。

    で、最後に、これらを「実装するな」と言って締めます。
    　通常は、ライブラリにソートロジックがあるので、それを使え。
    　件数が多く、メモリに載らない場合は、ＤＢＭＳに突っ込んで処理しろ。

    コーディング／デバッグの時間を考えたら、自力実装するのは無駄ですから。
    --
    notice : I ignore an anonymous contribution.
  • 最近流行りのComputer Science Unplugged [csunplugged.com]ではこういうこと [google.com]を子供たちにやらせたりしています。
  • 次にコムソートを教えるなら、バブルソートから入って、ソート問題の複雑さに触れさせていくのもいいかもしれませんが。

    古典的かつ実用性のあるソートを選ぶなら、挿入→クイック→マージ→あと適当に追加のメモリ使用量が少なくて比較の計算量が最悪でもO(n log n)なアルゴリズムを一つ、の順でしょうね。
  • なにも教わらない場合、人は「選択ソート」を使うことが多い。なので、まず自分がどのようにモノを整列させるのか、トランプなどで自覚させて、それは「選択ソートと言うんだよ」と教えた上で、本格的に教える最初のソートアルゴリズムは何? という質問だと考える事にすると、私はマージソートが良いとおもいます。

    意外と判りやすく、すっきりしていて、その癖早い。
    Divide and Concur の原理も踏襲している。
    計算量も安定している。
    実は並列処理もしやすい(特に部分ソートが完全に終わらなくても、次のマージが始められるところとか)

    選択ソートと比べてどちらが早いのか、どうして早いのか、の説明を開始して計算量とかの説明へと移行するのもやりやすい。
    --
    fjの教祖様

  • そうだ！ (スコア:1, おもしろおかしい)

    by Anonymous Coward on 2008年08月23日 14時25分 (#1408454)
    ソートアルゴリズムを教える順番をソートするアルゴリズムを作れば良いんだよ！！１１！！１！１！！！１１１！ぬ
  • 実データそのものを並べ替えるのは無駄が多いってことも教えていくといいよ

    --
    #バカ正直にソートして終了予定時間が12000時間後とかってね･･･

    • Re:アルゴリズムも大事だけど (スコア:2, おもしろおかしい)

      by Tsukitomo (22680) on 2008年08月23日 18時51分 (#1408577) 日記
      > #バカ正直にソートして終了予定時間が12000時間後とかってね･･･

      ちゃんと終了時に「オカエリナサイ」と表示されるので問題ありません。

      # 12000に引っかかっただけだけど。
      --
      Your 金銭的 potential. Our passion - Micro$oft

      Tsukitomo（月友）
      シェア
      親コメント
  • 最初に学ぶべきという議論から外れますが、制約が多く使い道が無さそうな上に何の工夫も無さそうなイメージなためか、「アルゴリズムの授業」ではすっぽり抜け落ち気味に思えるビンソート。工夫して使える場面を見つければかなりの威力なので知っておくべきかと。 それ自体は頑張って勉強する程に複雑なアルゴリズムじゃないけど、どういう場面でどういう風に使えるか・・・とかを。

    # 実用例として有名なところでは初代PSのポリゴン描画はビンソートベース。
  • で、スパゲッティソート [wikipedia.org]は半導体素子の中でできるようになったのかい？
    O(N)なんだぜ？
    --
    love && peace && free_software
    t-nissie
  • ソートを学んだ後にいろんな問題が結局はソート・データの順序付けという問題に落ち着くことに気づく。
    ソートを学ぶということに単にデータを並べ替えるだけじゃなくて、データを並べ替える、データに順位をつけるということの意味に気づいたのは結構あとになってから。
    計算幾何周辺の話かな。
    かなり独学で学んでるんで気づくのに遅れた感があるけど、真っ当な教育を受けている人はソートの講義を受けた後にそういう点も教わるんだろうか。
    --
    妖精哲学の三信
    「だらしねぇ」という戒めの心、「歪みねぇ」という賛美の心、「仕方ない」という許容の心

    • ソートを学ぶということに単にデータを並べ替えるだけじゃなくて、データを並べ替える、データに順位をつけるということの意味に気づいたのは結構あとになってから。
      計算幾何周辺の話かな。

      えぇ、「結構あと」にならないと判らない事なので、普通は授業では教えてもらえません。

      それは、卒論で地獄を見ている最中に降ってくる天使のささやきの一つです。
      --
      fjの教祖様
      シェア
      親コメント
typodupeerror

未知のハックに一心不乱に取り組んだ結果、私は自然の法則を変えてしまった -- あるハッカー