池田です。

From: Itou-T15 / mail.dnp.co.jp
Date: Wed, 27 Jul 2005 18:02:58 +0900
> 
> 入力ストリームがランダムで、上位数個を拾うのでは
> 単純なバブルソートがいいのでは。

伝統的には、このような用途にはヒープソートが良いと
されていたかと思います。

値を入れたり取り出したりするときにヒープ構造のデータが
整列されるというものなので、今回の条件に向いていそうです。

Ruby でヒープ構造を扱う使いやすいライブラリがあるかどうか
不明ですが、古典的で有名なアルゴリズムなので、参考文献も多く、
実装もさほど難しくないと思います。

キーワードは、heap order、a heap ordered array、heapsort
あたりかと (Knuth 先生の本の索引そのままですが)。

-- 
池田 克巳  <ikedak / rg8.so-net.ne.jp>
           <http://www013.upp.so-net.ne.jp/ikeda/index.html>