ソートのアルゴリズム

2つの値を比較した時に同じだった場合、元の順序を壊さない
ソートのアルゴリズムでバブルソートよりも高速なソートって
ありましたっけ？どなたか教えてください。
宜しくお願いします。

バブルソートよりっておい!

クイックソートの比較関数に元の順序も比較対象にすれば？

はい終わり。

冬休みのレポートか。

ええかげんにせい・・・

我々は1が何故このようなスレッドを立てたのかという疑問を解決するため、
1の故郷に向かった。まだ日本にこんなところがあったのか…
思わず口に出てしまった言葉を同行した友人に失礼だと咎められた。
小人が住むような小さな家、ツギハギだらけの服を着る農夫たち、そして
彼らは余所者で身なりのいい我々を監視する様に見詰めている。
高度成長だの、神武景気だの、ワールドカップだので浮かれていた我々は改めて
農村の現状を噛み締めていた。ボロ屑のような家に居たのは老いた母親一人
我々を見るなり全てを悟ったのか、涙ながらに息子が申し訳ありませんと
我々に何度も土下座して詫びた。我々はこの時初めて1を許そうと思った。
誰が悪い訳ではない、農村の貧しさが全て悪かったのだ。我々は1の母親から
買った干し柿を手に、打ちひしがれながら帰路についた

マージソートならO(nlogn)だ。
２～５は、ソートの安定・非安定について勉強すること。

>>ソートの安定・非安定

ようするに
>>2つの値を比較した時に同じだった場合、元の順序を壊さない
だろ?

んなこったあ、わかってんだよ。
クイックソートは非安定だ。
けど、ソート以前の順序を、比較関数に適応することことで
結果的に安定になるの。

＞２
「元の順序も比較対象にする」と
「2つの値を比較した時に同じ」ではなくなってしまいます
かってに条件を変更しないでください。

>>8=2
qsortとかのライブラリで、交換をどう制御するんだ？
馬鹿？

>9,10
だめだこいつら...

どうダメなのか説明してみ
ダメだけ言って逃げるなよ

>11=8=2なら、詳しく説明しろ。

>>12-13
ホント馬鹿だな（藁

お、逃げたな。
結局答えられないだけだろ(ﾜﾗ
「馬鹿」しか書けんならさっさと逃げて消えろや

２じゃないけど。

二つの値が同じだった時だけ
順序を比較するんでしょ？ >>12=13

説明しろとかいう前に自分の頭で考えたら？
あ、考えてもわからなかったんだー（藁

>>14=11=8=2
ふぁあーあ、消防相手にしてたのか。もう寝るわ。
んじゃ、2の反省文は宿題にしておく。今日の朝までに提出する事。いいな？>2

>>16
どうせ想像だけで検証なんかしてないんだろ。
そんな単純な考え方じゃだめなんだって！
もっと良く考えてみ？

>17 あーあ、もう引っ込みつかないね。かわいそ。
一晩寝て、頭スッキリさせてから、出直しておいで。

ただの中傷合戦になってきたので
＝＝＝＝＝＝＝＝終了＝＝＝＝＝＝＝＝

おいおい勝手に終らすなよ。>20=2
全然中傷じゃないって。２も理解してない様だし。

>>21
多分、理解していないのはあなただけです。

＝＝＝＝＝＝＝＝終了＝＝＝＝＝＝＝＝

オイオイ、１が知りたいのはバブルソートより高速なソートだろ？
だったら、マージソートでもクイックソートでも良いじゃねーか。

＞2
まだわかってないのか？
アホ相手は疲れるね。

同じ値の比較だけならば、交換は行われないので、入れ替わる事はない。が、
比較で異なった時に行われる要素の交換で、同じ値が入れ替わらない保障が無いのが「安定しないソート」。
そもそも同じ値かどうかはソートが完了するまで判明しないので２の考えには無理がある。
反省文は朝までに各自提出する事！

>24,25
だめだこいつら...

全員馬鹿。
クイックソートした後にソート前の順番（インデックスを参照して）でバブルソートするのが一番効率的だ。
同じ文字の確立なんて低いだろ？
マージなんか使うな低脳！
お前等全員リストラだ！！

２６及びその部類達は答えが欲しいがために挑発をつづける厨房です
反応してはいけません

>比較で異なった時に行われる要素の交換で、同じ値が入れ替わらない保障..
ニッポンゴ ムツカシーネ

>同じ文字の確立なんて低いだろ？
勝手に決めるな

＞29
マジ馬鹿発見！
煽ったつもりだろうが自分の低脳振りをアピールしただけだぞ。
真性厨房だろ（藁

>25
君もういいよ。お布団へお入り。

>26
理由書けよ。

フィーバーしてます。

フィーバーと言うよりエゴのぶつかり合い。
VB vs Delphiと余りかわらん。

stable sortの意味が分かっていない人間と
stable sortでなくても順序付けにindexを含めれば同等に処理できるという人間と
バカなやり取りをしていることが分かってて煽ってる人間と、
なにが間違ってるのか分からないもののとりあえず煽ってる人間が、
入り乱れております。

期待age

あげてないずぁん

いい感じ

１のソートの対象になるデータ次第だろ？
結局ソートなんてデータ次第なんだよ。
データ（ソートに必要な回数）によって最適なアルゴリズムは変わるだろ？
もう終わりにしようぜ！
お前等全員ミレニアムの年末に彼女がいなくて一人で淋しくインターネットしてる３流私立大学のメガネでぶのコンピュータオタクなんだろ。
こんなお互いを中傷し合う事で淋しさを紛らわすなんて子ども地味たこと辞めようぜ。
さっさと回線切ってＡＶでも借りてきて一発抜いて寝ろよ！
明日はきっと今日よりも最悪な日。
その次の日も、またその次の日も・・・
そうやって１人でどんどん不幸になっていって最後にはバットを振り回して怪我人出して逮捕されてムショでケツ掘られてアンアンの毎日だ。
お前等の人生最高だな。
超かっこいいよ！

日本のIT産業の未来は明るい。

＞４０
良く言った
あんたはエライ

いくつか用意してランダムで決める（藁

なーんだ。もう終わりか。もっとバカ同士ののしりあえば面白いのに。
ねよねよ。

１のデータが数十件だったらお前ら報われねーな＞ALL

だから冬休みの宿題だってば。

と、落ち着いたところで私には
25 のいってることがよくわからないんですけど、
誰か説明してくれません？

あれ、名前に勝手にわけのわからんのがはいっちゃった。

> 2つの値を比較した時に同じだった場合、元の順序を壊さない
そもそも、こういうソートってたとえばどういうときに必要なの?

ソート済みのリスト複数を結合とか？
とりあえず１は頭の良い奴ではないので細かなツッコミはよそう。
いじめ（悪い）

>>50
>ソート済みのリスト複数を結合とか？
その前提として、要素全体が評価対象じゃなくて、
要素の一部が評価対象である、と言ってる?
たとえば Yamada Taro,Japan,24,Male てな
個人データ群を年齢をキーとしてソートとか?

それにしても
25の言ってる「同じ値」ってどういう意味なのかが
わかりません。

ちょっと話題がずれるが
basicでswap命令が消えたのはいつだったか
あの時、私はその理由がわからずおおいに戸惑ったものだ。
あれはまさしく退化ではないか…<笑>

比較結果が同じ場合に、元の並び順で大小を決めればいいかと思いつきで書きましたが
よくよく考えたら、無理ですね。
鬱だ、２１世紀を目前に回線切って首つります。
板橋あたりで自殺のニュースがあったらそれは私です。

ちなみに２，８以外は自分ではありません。
みなさんよい新世紀を。

つまらんな。
もっとソートについて熱く語ってくれよ。age

じゃあスレ作り直したら？　１の内容じゃネタスレにしかならんsage

珠玉のプログラミングにのってたbitsortにはびびった。

http://www.programmingpearls.com/
http://www.programmingpearls.com/code.html

つーか、勉強不足なだけか・・・。

ああ、あの本は買わなきゃ、ってかんじだよねえ。
でもすでにいっぱいキューにたまってるからなあ...
#amazon.co.jpが送料無料のうちに英語版買うかな..

誰かここにくいっくそ－とのそ－す書いて下さい

index付shell sortにしとけ

そーと(文字列){
　　文字列を並べる
　　天才チンパンジーに見せて並べ替えをさせる
　　値を返す
}

そーと(文字列){
　　文字列を水槽に落とす //浮力の小さい順に沈んでいく
　　出来た層を返す
}

そーと(文字列){
　　文字列にマラソンをさせる //いつのまにか足の速い順になっている
　　順位順に校舎に戻ってよし
　　}

総統も相当ソートが（以下略）

去年ぐらいに出たアルゴリズムの入門書で、ソートの解説が「シェルソートまで」
つーすごい本なかったっけ？「クイックソート」のクの字もなかったやつ。

2のいうとおりにやればOKだよ
qsort関数使えや

理解できないなら勉強せいや

>>63
途中で近道してた奴が3人もいました。

値が同じ時は元の順番を優先させてのクイックソートを使えや

>>68
クイックソートって「あるデータだと」
かなり遅いアルゴリズムって知ってる？

情報１種の過去問であったよな
当然知ってるよ

クイックソート(文字列 s){
文字　a =　真中頃にある文字を見つける(s);
　do{
　　int n1=先頭からaより大きな文字を探させる
　　int n2=後ろからaより小さなな文字を探させる
　　s->交換(n1,n2);
　}while(先頭からの検索点<=後ろからの検索点)
n=文字aの位置
クイックソート(文字列の先頭からnまで);
クイックソート(文字列のn番目から最後まで);

}

>>68
あ。
安定な整列を行なう関数をわざわざ自作していたよ…。
鬱出汁膿

で、pegionhole sortがquick、mergeより速いってホント？

>>73

そりゃビンソートとか基数ソートと同じで O( n ) だから、
使える状況なら速いだろうけど。

>>72
だから、>>72にあるようにクイックソートだと前からと後ろから
検索して交換という手順があるから、　元の順番を優先させるには
元の順番のフィールドをデータ構造に含んでいなければいけない。

ニホンゴムツカシイネ

qsort関数の条件判定の関数に値が等しければ
元の順番を使って比較するように
いじれば終わり

それか
ビンソートなりマージソートでもいいよ

バカか？
選択した境界値が複数存在した場合どうするんだよ。

>>77
配列の時はいいけどリンクリストのときはどうするよ
データの要素に元の位置の情報がなきゃお手上げでしょ。
配列の場合は「インデックス」っていう暗黙の情報を
比較条件に使うことができるってだけじゃん

同じ値があれば
各々のポインタをつたってって位置情報を割り出し
元の順序を比較条件に追加だよ

＞データの要素に元の位置の情報がなきゃお手上げでしょ。
ソートするってことは並んでる順番をかえることだよ
元の並んでる順番の情報がないわけないじゃん

>>80各々のポインタをつたってって位置情報を割り出し
　　　　　　　~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>>81
>＞データの要素に元の位置の情報がなきゃお手上げでしょ。
>ソートするってことは並んでる順番をかえることだよ
>元の並んでる順番の情報がないわけないじゃん

ごめん、「お手上げ」っていうのは撤回する。
ただリストの場合その「順番の情報」を取得するのにえらくコストが
かかるって言いたかったのよ。
そんなコストかけるくらいならqsortなんか使わずに他のO(NlogN)の
安定なアルゴリズム使った方がマシって思ったのさ。
確かにやりようによってはリストでも安定なqsortできるかもしれないけど
変な小細工して遅くなるようなら意味ないし

>>27
なぜマージはいけないの？

確かにそうだな
安定で最速なソートとなると
考えてソート法を選ぶしかないな

あんたなかなかやるな
プログラム系のホームページを持ってたら教えて下さいな

qsortも遅くならないように普通は改良されてるから、
何も考えずにqsortでいいんじゃないか？
それはまずいの？

ただのqsortじゃ安定しないの

>>86
だから、不安定にならないように色々工夫されてるんじゃないの？
組み込みの関数なんかは特に。

>>87
わざわざ安定なソートになるように変形してあるqsortの実装は
見たことないぞ、俺。組み込みがどうとかは知らんけど。

>>87
stable sortの意味が分かって書いてるのか？
最悪なケースをなるべく生み出さないようなpivotの選出法とか、
数が少ないときはbubble sortに切り替えるだとかいったテクニックは
色々使われていると想定できるが、それはソートが「安定」かどうか
とは全く次元の違う話だぜ。

みんないやらしいね。ところでホントに何でマージソートはいけないの？>>27

記憶領域を大量に使う（150%）ことを覗けばqsortより優秀だと思ってるんだが。
あと、
pegionhole sortとビンソートってのもわからん。
ダメだな、俺。
[分布数え|radix|マージ|挿入]ソートしか使わないもん。

クイックソートした後にソート前の順番（インデックスを参照して）でバブルソートするのが一番効率的だ。
同じ文字の確立なんて低いだろ？

一番効率的とゆっときながらバブルソートを使うのが理解不能

>>84
だいぶ前に勢いあまってソース公開スレに自推したことあるけど
恥ずかしいからヒミツ

>>85
Cの標準ライブラリのqsort仕様だと元の順序は保証されてないな
でも扱うのは配列だから比較のときに位置情報は使えるな

>>92
ソート前の順番を保持してqsortかけるなら、それもソートキーに
含めてqsortすれば安定するやんけ。
なんでわざわざ最後にバブルソートかけるんだ？
恥ずかしい奴。

>>95
全部読め。
アレは引用だ

>>89
だから、そういう工夫された方法を使ったqsortを使ってれば、
実用上問題じゃないんじゃないの？
しかも、C言語とかにはじめからついてる関数はそうだから
何も問題ないんじゃないの？ってこと。
自分で変なqsortを書かない限りね。
間違ってる？

>77
>qsort関数の条件判定の関数に値が等しければ
>元の順番を使って比較するように
>いじれば終わり
元の順番を使うって、キーの配列まるまるコピーしておいとくの？？
再帰の底で全部が同じキーの値になった場合に、その部分だけのソート
用のキーとして、元の並びの添え字を保持しておき、それを使うって意味
だよね。キーがほとんど重なってないときはメモリがもったいないよ・・

だれかマージソートがダメな理由を教えてくれ～
O(nlogn)でデータの選り好みをしないし、qsortなんかより
よっぽどいいと思うんだが？

記憶領域なんて256もつんでおけばたいてい問題ないだろ？

qsortってCの単なるライブラリ関数であってquick sortの事を
一般的にqsortって言ってるわけではないはずなのに、
みんなqsortと省略するのはなんかねぇ・・

>99
>記憶領域なんて256
学生なんですが、定数なんてソースに埋めるもんなんですか？？

>>101
意味不明
>>99
運悪いとページングがおきる可能性がある。そんなに気にすることもないかも知れんが

すまん。256はPCの搭載メモリが256Mってことだ。

>運悪いとページングがおきる可能性がある。
なるほど。そんなコアなところまで気が回らなかった。

>>97
だから、「Ｃ言語とかにはじめからついてるqsort」は安定じゃねぇってばさ。

>>99
普通のデータだと n log n の係数がでかいせいでクイックソートより遅い。
27みたいな余計なことやってると別のような気もしないでもないが。

＞８５
「遅くなる・ならない」と「安定・不安定」は全く別の話ですよ。

ちなみに関係ないけど VC++ の qsort は
　・最初と真ん中と最後の値の中央値をピボットにする。
　・サイズ８以下なら挿入ソート
でした。

＞再帰の底で全部が同じキーの値になった場合に、その部分だけのソート
＞用のキーとして、元の並びの添え字を保持しておき、それを使うって意味
＞だよね。

qsortの比較関数
で２つの値が等しいときはその時の位置情報を使う
元の並びはいらないよ

工夫されたquick sortでソートした後にバブルソートがベスト。
工夫されたとはpivot選択時にskew checkを行なっていたり、
要素数がある程度以下になった時にはバブルなどに切り替えるソート。

compound keyを用いたquick sortでも良いがkey comparisonの負荷
が増加する点から考えて次点とす。
一つ目の順序が分からない云々言っている奴がいるが、
一つ目のソートができているという事はそのためのkeyは参照という意味である。

>>106
その方法が無効な実装も考えられる。
結局、実装依存になってしまうような気がする。

>>107
>工夫されたquick sortでソートした後にバブルソートがベスト。
アホか？
少なくともバブルソートより基本挿入法のほうが速い
バブルソートがベストである根拠を言ってくれ

> 同じ文字の確立なんて低いだろ？
馬鹿か？
いつ誰が比較する値を「文字」と決めた？
いつ誰が同じデータが出現する確率が低いと言った？

勝手にデータを妄想するな、厨房！

ＧＣＡソート？ってどーよ？
あと、厨房にもわかるように、詳しく解説すれ。

>>77 とかホントにクイックソートのコード書けるのか？
少なくとも単純なクイックソートアルゴリズムからは元の順
番をキーに入れるしかない。

理由は、単純なクイックソートは、[前から検索]と[後ろから検索]
しながら「交換」するからだ。

これを解決するには、一旦マークした後、交換ではなく[挿入]し
なければならない。
それは　速度的には既にクイックとは言えない

>理由は、単純なクイックソートは、[前から検索]と[後ろから検索]
>しながら「交換」するからだ。
値が同じ時に交換するしないを
位置情報で条件分岐させるんだよ

>>112
交換する２つの値の間にどちらかと同じ値があって
飛び越してしまう可能性もあるよね。
ソレを避けるためにはその間の値をサーチするしかない。
（ソレをやるとすでにクイックソートとは言えないって
111は言いたかったんだよね？）
比較する２つの値が同値かどうかチェックするだけでは
上記の飛び越しの可能性を避けることはできないよ
（つーことで比較関数が「そのときの」位置情報が使えても無駄
っていうことに後から気が付いた自分。初期配置の情報がないと
どうやってもクイックソートは安定になりそうもない）

Microsoft の qsort() の実装には、こういう問題もあったみたいね。
今はどうなんだ？

http://support.microsoft.com/support/kb/articles/Q48/9/65.ASP?LN=EN-US&SD=gn&FR=0&qry=Q48965&rnk=1&src=DHCS_MSPSS_gn_SRCH&SPR=CHS

＞値が同じ時に交換するしないを
＞位置情報で条件分岐させるんだよ
では無理です

最初の順番を記憶させるか

第１比較キーが等しければ
第２比較キーで比較するように
大小比較の部分をいじるか

マージソートやビンソートを使うかだね

＞値が同じ時に交換するしないを
＞位置情報で条件分岐させるんだよ
では無理です

最初の順番を記憶させるか

第１比較キーが等しければ
第２比較キーで比較するように
大小比較の部分をいじるか

マージソートやビンソートを使うかだね

おまえら全員
バブルソート
選択ソート
挿入ソート
再帰を勉強して・・・＜＜ここが重要だ。厨房
シェルソート
クイックソートを勉強し直せ。
現在もっともソートが最高速なのはイントロソートだ。

＞114
VC2以降は無事。

クイックソートの安定がどうたら言ってる奴

今あがってる
http://piza.2ch.net/test/read.cgi?bbs=tech&key=978149371

の、 5,6,9,30 を読め

このスレで議論されてるような、
速くないクイックソートを使うメリットを教えてください。

>>120　イヤミか？
安定なクイックソートはキーに最初の順を入れておくしかない
そうでない改善をしたらそれはクイックソートではないって事だ

で、１の結論はマージソートでいいんだな？
つうかイントロソートの概要でもいから誰か教えてくれよ
intoro sortで検索するとごみが多すぎてワケワカラン

>>122

　Introspective　Sorting なら D. R. Musser に聞け
http://www.cs.rpi.edu/~musser/gp/code/intsort.h.txt


そして
よかったら解説してくれ

>>123のリンク先のついて
ソースは読んでない。説明では基本はクイックソート、ピボットを決める
際に選んだ数によってヒープソートに切り替えるといっている。
メモリ消費：少ない
速度：N2地雷を回避しつつ通常はクイックソート並
安定か：不安定
といった感じか？

うんがー
肝心の__unguarded_partition関数の中身はどこだー
<algo.h>ってなんジャー
STL頭いてー

>>109
>少なくともバブルソートより基本挿入法のほうが速い
>バブルソートがベストである根拠を言ってくれ

第一キーでソートしておけば泡の動く範囲が小さく限定されると期待できるから。

おっと、泡は第二キーで動くって事ね。

>>117
>もっともソートが最高速
ナイス日本語。

クイックソートにしとけ。
クイックソートが不安定で困ったなんて話は聞いたことが無い。

不安定よりも、N2地雷コワイよ。

>>124
違う。ピボットとは関係なしに単純に再起の深さで決めている。ソースの感じだと
再起呼び出しの際に深さを表す数をつけて行っている。再起の深さがlog2(size)
になったところでヒープソートに切り替えてるようだ。当然再起にかかわるスタック
消費が増えるのでややメモリ的にはクイックソートより劣るだろう。

通読して地雷を避けるのはダメかな。N+N/2+N/4+...=2N
入れ替え計算量 nlogn 通読 2N 。ま、通読じゃ遅いか。

あ 2N じゃない。N*深さ=nlogn だなぁ。。

N2地雷なんて実際に踏むことあるのかな。
なんか、俺もう既に整列し終わった配列をqsort関数で
ソートしてみたことあるけど、遅くならなかった気がする
のだが。これって、Cのqsort関数は純粋なクイックソート
じゃないってことだろ？
N2地雷の問題なんて多くの実装において解決済み
なんじゃない？

N2地雷ってなに？

>>135
ようわからんが、計算量のオーダーがNになってしまう時の
ことじゃない？

俺は130が使ってたから、知ったかかまして、推測で使っただけ
なんだけどね。
検索しても出て来ないから、そんな言葉無いのかも。
O(n)のつもりで書いたんだけど。

ていうか、エヴァンゲリオンか？

＞134
O(n^2)じゃないの？
元ネタはエヴァだね、確かもう一方のソートスレで誰かが使い始めてたような・・・
という事で外では使わない方がいいかも

>>134
値を２つに分けるときの参照値の選び方を工夫すればソート済みの
データで遅くなる問題は避けられる。
べつにそうしたからってクイックソートでないって事にはならない。
>>105みたいに最初と最後と真中の位置のキーの中央値をとればだいたいOK
(厳密に言えばこれでも非効率になる初期配列もありえるはずだけど)

Webで検索したらエヴァンゲリオンのサイトばかり引っかかって、
どっちが元ネタなのか見分けがつかなかった。
爆発するってことからも、オーダーN^2のことかな。

ソートとは直接関係ないけど、キーが全て異なる配列と自然数nを入力として、
大きいほうからn番目のものをO(n)で探すアルゴリズムがあって、
それを聞いた時すげえ!と感心した記憶がある。

煽りきぼーそ。

話はデータが配列かリストか、ということで全然違う。

リストなら、キーで振り分けてできたリスト2つを下請けに出せば
安定なクイックソート完成。
って、もしかしてこれはクイックソートとは言わないのか？

配列の場合だと、クイックソートのように安定でなくなるか、
(マージ|ヒープ)ソートのようにin-placeでなく（メモリ消費量が
大きく）なるか。

http://ei5nazha.yz.yamagata-u.ac.jp/ADT/sorting.html

てゆーか、配列上でのマージソートって工夫したらin-placeに
なりませんか？

>>99
某STLのstd::list::sortはマージソートだったよ。
リストだと記憶領域は増えないらしい。
マージ中の領域を使いまわせる。
イテレーターの妙技を見たよ。

>>129は安定なソートの意味が分かっていないと思われ

比較数を少なくすることが最優先の場合は、
どんなソートがお勧め？

車輪の再発明。つーか先走りすぎだが。

マージを再帰でやればメモリ消費せずにしかも安定なソートにできるぢゃん。
O(n(logn)^2)になってしまうが。

並列計算機のバイトニックソートの情報キボーン。
古いbit誌捨ててしまったのが悔やまれる。

再帰でやるってことはメモリ消費してるってことだろがｺﾞﾙｧ?>147
末尾再帰なら話は別だが。

それから、bitとかの雑誌のバックナンバーは図書館でいつでも閲覧可能だけど。>147

>>144
stable_sortとstd::sortは？

>>148
知っとるわﾎｹﾞｪ! (ｵｲ
クイックソートと同じようにスタックサイズはO(logn)でOK。ってこと。

末尾再帰……わからない宇津死

>>149
すっかり忘れてました。見てきます。

>>146
元データは何？

>元データは何？
たとえばMP3や獲ろ画像ファイル。
比較を人間がやるとベスト版ができるかなーと思ったので。
で、なるべく比較回数を減らして、なおかつ早い段階で
大雑把な順位付けができるようなアルゴリズムを考えてる。
変形シェルソートが有力か？

>>152
なるほど。ってそれは個人でやる話？投票のような話？
個人でやる話なら……

ベスト盤作成支援ツール。条件は
１．ユーザーに「むだな比較をやらされている」と感じさせないこと。
２．ユーザーに「信頼性がある」と感じさせること。
うーん、

ユーザーに比較させるとa<b,b<cだけどc<aってなりそう

比較・ソートは付加的な機能で、基本はMP3プレイヤーがいいような。
今再生してるのとその前のとでどっちがいいかを
簡単なキー入力で指定する。
だから速度・計算量・使用メモリはぜんぜん問題にならない。

人間の信頼性はあてにならないので、
# >154どころかa>bが時間経ってa<bになることもありうる
なるべく評価値の近いもの同士の比較は避ける。
なるべくランダム再生になるようにする。
評価値の高いものは若干多めに再生する。
ゴミは極力再生しない。アボーンキーでもつけるか？

ってなんかソートとはあんまり関係なくなっちゃな...