wikipediaに掲載されているinsertion sortのコードは駄目すぎらしい

やねうらおさんが久しぶりに更新されていた
insertion sortについて。これは「既にソートされている」リストに「効率よく追加するソート」らしい

http://e-words.jp/w/E68CBFE585A5E382BDE383BCE38388.html

与えられた要素がソート済み状態に近ければ比較的高速だが、要素が逆順に並んでいるととてつもない時間を要する。
この欠点をある程度緩和した改良版にシェルソートである。

大学でqsortやらshellsortやbublesortは実習した覚えがありますが、
insertion sortは実習した記憶がないです。
ある意味、アルゴリズムの演習向けというよりは、リアルな実世界向けのソートかもしれません

http://d.hatena.ne.jp/yaneurao/20091126#p1

> 例ってのはエッセンスを伝えるものだから

insertion sortに限って言えばそれは間違いです。これは、要素数が少ないときのために特化されたソートであって、
もともとの狙いが高速化にあります。insertion sortで書いて高速化しないなら何の利用価値もないのです。

確かに。解りやすさ優先ならqsortなんかあり得ないでしょうし(^^;

コンピュータ将棋では、手のオーダリングでソートをみなさんやってると思いますが、
insertion sortを使われている人は意外に少ないのではないかと思います。
使ってますか？

misakiは使ってないんですよね。全部手を生成してからまとめてソートしているので、
GenCap、GenNoCap、GenDropみたいにカテゴリー別に生成する場合は、
ソート済みのリストに追加していくソートでしょうから、効率がよくなるのだろうと思います

ちなみにBonanzaのInsertion sortのコード

	/* insertion sort */
	psortv[nqmove] = INT_MIN;
	for ( i = nqmove-2; i >= 0; i-- )
	  {
	    value = psortv[i];  move = pmove[i];
	    for ( j = i+1; psortv[j] > value; j++ )
	      {
		psortv[j-1] = psortv[j];  pmove[j-1] = pmove[j];
	      }
	    psortv[j-1] = value;  pmove[j-1] = move;
	  }

	ptree->move_last[ply]             = ptree->move_last[ply-1] + nqmove;
	ptree->anext_move[ply].move_last  = pmove;
	ptree->anext_move[ply].next_phase = next_quies_captures;
      }