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

開始!

57 名前： 名無しさん＠お腹いっぱい。 投稿日： 2000/12/30(土) 12:34
珠玉のプログラミングにのってたbitsortにはびびった。

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

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

で、結局stable quick sortは実装可能かどうか結論を出せ！

>>3
何故順番が安定でないかについてレポートせよ

>>3
答えは可能です。

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

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

ただし、交換する都度検索したのではクイックソートなんて
名前を付けられないでしょうね

あるいは、その場で交換しないで、
つまり交換しなければならない個所にマークだけしておき、
手前から交換してゆく方法でも安定なソートが可能です
->3736139<-に対してマークだけ
---*-*@@--　とつけて
交換は前から順に交換してゆきますつまり
7<->1 6<->3 と交換します。

マークをつけずに、最初に分割点を探すだけにして
次に分割点からそれぞれ後ろに向かって比較交換しても同じですね

>>5
それを「できる」と言っていいのかな〜？
現実的な解じゃない気が。
いちいち比較の時に検索しに行くって、クイックソートを使う意味があまり無い気がするし。
普通に他の安定ソート使った方が圧倒的に速いような・・・。
暇ができたら試してみようかな。

それはそーと(凍結)、ギコソートやモナソートをだれか作ってください。

久々にいいネタで燃えてるのでage

>>6のマーク付けの方法
その方法だと、たとえば、データが
->3736139<-
でなく、
->3736319<- だと、左から2番目の7と、右から3番目の3が交換されるので、安定
ではないような氣がしますが…
ちなみに私なら、整列前の位置をどこかに保存しておいて、普通にクイックソート
した後に、保存しておいた値を使って挿入ソートするのがいいような...
って、クイックソートから離れてしまったのでsage。
安定という命題からも離れてしまったのでsage。
あと、直観ですが、nの2乗に比例する時間か、nに比例する作業領域（マージソート
の場合はn/2?）を使わないと安定なソートはできないような氣がしますが、間違って
いたら申し訳ないのでsage。

総統も相当ソートがお好きですなあ、はははははは。

だれか代表的なソートアルゴリズムを安定、不安定で分けて一覧作りませんか？
以下は私が判る範囲で。

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

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

○不明
・コムソート(バブルソートの親戚なので、安定？)

安定 デマイズソート

>>11
コムソートはシェルソートと同じで、離れた値を比較・交換し、だんだん間隔を
狭めていくので、不安定だと思います。
サイトによっては「クイックソートより高速」などと表現されていることがあります
が、私がintの配列で実装したところでは、シェルソートとクイックソートの中間
位の速度でした。（キーの型を変えれば違うかも）
あと、不安定のほうに、ヒープソートを追加キヴォン。

クイックソートが最強！
これでいいのだ。

代表的なソートアルゴリズム一覧
-------------------------------
○安定ソート(順序不定)
・バブルソート
・挿入ソート
・選択ソート
・分布数えソート
・マージソート
・ラディックスソート(基数ソート)
・デマイズソート　　　　　　　　　←12で追加
-------------------------------
○不安定ソート(順序不定)
・クイックソート
・シェルソート
・コムソート
・ヒープソート 　　　　　　　　　←13で追加
-------------------------------
他にもありましたらお願いします。
あとは必要リソース、制限とかもあると良いかな。

--------------------------------------------------------------
名前　：　安定度（5：良<->1：悪）　：　必要リソース　：　備考

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

安定度のみでソート
--------------------------------------------------------------

安定度って何だよ？安定度の高低はどういう基準で決まるんだ？

それはさておき、一覧にするなら計算量は必須だろうな。
また、必要リソースではなく、in-placeか否かの方がいいのではないか？

マージソートは安定で、しかも速いみたいだね。
マージソートの欠点は無いの？

データ数と同程度（あるいは半分）の記憶領域を必要とする。
速度もクイックソートより遅い傾向にある。

＞マージソート
名前がダサい

>>19
クイックソートより遅いって、そりゃ当たり前じゃ。

分布数えソート(安定)
　　計算時間：O(n)
　　制限：キーが整数で、その範囲が判っている場合のみ適用可能
　　作業領域：分布格納用の整数配列(例：キーが0〜127の範囲なら128個の整数配列)

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

ところで>>16の安定度って基準は何？
もしかして５段階評価？主観で決めろと？

いかにしてO(n)とかの速いソートに渡せるようにデータ作成するか、って話題も面白いと思うけどなー。

>21
なぜ当たり前なのかな？
クイックソートでO(n^2)になるデータだったら
マージソートの方が速いかもしれないぞ。

>>24
いや、でも妙な制限無しのソートで、平均して一番速いのはクイックソートだろ。

リストをソートするなら、マージがいい。

速度
クイックソート＞マージソート＞ヒープソート＞シェルソート＞＞他＞＞バブルソート
（ただし、条件の違う分布数えソートなどを除く）

これでいい？

入れ替えが発生しないときならバブルソートが一番速い。
キャッシュヒット率最強！

要素数がやたら少ないときとか。

今朝読み返して赤面中です。お恥ずかしい
安定にするには２度目のスキャンでは交換ではなく
挿入してシフトするしかないですね。

>>13
ヒープソートって不安定か？
最悪の場合でも速いソートとして有名だが？

実際にプログラム中で使う時はソートを直接するよりB木とかハッシュとかで
処理する方が多くありませんか？

というか最近ならデータベースか・・・

ビットソートは・・・？

4,10,3,8,6

0001101010100000

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

http://www.programmingperls.com/bitsort.c

>>31
ヒープソートの速度が不安定なのではなく、同一の値における整列前の順序が保存
されるか否かという観点で>>11の表は分類されていると思うのですが。
速度に関しては全くおっしゃる通りで、最悪の場合でもn log n の時間で実行
できますね。ただし、実装方法にもよりますが、最初から逆順に並んでいるデータを
好む傾向があります。

Cマガ最新刊のPlaugerの記事は「sortの改良」で、
quick sortのLatest and Greatestな実装が解説されてます。
ソートヲタは必読ですな。

複合キーでソートすればクイックソートも安定になると思うけど。

1991年のバイト誌で紹介されたコムソートの最
適化版、コムソート１１。

日経バイト誌での追試（数千件くらいだったと
思う）ではクイックソートの速度を上回ってお
り、個人的に試した数万〜数十万件の文字列の
ソートでもクイックソートを圧倒していました。

コームソートと言って欲しい。。。いいけど。

長さ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より遅いような気がしますが...

comb sort 11だ！>39

>>40

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

いや〜ン

女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女ァ!

もうすぐ紅白だが、その前にぜひ解説してくれ！>36

(-＿-) ﾀﾞﾚﾓｶﾏｯﾃｸﾚﾅｲ･･････ｳﾂﾀﾞｼﾉｳ
(∩∩）

>>45
リンク先見れないのだが

(-＿-)
(∩∩） ｽﾍﾟﾙﾐｽ･･････ｳﾂﾀﾞｼﾉｳ

http://www.programmingpearls.com/bitsort.c

>>45=2
bitsortは制限が強すぎるような気が...

英語わからん。
全訳してくれ！>2

謹賀新年g

>>35の記事を読んで自分なりに実装してみました（ただし、intの配列で)。
あくまでもintの配列の時の話ですが、挿入ソートに切り替える閾値は7-10の
間が良いようでした。ヒープソートに切り替えるタイミングはPlauger氏の
いうようなタイミングでいいと思います。
あと枢軸値の選び方ですが、Plauger氏の方法でも1　..　n/2　..　1のように
並んだ配列を食わせると実行時間が倍程度になるようです。ある程度以上の再帰が
おきたらヒープソートを使うことによってスタックオーバーフローはおきないよう
になっているので、いっそのこと枢軸値はランダムに選んでもいいような気が
いたしました。で、実際にやってみたら、良好な結果を得ました。
（入力によって実行時間が極端に変化することがないということです。）
あと、以上の結果はあくまでもintの配列で自分で実装した結果ですので、
ライブラリ関数として汎用性を重んじたPlauger氏の実装と単純な比較は
できません。
そのうちPlauger氏のソースを直接いじってご報告致す所存。

>>49
ピアソンから出ている「珠玉のプログラミング」という本を読めば詳しく書いて
あります。
私も読んでいるところであります。
参千四百円＋税であります。

気になったので確認
長さ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
ううむ、確かにクイックソートの方が速い。
９年前の計測はまぼろしか？

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

>>51
挿入ソートに切り替えるタイミングは9が定説。

>>53
私もクイックソートより早いアルゴリズムがあると聞いて早速実装してみて、
結果に落胆したクチなんですよね。

折角なのでだれか比較演算の回数と入れ替えの回数も計測して下さい。

s/早い/速い
鬱だ...

自分でヤレ>56

最強のアルゴリズムだとか、最速の方法だとか、つまらん幻想をもつな。
アルゴリズムには長所と短所がある。なにか一つの方法論に頼ろうとするな。

>>59
なんでもクイックソートあたりにしとけば、いいんじゃないの？

>59
私はバブルソートを使うならクイックソートを使うという
一つの方法論に頼っています。

>>59
別にいいじゃん。
このスレッド好きだな。

俺はとりあえず実装簡単で不利なケースのないshell sort書いて、
必要であればquick sortに書き換える。
quick sortはn^2地雷回避コードきっちり書くの結構面倒なので。

ソートなんか何度も自分でかかねーよ。ばーか。
quick sortとheap sortとmerge sortがあれば事足りるだろ。

あとはAVL木、キャッシュ付きAVL木、自己組織化木、オープンハッシュあたりで十分。
というわけでSTL使え。

>>64
ハッシュとソートがどう関係あるのか教えれ。
リンクリストにつなぐときに順番を考慮して、っていうのは無しな。
もし関係ないならそう書け。

”リンクリストにつなぐときに順番を考慮して”
↑意味不明

bucket sortも便利だろ(藁

仕事で使うソートは、大体バブルソート。
Ｑソートは、バブルがあまりに遅いときだけかなー。

シェル、インサート、マージ、なんかは、研修の時ぐらいしか使わんなー。

何で今時バブルソートなんだ？
例えば、C言語はqsort関数が標準でついてるだろ。
sortする関数がついてない言語なんてあるのか？

>>66
バケツソートってメジャー？

＞68
そう責めるなよ。ライブラリの使い方をしらないだけなんだから。

やっぱヒープが一番気持ちいーよね。
全てを壊して始めからって感じで。

あわびにインサートして、中でマージって、いい感じ

クイックなのはいただけないな。

なんだか車輪の再発明でおおよろこびしてるやつらがいるな

どこに？>74
ちゃんと番号で教えてくれ。

>>75
飼い主に小便を垂れるイヌ発見

間違えました。スマソ

DelphiのVCLにあるQuickSortって、何の工夫もないQuickSortなんだけど
誰も文句言わなかったのかなあ

つーか、おまえらんなかでちゃんと数学的に
説明できるやついねえのかよ。
大学行ってないやつはしょうがないが。
なぜ、
O(n^2)
と
nlog(n)　　　t < c*nlog(n)
くらいの説明がでてこんのだ。
数学勉強しろ！
リンク任せにすな！
上の二つどっちがドレですか？とか聞くな！

>>79
おしえて♪

しかも文字列を含む構造体の配列なんかソートするときに参照カウントの関係で、
構造体の要素後とに代入しないといかんかったりするんだよね。

しぶしぶMFCみながら作りなおしたよ．．．

びっぐおー

>>79
O(n^2)はともかく
> nlog(n)　　　t < c*nlog(n)
って何？意味不明。

http://www.inet-lab.org/ted/program/prog005.htmlより
それ以来、ソートにはシェルソート (そのとき Y 氏が使ったのがこのアルゴリズム) を信者の様に使っていますが、自分で作ったソートのアルゴリズムにも生き残る道がありました。私の作ったアルゴリズムは、ソートされた配列の後尾に追加されたデータをソートするときには、どのソートにも負けないので、配列に順次データを追加して結果を表示するなどというプログラムには、今でも使っています。


これって挿入ソートだろうな。
> 自分で作ったソートのアルゴリズム
って無知を晒してるだけでイタイのですが。

そーとしておいてやれ

>>85
ソートスレほど親父ギャグがでるスレもすくないね。

BWTをどうにか早くしたい。

ただのQuickSortだと遅すぎるんですが、
何かいいアイデアは無いですか？
お知恵を拝借したいのです。

>>87
http://www.ingnet.or.jp/~kojif/mu/comp/bwt.htm
BWTってこれ？

>>87
バケツ法はどう？

>>86
　じゃあ、お言葉に甘えて「ボゴソート」Ｏ(n!)

>>88
そうです。それ。
安定じゃなきゃいけないんです。

>>89
配列がかなりでかい(最低でも数メガ)あるので、
ちょっと遅いかな・・・と。

最もメモリ消費量とスピードの天秤が取れてるは
クイックそーち戸？

>>87
基数ソートが応用できないかな？
キーが巨大だから全段実行するとO(n^2)の計算量になってしまうけれど、
ある程度緩やかにソートできたら、他の安定なソートでとどめを刺せば良さそう。
キーがサイクリックに読み替えできるのがポイント
各桁の度数分布が全部同じなのも美味しい

>>12
デマイズソートって何ですか？
Google にも引っかかりません

>>94
>>12が生み出した変形バブルソート。

>>87
予備的なソートならバケツソートの方が簡単かも？
89 の方が正解か？
基数ソートやバケツソートはキーの比較が楽なのがメリット。

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

あと、特殊なデータ（例オール０）だと異様に時間が掛かりそうだけれど、
対策は必要だろうか？

最もメモリ消費量とスピードのバランスが取れてるのは
クイックソート？

http://www.soi.wide.ad.jp/class/97001/slides/04/021.html
馬鹿ソート

オール０対策はかなり重要です。

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

そうなると比較結果のハッシュとかまで
考慮しなきゃいけないのかなぁ。

ビンソートはどうなんですか？

スタック版クイックソートのスタックの大きさって、
配列要素の値のビット数分でいいって、どっかの本に載ってたけど、
どういう根拠でしょう？

リボルバーソートがベストでしょう

>>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)

ビンソートはどうですかー

基数ソートってラディックスソートのこと?

漏れがなにか読み落としてるのかもしれんが、stable な quick ソートは
簡単にインプリメントできるぞ。前に Lisp で書いたことがあるし、c++
でも別段大過なく書けると思う。

qsort(1 1' 5 2 2' 4 5') -> qsort(1 1' 2 2') + qsort(5 4 5')
というように、串刺ししつつ上下に分割してゆけば良いだけ。
配列だと領域が少し多く必要になる。
リストだと新規の領域は一切必要ない。

lispのコードで良いから書いて見てくれ>106

>>106
それから、マージしていくの？

>>106
>リストだと新規の領域は一切必要ない。
これってリストの破壊操作をするってことですか？

>106
早くその安定なクイックソートというのを見せてくれ。

>>101
分割・再帰のたどり方が賢い（小さいブロックを先に片づける）、
プラス、tail recursion が最適化されているならその通り。
タコな実装だとワーストケースで要素数に比例するスタックを消費する。

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

再帰は使わず、自前でスタックを作って、ループ処理にするのが吉

ビンソートはどうですか？

>>104 >>112
確かに比較しないで済むけど
メモリをどのぐらい確保してやるつもり？
無理だと思うのだけど。

>>103
基数ソートで文字列の整列？
無理だと思うのだけど。
> 平均で O(n log n)、最悪でO（n^2)の計算量。
この計算量がどこから出てきたのかよくわからぬのだが。
基数ソートってO(n)でしょ？

>>113
まずは >>87-88 を読んでください。

>>93で考えたのは問題の特殊性を活かした変則的な基数ソートです。
具体的な説明はもう少し待ってください。

>>114
あ、ソートする対象の文字列の長さが同じなわけ？

>>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;
}

>>93
各ノードがノード値に対応するデータのバケツを持つ
バイナリツリーに挿入してゆくってのはどう？
左右に落っこちるときに、「何文字目までは等しかった」というのを
保存しておけば、比較の回数も減らせるし書く比較のコスト削減もできる。

>>比較の回数も減らせるし書く比較のコスト削減もできる。
各比較のコストは減るけど、回数は減らせないか。

参考までに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 ...))

>>119
これはもしかして安定？

ビンソートはどうですかー

ためになるぞage

>>120
ちがうよ

>>87
結局どうなった？

Ｂｙトニックそ〜と

>>120
安定しないソートです。
それと、既に整列されたリストについての処理はとても遅くなります。
安定を気にするなら、データも比較する様にしてください。
;(数字 . 数字)の様なdot対のalistの場合
(qsort1
  (lambda (l r)
    (if (= (car l) (car r)) ;同値
        (< (cdr l) (cdr r)) ;データを比較
        (< (car l) (car r))
    ))
  alis
)

ビンソートはどうですか？

バケツソートマンセー

>>124
ごめんなさい。
色々お知恵を頂いておいてアレなんですが
暇が無くて一行も書けてません。

ごめんなさい。sage

ビーンソートー

はるか昔にサイエンス誌に載っていたネタだが、
パスタ素子による並列物理演算ソート、マンセー

>>131

量子コンピュータでよく出てくる話題だよね＞パスタ素子