トップページ⇒tech
132コメント42KB

ソートアルゴリズムを熱く語ろう♪

■ このスレッドは過去ログ倉庫に格納されています
000155NGNG
開始!
000257NGNG
57 名前： 名無しさん＠お腹いっぱい。 投稿日： 2000/12/30(土) 12:34
珠玉のプログラミングにのってたbitsortにはびびった。

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

つーか、勉強不足なだけか・・・。
0003デフォルトの名無しさんNGNG
で、結局stable quick sortは実装可能かどうか結論を出せ！
0004デフォルトの名無しさんNGNG
>>3
何故順番が安定でないかについてレポートせよ
0005デフォルトの名無しさんNGNG
>>3
答えは可能です。

クイックソートでは、前からと後ろから挟むように
前からは大さい値を見つけた時点で、
後ろから小きい点を見つけた時点で一つ交換します。
たとえば、値５と比較してる時
->3736139<-
　3331 679
前から7のところで、後ろから３のところで交換が生じます
そのまま比較を続けても次の3では交換が起きませんから
そして再帰の次のステップで今度は先頭の３が一番後ろに回ってしまいます

ようは交換する時、同じ値が無いか調べて同じ値があれば
前に移すときは一番後ろのものに　後ろに移す時は一番前のものと
交換するように変更すればOK

ただし、交換する都度検索したのではクイックソートなんて
名前を付けられないでしょうね
0006デフォルトの名無しさんNGNG
あるいは、その場で交換しないで、
つまり交換しなければならない個所にマークだけしておき、
手前から交換してゆく方法でも安定なソートが可能です
->3736139<-に対してマークだけ
---*-*@@--　とつけて
交換は前から順に交換してゆきますつまり
7<->1 6<->3 と交換します。

マークをつけずに、最初に分割点を探すだけにして
次に分割点からそれぞれ後ろに向かって比較交換しても同じですね
0007デフォルトの名無しさんNGNG
>>5
それを「できる」と言っていいのかな〜？
現実的な解じゃない気が。
いちいち比較の時に検索しに行くって、クイックソートを使う意味があまり無い気がするし。
普通に他の安定ソート使った方が圧倒的に速いような・・・。
暇ができたら試してみようかな。

それはそーと(凍結)、ギコソートやモナソートをだれか作ってください。
0008デフォルトの名無しさんNGNG
久々にいいネタで燃えてるのでage
0009デフォルトの名無しさんNGNG
>>6のマーク付けの方法
その方法だと、たとえば、データが
->3736139<-
でなく、
->3736319<- だと、左から2番目の7と、右から3番目の3が交換されるので、安定
ではないような氣がしますが…
ちなみに私なら、整列前の位置をどこかに保存しておいて、普通にクイックソート
した後に、保存しておいた値を使って挿入ソートするのがいいような...
って、クイックソートから離れてしまったのでsage。
安定という命題からも離れてしまったのでsage。
あと、直観ですが、nの2乗に比例する時間か、nに比例する作業領域（マージソート
の場合はn/2?）を使わないと安定なソートはできないような氣がしますが、間違って
いたら申し訳ないのでsage。
0010デフォルトの名無しさんNGNG
総統も相当ソートがお好きですなあ、はははははは。
0011デフォルトの名無しさんNGNG
だれか代表的なソートアルゴリズムを安定、不安定で分けて一覧作りませんか？
以下は私が判る範囲で。

○安定ソート
・バブルソート
・挿入ソート
・選択ソート
・分布数えソート
・マージソート
・ラディックスソート(基数ソート)

○不安定ソート
・クイックソート
・シェルソート

○不明
・コムソート(バブルソートの親戚なので、安定？)
0012デフォルトの名無しさんNGNG
安定 デマイズソート
0013デフォルトの名無しさんNGNG
>>11
コムソートはシェルソートと同じで、離れた値を比較・交換し、だんだん間隔を
狭めていくので、不安定だと思います。
サイトによっては「クイックソートより高速」などと表現されていることがあります
が、私がintの配列で実装したところでは、シェルソートとクイックソートの中間
位の速度でした。（キーの型を変えれば違うかも）
あと、不安定のほうに、ヒープソートを追加キヴォン。
0014デフォルトの名無しさんNGNG
クイックソートが最強！
これでいいのだ。
0015デフォルトの名無しさんNGNG
代表的なソートアルゴリズム一覧
-------------------------------
○安定ソート(順序不定)
・バブルソート
・挿入ソート
・選択ソート
・分布数えソート
・マージソート
・ラディックスソート(基数ソート)
・デマイズソート　　　　　　　　　←12で追加
-------------------------------
○不安定ソート(順序不定)
・クイックソート
・シェルソート
・コムソート
・ヒープソート 　　　　　　　　　←13で追加
-------------------------------
他にもありましたらお願いします。
あとは必要リソース、制限とかもあると良いかな。
0016期待ageNGNG
--------------------------------------------------------------
名前　：　安定度（5：良<->1：悪）　：　必要リソース　：　備考

バブルソート　：　4　：　？　：　？
挿入ソート　：　4　：　？　：　？
選択ソート　：　4　：　？　：　？
分布数えソート　：　4　：　？　：　？
マージソート　：　4　：　？　：　？
ラディックスソート(基数ソート)　：　4　：　？　：　？
デマイズソート　：　4　：　？　：　？
クイックソート　：　2　：　？　：　？
シェルソート　：　2　：　？　：　？
コムソート　：　2　：　？　：　？
ヒープソート　：　2　：　？　：　？

安定度のみでソート
--------------------------------------------------------------
0017デフォルトの名無しさんNGNG
安定度って何だよ？安定度の高低はどういう基準で決まるんだ？

それはさておき、一覧にするなら計算量は必須だろうな。
また、必要リソースではなく、in-placeか否かの方がいいのではないか？
0018デフォルトの名無しさんNGNG
マージソートは安定で、しかも速いみたいだね。
マージソートの欠点は無いの？
0019デフォルトの名無しさんNGNG
データ数と同程度（あるいは半分）の記憶領域を必要とする。
速度もクイックソートより遅い傾向にある。
0020名無しさん＠お腹いっぱい。NGNG
＞マージソート
名前がダサい
0021デフォルトの名無しさんNGNG
>>19
クイックソートより遅いって、そりゃ当たり前じゃ。
0022デフォルトの名無しさんNGNG
分布数えソート(安定)
　　計算時間：O(n)
　　制限：キーが整数で、その範囲が判っている場合のみ適用可能
　　作業領域：分布格納用の整数配列(例：キーが0〜127の範囲なら128個の整数配列)

逆写像ソート(安定)
　　計算時間：O(n)
　　制限：分布数えソートと同じ
　　作業領域：ソートする配列と同じ大きさの作業用配列が２つ
　　備考：分布数えソートより遅い

ところで>>16の安定度って基準は何？
もしかして５段階評価？主観で決めろと？
0023デフォルトの名無しさんNGNG
いかにしてO(n)とかの速いソートに渡せるようにデータ作成するか、って話題も面白いと思うけどなー。
0024デフォルトの名無しさんNGNG
>21
なぜ当たり前なのかな？
クイックソートでO(n^2)になるデータだったら
マージソートの方が速いかもしれないぞ。
0025デフォルトの名無しさんNGNG
>>24
いや、でも妙な制限無しのソートで、平均して一番速いのはクイックソートだろ。
0026デフォルトの名無しさんNGNG
リストをソートするなら、マージがいい。
0027デフォルトの名無しさんNGNG
速度
クイックソート＞マージソート＞ヒープソート＞シェルソート＞＞他＞＞バブルソート
（ただし、条件の違う分布数えソートなどを除く）

これでいい？
0028デフォルトの名無しさんNGNG
入れ替えが発生しないときならバブルソートが一番速い。
キャッシュヒット率最強！
0029デフォルトの名無しさんNGNG
要素数がやたら少ないときとか。
00305,6NGNG
今朝読み返して赤面中です。お恥ずかしい
安定にするには２度目のスキャンでは交換ではなく
挿入してシフトするしかないですね。
0031デフォルトの名無しさんNGNG
>>13
ヒープソートって不安定か？
最悪の場合でも速いソートとして有名だが？
0032デフォルトの名無しさんNGNG
実際にプログラム中で使う時はソートを直接するよりB木とかハッシュとかで
処理する方が多くありませんか？

というか最近ならデータベースか・・・
00332NGNG
ビットソートは・・・？

4,10,3,8,6

0001101010100000

重複無し、データはひとつでそれに付随するデータ無しのとき使う。

http://www.programmingperls.com/bitsort.c
0034デフォルトの名無しさんNGNG
>>31
ヒープソートの速度が不安定なのではなく、同一の値における整列前の順序が保存
されるか否かという観点で>>11の表は分類されていると思うのですが。
速度に関しては全くおっしゃる通りで、最悪の場合でもn log n の時間で実行
できますね。ただし、実装方法にもよりますが、最初から逆順に並んでいるデータを
好む傾向があります。
0035デフォルトの名無しさんNGNG
Cマガ最新刊のPlaugerの記事は「sortの改良」で、
quick sortのLatest and Greatestな実装が解説されてます。
ソートヲタは必読ですな。
0036デフォルトの名無しさんNGNG
複合キーでソートすればクイックソートも安定になると思うけど。
0037ゆたんぽNGNG
1991年のバイト誌で紹介されたコムソートの最
適化版、コムソート１１。

日経バイト誌での追試（数千件くらいだったと
思う）ではクイックソートの速度を上回ってお
り、個人的に試した数万〜数十万件の文字列の
ソートでもクイックソートを圧倒していました。
0038デフォルトの名無しさんNGNG
コームソートと言って欲しい。。。いいけど。
0039デフォルトの名無しさんNGNG
長さ0-255の文字列の配列100,000件をソートしてみました。
comb sort 8.13
quick sort(1) 5.06
quick sort(2) 2.81
qsort 3.06
結果は秒です。
quick sort(1)は、通常のクイックソート、(2)は要素数が10を下回った場合に
挿入ソートに切り替えました。また、qsortは標準ライブラリのqsortです。
環境は、
CPU P100
MEM 40M
OS Vine Linux 2.1
egcs-2.91.66 最適化オプションなしです。
やはりcomb sortはquick sortより遅いような気がしますが...
0040デフォルトの名無しさんNGNG
comb sort 11だ！>39
0041デフォルトの名無しさんNGNG
>>40

>>39 で
comb sortと書いてあるのは実際はcomb sort 11でした。
失礼。

004240NGNG
いや〜ン
0043>40NGNG
女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女ァ!
0044期待ageNGNG
もうすぐ紅白だが、その前にぜひ解説してくれ！>36
00452NGNG
(-＿-) ﾀﾞﾚﾓｶﾏｯﾃｸﾚﾅｲ･･････ｳﾂﾀﾞｼﾉｳ
(∩∩）
0046デフォルトの名無しさんNGNG
>>45
リンク先見れないのだが
00472NGNG
(-＿-)
(∩∩） ｽﾍﾟﾙﾐｽ･･････ｳﾂﾀﾞｼﾉｳ

http://www.programmingpearls.com/bitsort.c
0048デフォルトの名無しさんNGNG
>>45=2
bitsortは制限が強すぎるような気が...

0049デフォルトの名無しさんNGNG
英語わからん。
全訳してくれ！>2
0050新世紀期待ageNGNG
謹賀新年g
0051デフォルトの名無しさんNGNG
>>35の記事を読んで自分なりに実装してみました（ただし、intの配列で)。
あくまでもintの配列の時の話ですが、挿入ソートに切り替える閾値は7-10の
間が良いようでした。ヒープソートに切り替えるタイミングはPlauger氏の
いうようなタイミングでいいと思います。
あと枢軸値の選び方ですが、Plauger氏の方法でも1　..　n/2　..　1のように
並んだ配列を食わせると実行時間が倍程度になるようです。ある程度以上の再帰が
おきたらヒープソートを使うことによってスタックオーバーフローはおきないよう
になっているので、いっそのこと枢軸値はランダムに選んでもいいような気が
いたしました。で、実際にやってみたら、良好な結果を得ました。
（入力によって実行時間が極端に変化することがないということです。）
あと、以上の結果はあくまでもintの配列で自分で実装した結果ですので、
ライブラリ関数として汎用性を重んじたPlauger氏の実装と単純な比較は
できません。
そのうちPlauger氏のソースを直接いじってご報告致す所存。
0052デフォルトの名無しさんNGNG
>>49
ピアソンから出ている「珠玉のプログラミング」という本を読めば詳しく書いて
あります。
私も読んでいるところであります。
参千四百円＋税であります。
0053ゆたんぽNGNG
気になったので確認
長さ0-200,000の文字列の配列100,000件をソートしてみました。

comb sort 721
qsort 270(ライブラリ関数)

160万件だと

comb sort 27499
qsort 6720(ライブラリ関数)

結果はmsです。環境は、

CPU PIII 500
MEM 512M
OS Windows NT 4.0 SP5
VC++ 6.0
ううむ、確かにクイックソートの方が速い。
９年前の計測はまぼろしか？

世紀をまたがってプログラムを組んでしまいました。

0054デフォルトの名無しさんNGNG
>>51
挿入ソートに切り替えるタイミングは9が定説。
0055デフォルトの名無しさんNGNG
>>53
私もクイックソートより早いアルゴリズムがあると聞いて早速実装してみて、
結果に落胆したクチなんですよね。
0056デフォルトの名無しさんNGNG
折角なのでだれか比較演算の回数と入れ替えの回数も計測して下さい。
005755NGNG
s/早い/速い
鬱だ...
0058デフォルトの名無しさんNGNG
自分でヤレ>56
0059デフォルトの名無しさんNGNG
最強のアルゴリズムだとか、最速の方法だとか、つまらん幻想をもつな。
アルゴリズムには長所と短所がある。なにか一つの方法論に頼ろうとするな。
0060デフォルトの名無しさんNGNG
>>59
なんでもクイックソートあたりにしとけば、いいんじゃないの？
0061デフォルトの名無しさんNGNG
>59
私はバブルソートを使うならクイックソートを使うという
一つの方法論に頼っています。
0062デフォルトの名無しさんNGNG
>>59
別にいいじゃん。
このスレッド好きだな。
0063>61NGNG
俺はとりあえず実装簡単で不利なケースのないshell sort書いて、
必要であればquick sortに書き換える。
quick sortはn^2地雷回避コードきっちり書くの結構面倒なので。
0064>63NGNG
ソートなんか何度も自分でかかねーよ。ばーか。
quick sortとheap sortとmerge sortがあれば事足りるだろ。

あとはAVL木、キャッシュ付きAVL木、自己組織化木、オープンハッシュあたりで十分。
というわけでSTL使え。
0065デフォルトの名無しさんNGNG
>>64
ハッシュとソートがどう関係あるのか教えれ。
リンクリストにつなぐときに順番を考慮して、っていうのは無しな。
もし関係ないならそう書け。
0066デフォルトの名無しさんNGNG
”リンクリストにつなぐときに順番を考慮して”
↑意味不明

bucket sortも便利だろ(藁
0067名無しさんNGNG
仕事で使うソートは、大体バブルソート。
Ｑソートは、バブルがあまりに遅いときだけかなー。

シェル、インサート、マージ、なんかは、研修の時ぐらいしか使わんなー。
0068デフォルトの名無しさんNGNG
何で今時バブルソートなんだ？
例えば、C言語はqsort関数が標準でついてるだろ。
sortする関数がついてない言語なんてあるのか？
0069名無しさん＠お腹いっぱい。NGNG
>>66
バケツソートってメジャー？
0070デフォルトの名無しさんNGNG
＞68
そう責めるなよ。ライブラリの使い方をしらないだけなんだから。
0071デフォルトの名無しさんNGNG
やっぱヒープが一番気持ちいーよね。
全てを壊して始めからって感じで。
0072デフォルトの名無しさんNGNG
あわびにインサートして、中でマージって、いい感じ
0073デフォルトの名無しさんNGNG
クイックなのはいただけないな。
0074デフォルトの名無しさんNGNG
なんだか車輪の再発明でおおよろこびしてるやつらがいるな
0075デフォルトの名無しさんNGNG
どこに？>74
ちゃんと番号で教えてくれ。
0076デフォルトの名無しさんNGNG
>>75
飼い主に小便を垂れるイヌ発見
0077７６NGNG
間違えました。スマソ
0078デフォルトの名無しさんNGNG
DelphiのVCLにあるQuickSortって、何の工夫もないQuickSortなんだけど
誰も文句言わなかったのかなあ
0079デフォルトの名無しさんNGNG
つーか、おまえらんなかでちゃんと数学的に
説明できるやついねえのかよ。
大学行ってないやつはしょうがないが。
なぜ、
O(n^2)
と
nlog(n)　　　t < c*nlog(n)
くらいの説明がでてこんのだ。
数学勉強しろ！
リンク任せにすな！
上の二つどっちがドレですか？とか聞くな！
0080デフォルトの名無しさんNGNG
>>79
おしえて♪
0081>>78NGNG
しかも文字列を含む構造体の配列なんかソートするときに参照カウントの関係で、
構造体の要素後とに代入しないといかんかったりするんだよね。

しぶしぶMFCみながら作りなおしたよ．．．
0082デフォルトの名無しさんNGNG
びっぐおー
0083デフォルトの名無しさんNGNG
>>79
O(n^2)はともかく
> nlog(n)　　　t < c*nlog(n)
って何？意味不明。
0084デフォルトの名無しさんNGNG
http://www.inet-lab.org/ted/program/prog005.htmlより
それ以来、ソートにはシェルソート (そのとき Y 氏が使ったのがこのアルゴリズム) を信者の様に使っていますが、自分で作ったソートのアルゴリズムにも生き残る道がありました。私の作ったアルゴリズムは、ソートされた配列の後尾に追加されたデータをソートするときには、どのソートにも負けないので、配列に順次データを追加して結果を表示するなどというプログラムには、今でも使っています。


これって挿入ソートだろうな。
> 自分で作ったソートのアルゴリズム
って無知を晒してるだけでイタイのですが。
0085デフォルトの名無しさんNGNG
そーとしておいてやれ
0086デフォルトの名無しさんNGNG
>>85
ソートスレほど親父ギャグがでるスレもすくないね。
0087デフォルトの名無しさんNGNG
BWTをどうにか早くしたい。

ただのQuickSortだと遅すぎるんですが、
何かいいアイデアは無いですか？
お知恵を拝借したいのです。
0088デフォルトの名無しさんNGNG
>>87
http://www.ingnet.or.jp/~kojif/mu/comp/bwt.htm
BWTってこれ？
0089デフォルトの名無しさんNGNG
>>87
バケツ法はどう？
0090デフォルトの名無しさんNGNG
>>86
　じゃあ、お言葉に甘えて「ボゴソート」Ｏ(n!)
0091デフォルトの名無しさんNGNG
>>88
そうです。それ。
安定じゃなきゃいけないんです。

>>89
配列がかなりでかい(最低でも数メガ)あるので、
ちょっと遅いかな・・・と。
0092デフォルトの名無しさんNGNG
最もメモリ消費量とスピードの天秤が取れてるは
クイックそーち戸？
0093デフォルトの名無しさんNGNG
>>87
基数ソートが応用できないかな？
キーが巨大だから全段実行するとO(n^2)の計算量になってしまうけれど、
ある程度緩やかにソートできたら、他の安定なソートでとどめを刺せば良さそう。
キーがサイクリックに読み替えできるのがポイント
各桁の度数分布が全部同じなのも美味しい
0094デフォルトの名無しさんNGNG
>>12
デマイズソートって何ですか？
Google にも引っかかりません
0095デフォルトの名無しさんNGNG
>>94
>>12が生み出した変形バブルソート。
009693NGNG
>>87
予備的なソートならバケツソートの方が簡単かも？
89 の方が正解か？
基数ソートやバケツソートはキーの比較が楽なのがメリット。

それで、クイックソートもピボットを特定の要素ではなく
特定の桁だけで比較する方が速いかな？
分割の効率は落ちるけれど。

あと、特殊なデータ（例オール０）だと異様に時間が掛かりそうだけれど、
対策は必要だろうか？
009792改NGNG
最もメモリ消費量とスピードのバランスが取れてるのは
クイックソート？
0098デフォルトの名無しさんNGNG
http://www.soi.wide.ad.jp/class/97001/slides/04/021.html
馬鹿ソート
009987NGNG
オール０対策はかなり重要です。

BWTって、比較関数をどれだけ呼ばないで済むか、
がポイントになると思います。文字列比較なんで。

そうなると比較結果のハッシュとかまで
考慮しなきゃいけないのかなぁ。
0100デフォルトの名無しさんNGNG
ビンソートはどうなんですか？
0101デフォルトの名無しさんNGNG
スタック版クイックソートのスタックの大きさって、
配列要素の値のビット数分でいいって、どっかの本に載ってたけど、
どういう根拠でしょう？
0102　NGNG
リボルバーソートがベストでしょう
010393NGNG
>>99
いくつか考えてみたけれど、
キーの比較のコスト（平均 O(log n)、最悪 O(n)）を考えると
>>93で考えた基数ソートをベースにする方法が
安定した速度を確保できそう。
平均で O(n log n)、最悪でO（n^2)の計算量。
キー全体でなく、桁（byte？）単位で比較すれば済むのが美味しい

クイックソートだと平均 O(n(log n)^2)、最悪O(n^3)
ヒープソートでも、最悪 O((n^2) log n)
0104デフォルトの名無しさんNGNG
ビンソートはどうですかー
0105デフォルトの名無しさんNGNG
基数ソートってラディックスソートのこと?
0106デフォルトの名無しさんNGNG
漏れがなにか読み落としてるのかもしれんが、stable な quick ソートは
簡単にインプリメントできるぞ。前に Lisp で書いたことがあるし、c++
でも別段大過なく書けると思う。

qsort(1 1' 5 2 2' 4 5') -> qsort(1 1' 2 2') + qsort(5 4 5')
というように、串刺ししつつ上下に分割してゆけば良いだけ。
配列だと領域が少し多く必要になる。
リストだと新規の領域は一切必要ない。
0107デフォルトの名無しさんNGNG
lispのコードで良いから書いて見てくれ>106
0108デフォルトの名無しさんNGNG
>>106
それから、マージしていくの？
0109デフォルトの名無しさんNGNG
>>106
>リストだと新規の領域は一切必要ない。
これってリストの破壊操作をするってことですか？
0110デフォルトの名無しさんNGNG
>106
早くその安定なクイックソートというのを見せてくれ。
0111デフォルトの名無しさんNGNG
>>101
分割・再帰のたどり方が賢い（小さいブロックを先に片づける）、
プラス、tail recursion が最適化されているならその通り。
タコな実装だとワーストケースで要素数に比例するスタックを消費する。

教科書にはわかりやすさ優先でタコな実装が
載っていることも多いから、要注意。

再帰は使わず、自前でスタックを作って、ループ処理にするのが吉
0112デフォルトの名無しさんNGNG
ビンソートはどうですか？
0113デフォルトの名無しさんNGNG
>>104 >>112
確かに比較しないで済むけど
メモリをどのぐらい確保してやるつもり？
無理だと思うのだけど。

>>103
基数ソートで文字列の整列？
無理だと思うのだけど。
> 平均で O(n log n)、最悪でO（n^2)の計算量。
この計算量がどこから出てきたのかよくわからぬのだが。
基数ソートってO(n)でしょ？
011493NGNG
>>113
まずは >>87-88 を読んでください。

>>93で考えたのは問題の特殊性を活かした変則的な基数ソートです。
具体的な説明はもう少し待ってください。
0115113NGNG
>>114
あ、ソートする対象の文字列の長さが同じなわけ？
0116デフォルトの名無しさんNGNG
>>107-109
確かによく考えたらこれじゃマージソートだねえ。
リストの場合はマージがコストゼロだから速いけど。

LISP の方は11年も前なので非破壊操作はともかく非再起で
ループする構文忘れちゃったよお。C で許して。

typedef struct _cell {
int v;
struct _cell* tail;
} *list;

void qsort_sub(list *p, list tail) {
list l = *p;
if (l) {
list lowwer, upper, *pLowwer = &lower, *pUpper = &upper;
int v = l->v;
while (l) {
if (l->v <= v) {
*pLower = l; *pLower = &l->tail;
} else {
*pUpper = l; *pUpper = &l->tail;
}
l = l->tail;
}
*pLower = *pUpper = NULL;
qsort(&upper, tail); qsort(&lower->tail, upper);
*p = lower;
} else {
*p = tail;
}
}

list qsort(list l) {
qsort_sub(&l, NULL);
return l;
}
0117デフォルトの名無しさんNGNG
>>93
各ノードがノード値に対応するデータのバケツを持つ
バイナリツリーに挿入してゆくってのはどう？
左右に落っこちるときに、「何文字目までは等しかった」というのを
保存しておけば、比較の回数も減らせるし書く比較のコスト削減もできる。
0118117NGNG
>>比較の回数も減らせるし書く比較のコスト削減もできる。
各比較のコストは減るけど、回数は減らせないか。
0119109NGNG
参考までにlisp（というかScheme）でのリストの非破壊ソート
(define (qsort1 cmp l)
  (letrec (
    (q2 (lambda (l1 m l2 l)
      (if (pair? l)
          (if (cmp (car l) m)
              (q2 (cons (car l) l1) m l2 (cdr l))
              (q2 l1 m (cons (car l) l2) (cdr l)))
          (append (q1 l1) (cons m (q1 l2))))
    ))
    (q1 (lambda (l)
      (if (pair? l)
          (q2 '() (car l) '() (cdr l))
          l)
    )))
    (q1 l)  
  ))
;使い方
(qsort1 < '(4 2 1 3 5 ...))
0120デフォルトの名無しさんNGNG
>>119
これはもしかして安定？
0121デフォルトの名無しさんNGNG
ビンソートはどうですかー
0122デフォルトの名無しさんNGNG
ためになるぞage
0123デフォルトの名無しさんNGNG
>>120
ちがうよ
0124デフォルトの名無しさんNGNG
>>87
結局どうなった？
0125デフォルトの名無しさんNGNG
Ｂｙトニックそ〜と
0126109NGNG
>>120
安定しないソートです。
それと、既に整列されたリストについての処理はとても遅くなります。
安定を気にするなら、データも比較する様にしてください。
;(数字 . 数字)の様なdot対のalistの場合
(qsort1
  (lambda (l r)
    (if (= (car l) (car r)) ;同値
        (< (cdr l) (cdr r)) ;データを比較
        (< (car l) (car r))
    ))
  alis
)
0127デフォルトの名無しさんNGNG
ビンソートはどうですか？
0128デフォルトの名無しさんNGNG
バケツソートマンセー
0129デフォルトの名無しさんNGNG
>>124
ごめんなさい。
色々お知恵を頂いておいてアレなんですが
暇が無くて一行も書けてません。

ごめんなさい。sage
0130デフォルトの名無しさんNGNG
ビーンソートー
0131デフォルトの名無しさんNGNG
はるか昔にサイエンス誌に載っていたネタだが、
パスタ素子による並列物理演算ソート、マンセー
0132デフォルトの名無しさんNGNG
>>131

量子コンピュータでよく出てくる話題だよね＞パスタ素子
■ このスレッドは過去ログ倉庫に格納されています