「初めて学ぶソートアルゴリズムは何がいい？」記事へのコメント

マージソート

[okky (2487)]

なにも教わらない場合、人は「選択ソート」を使うことが多い。なので、まず自分がどのようにモノを整列させるのか、トランプなどで自覚させて、それは「選択ソートと言うんだよ」と教えた上で、本格的に教える最初のソートアルゴリズムは何? という質問だと考える事にすると、私はマージソートが良いとおもいます。

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

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

--
fjの教祖様

Re:マージソート

[khwarizmi (23623)]

何も教わらない人がカード（1-13と範囲が決まってることが自明）をソートしてと言われると机が使える限り絶対にbin sortをすると思うんだが．

Re:マージソート

[okky (2487)]

bin sort (バケットソート)であるためには、

1) まずいきなり4x13の領域を机上に確保
2) カードの最初から順番に1枚づつカードを4x13の置くべき場所に配置

という作業手順でなくてはいけません。はて、『2のステップを必ずこのようにやるでしょうか?』

私の知っているケースは、カードの中を引っ掻き回して「まずAを探し」、次に「2を探し」…とやっては卓上に置いていく人ばかりだったのですが…(もちろん、残りが10枚ぐらいになれば話は別ですが)。

ちなみに。器用でわかっている人は「机がなくても」手の中だけでバケットソートをしてしまいますね。

--
fjの教祖様

Re:

[Anonymous Coward]

> ちなみに。器用でわかっている人は「机がなくても」手の中だけでバケットソートをしてしまいますね。

挿入ソートじゃねーの
物理的な場合はバケツソートとほとんど区別つかないけどね