From: Itou-T15@...
Date: 2005-07-27T18:02:58+09:00
Subject: [ruby-list:40940] Re: 値の集合内の中から値の大きな数個のみを取得するには？


伊藤です

入力ストリームがランダムで、上位数個を拾うのでは
単純なバブルソートがいいのでは。

１．ソート済み配列に、数個詰める
２．入力ストリームより１個取り出し、最小値と比較
３．ソート済み配列 更新

データ処理が進むほど、最小値と比較の１回のみで終わります。
昇順ソート済み入力では最悪になります。

アルゴリズムの本では、クイックソート、中央値
関連の 上位Nを見つけるのがありますが。