5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

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

1 :55:2000/12/30(土) 13:09
開始!

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

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

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

3 :デフォルトの名無しさん:2000/12/30(土) 14:16
で、結局stable quick sortは実装可能かどうか結論を出せ!

4 :デフォルトの名無しさん:2000/12/30(土) 19:55
>>3
何故順番が安定でないかについてレポートせよ

5 :デフォルトの名無しさん:2000/12/30(土) 20:46
>>3
答えは可能です。

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

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

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

6 :デフォルトの名無しさん:2000/12/30(土) 20:59
あるいは、その場で交換しないで、
つまり交換しなければならない個所にマークだけしておき、
手前から交換してゆく方法でも安定なソートが可能です
->3736139<-に対してマークだけ
---*-*@@-- とつけて
交換は前から順に交換してゆきますつまり
7<->1 6<->3 と交換します。

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

7 :デフォルトの名無しさん:2000/12/30(土) 21:06
>>5
それを「できる」と言っていいのかな〜?
現実的な解じゃない気が。
いちいち比較の時に検索しに行くって、クイックソートを使う意味があまり無い気がするし。
普通に他の安定ソート使った方が圧倒的に速いような・・・。
暇ができたら試してみようかな。

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

8 :デフォルトの名無しさん:2000/12/30(土) 23:07
久々にいいネタで燃えてるのでage

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

10 :デフォルトの名無しさん:2000/12/30(土) 23:49
総統も相当ソートがお好きですなあ、はははははは。

11 :デフォルトの名無しさん:2000/12/31(日) 00:17
だれか代表的なソートアルゴリズムを安定、不安定で分けて一覧作りませんか?
以下は私が判る範囲で。

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

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

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

12 :デフォルトの名無しさん:2000/12/31(日) 00:39
安定 デマイズソート

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


14 :デフォルトの名無しさん:2000/12/31(日) 00:46
クイックソートが最強!
これでいいのだ。

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

16 :期待age:2000/12/31(日) 03:01
--------------------------------------------------------------
名前 : 安定度(5:良<->1:悪) : 必要リソース : 備考

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

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


17 :デフォルトの名無しさん:2000/12/31(日) 04:09
安定度って何だよ?安定度の高低はどういう基準で決まるんだ?

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

18 :デフォルトの名無しさん:2000/12/31(日) 04:11
マージソートは安定で、しかも速いみたいだね。
マージソートの欠点は無いの?

19 :デフォルトの名無しさん:2000/12/31(日) 04:38
データ数と同程度(あるいは半分)の記憶領域を必要とする。
速度もクイックソートより遅い傾向にある。


20 :名無しさん@お腹いっぱい。:2000/12/31(日) 05:12
>マージソート
名前がダサい

21 :デフォルトの名無しさん:2000/12/31(日) 05:15
>>19
クイックソートより遅いって、そりゃ当たり前じゃ。

22 :デフォルトの名無しさん:2000/12/31(日) 05:17
分布数えソート(安定)
  計算時間:O(n)
  制限:キーが整数で、その範囲が判っている場合のみ適用可能
  作業領域:分布格納用の整数配列(例:キーが0〜127の範囲なら128個の整数配列)

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

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

23 :デフォルトの名無しさん:2000/12/31(日) 05:37
いかにしてO(n)とかの速いソートに渡せるようにデータ作成するか、って話題も面白いと思うけどなー。

24 :デフォルトの名無しさん:2000/12/31(日) 05:56
>21
なぜ当たり前なのかな?
クイックソートでO(n^2)になるデータだったら
マージソートの方が速いかもしれないぞ。

25 :デフォルトの名無しさん:2000/12/31(日) 06:54
>>24
いや、でも妙な制限無しのソートで、平均して一番速いのはクイックソートだろ。

26 :デフォルトの名無しさん:2000/12/31(日) 07:15
リストをソートするなら、マージがいい。

27 :デフォルトの名無しさん:2000/12/31(日) 07:35
速度
クイックソート>マージソート>ヒープソート>シェルソート>>他>>バブルソート
(ただし、条件の違う分布数えソートなどを除く)

これでいい?

28 :デフォルトの名無しさん:2000/12/31(日) 07:38
入れ替えが発生しないときならバブルソートが一番速い。
キャッシュヒット率最強!

29 :デフォルトの名無しさん:2000/12/31(日) 07:55
要素数がやたら少ないときとか。

30 :5,6:2000/12/31(日) 09:57
今朝読み返して赤面中です。お恥ずかしい
安定にするには2度目のスキャンでは交換ではなく
挿入してシフトするしかないですね。

31 :デフォルトの名無しさん:2000/12/31(日) 09:57
>>13
ヒープソートって不安定か?
最悪の場合でも速いソートとして有名だが?

32 :デフォルトの名無しさん:2000/12/31(日) 10:21
実際にプログラム中で使う時はソートを直接するよりB木とかハッシュとかで
処理する方が多くありませんか?

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

33 :2:2000/12/31(日) 10:50
ビットソートは・・・?

4,10,3,8,6

0001101010100000

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

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

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


35 :デフォルトの名無しさん:2000/12/31(日) 12:42
Cマガ最新刊のPlaugerの記事は「sortの改良」で、
quick sortのLatest and Greatestな実装が解説されてます。
ソートヲタは必読ですな。

36 :デフォルトの名無しさん:2000/12/31(日) 13:46
複合キーでソートすればクイックソートも安定になると思うけど。


37 :ゆたんぽ:2000/12/31(日) 14:10
1991年のバイト誌で紹介されたコムソートの最
適化版、コムソート11。

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


38 :デフォルトの名無しさん:2000/12/31(日) 14:49
コームソートと言って欲しい。。。いいけど。

39 :デフォルトの名無しさん:2000/12/31(日) 16:32
長さ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より遅いような気がしますが...

40 :デフォルトの名無しさん:2000/12/31(日) 17:46
comb sort 11だ!>39

41 :デフォルトの名無しさん:2000/12/31(日) 17:57
>>40

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



42 :40:2000/12/31(日) 18:02
いや〜ン

43 :>40:2000/12/31(日) 18:58
女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女女ァ!

44 :期待age:2000/12/31(日) 19:06
もうすぐ紅白だが、その前にぜひ解説してくれ!>36

45 :2:2000/12/31(日) 21:42
(-_-) ダレモカマッテクレナイ・・・・・・ウツダシノウ
(∩∩)

46 :デフォルトの名無しさん:2000/12/31(日) 21:52
>>45
リンク先見れないのだが


47 :2:2000/12/31(日) 22:05
(-_-)
(∩∩) スペルミス・・・・・・ウツダシノウ

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

48 :デフォルトの名無しさん:2000/12/31(日) 22:07
>>45=2
bitsortは制限が強すぎるような気が...



49 :デフォルトの名無しさん:2000/12/31(日) 22:25
英語わからん。
全訳してくれ!>2

50 :新世紀期待age:2001/01/01(月) 00:24
謹賀新年g

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

52 :デフォルトの名無しさん:2001/01/01(月) 00:34
>>49
ピアソンから出ている「珠玉のプログラミング」という本を読めば詳しく書いて
あります。
私も読んでいるところであります。
参千四百円+税であります。


53 :ゆたんぽ:2001/01/01(月) 00:41
気になったので確認
長さ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
ううむ、確かにクイックソートの方が速い。
9年前の計測はまぼろしか?

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



54 :デフォルトの名無しさん:2001/01/01(月) 00:43
>>51
挿入ソートに切り替えるタイミングは9が定説。

55 :デフォルトの名無しさん:2001/01/01(月) 00:44
>>53
私もクイックソートより早いアルゴリズムがあると聞いて早速実装してみて、
結果に落胆したクチなんですよね。


56 :デフォルトの名無しさん:2001/01/01(月) 00:46
折角なのでだれか比較演算の回数と入れ替えの回数も計測して下さい。


57 :55:2001/01/01(月) 00:46
s/早い/速い
鬱だ...


58 :デフォルトの名無しさん:2001/01/01(月) 01:22
自分でヤレ>56

59 :デフォルトの名無しさん:2001/01/01(月) 10:39
最強のアルゴリズムだとか、最速の方法だとか、つまらん幻想をもつな。
アルゴリズムには長所と短所がある。なにか一つの方法論に頼ろうとするな。

60 :デフォルトの名無しさん:2001/01/01(月) 12:26
>>59
なんでもクイックソートあたりにしとけば、いいんじゃないの?

61 :デフォルトの名無しさん:2001/01/01(月) 13:07
>59
私はバブルソートを使うならクイックソートを使うという
一つの方法論に頼っています。

62 :デフォルトの名無しさん:2001/01/01(月) 14:36
>>59
別にいいじゃん。
このスレッド好きだな。

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


64 :>63:2001/01/01(月) 21:04
ソートなんか何度も自分でかかねーよ。ばーか。
quick sortとheap sortとmerge sortがあれば事足りるだろ。

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

65 :デフォルトの名無しさん:2001/01/01(月) 21:19
>>64
ハッシュとソートがどう関係あるのか教えれ。
リンクリストにつなぐときに順番を考慮して、っていうのは無しな。
もし関係ないならそう書け。


66 :デフォルトの名無しさん:2001/01/01(月) 21:23
”リンクリストにつなぐときに順番を考慮して”
↑意味不明

bucket sortも便利だろ(藁

67 :名無しさん:2001/01/02(火) 00:34
仕事で使うソートは、大体バブルソート。
Qソートは、バブルがあまりに遅いときだけかなー。

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


68 :デフォルトの名無しさん:2001/01/02(火) 00:39
何で今時バブルソートなんだ?
例えば、C言語はqsort関数が標準でついてるだろ。
sortする関数がついてない言語なんてあるのか?

69 :名無しさん@お腹いっぱい。:2001/01/02(火) 00:58
>>66
バケツソートってメジャー?

70 :デフォルトの名無しさん:2001/01/02(火) 01:55
>68
そう責めるなよ。ライブラリの使い方をしらないだけなんだから。

71 :デフォルトの名無しさん:2001/01/02(火) 02:22
やっぱヒープが一番気持ちいーよね。
全てを壊して始めからって感じで。


72 :デフォルトの名無しさん:2001/01/02(火) 02:57
あわびにインサートして、中でマージって、いい感じ

73 :デフォルトの名無しさん:2001/01/02(火) 02:57
クイックなのはいただけないな。

74 :デフォルトの名無しさん:2001/01/02(火) 03:53
なんだか車輪の再発明でおおよろこびしてるやつらがいるな

75 :デフォルトの名無しさん:2001/01/02(火) 05:15
どこに?>74
ちゃんと番号で教えてくれ。

76 :デフォルトの名無しさん:2001/01/02(火) 05:59
>>75
飼い主に小便を垂れるイヌ発見

77 :76:2001/01/02(火) 06:00
間違えました。スマソ

78 :デフォルトの名無しさん:2001/01/06(土) 21:52
DelphiのVCLにあるQuickSortって、何の工夫もないQuickSortなんだけど
誰も文句言わなかったのかなあ

79 :デフォルトの名無しさん:2001/02/07(水) 12:38
つーか、おまえらんなかでちゃんと数学的に
説明できるやついねえのかよ。
大学行ってないやつはしょうがないが。
なぜ、
O(n^2)

nlog(n)   t < c*nlog(n)
くらいの説明がでてこんのだ。
数学勉強しろ!
リンク任せにすな!
上の二つどっちがドレですか?とか聞くな!

80 :デフォルトの名無しさん:2001/02/07(水) 12:44
>>79
おしえて♪

81 :>>78:2001/02/08(木) 16:20
しかも文字列を含む構造体の配列なんかソートするときに参照カウントの関係で、
構造体の要素後とに代入しないといかんかったりするんだよね。

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

82 :デフォルトの名無しさん:2001/02/11(日) 04:50
びっぐおー

83 :デフォルトの名無しさん:2001/05/27(日) 16:28
>>79
O(n^2)はともかく
> nlog(n)   t < c*nlog(n)
って何?意味不明。

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


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

85 :デフォルトの名無しさん:2001/05/27(日) 19:28
そーとしておいてやれ

86 :デフォルトの名無しさん:2001/05/27(日) 19:58
>>85
ソートスレほど親父ギャグがでるスレもすくないね。

87 :デフォルトの名無しさん:2001/05/28(月) 21:53
BWTをどうにか早くしたい。

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

88 :デフォルトの名無しさん:2001/05/28(月) 22:32
>>87
http://www.ingnet.or.jp/~kojif/mu/comp/bwt.htm
BWTってこれ?

89 :デフォルトの名無しさん:2001/05/28(月) 23:00
>>87
バケツ法はどう?

90 :デフォルトの名無しさん:2001/05/28(月) 23:16
>>86
 じゃあ、お言葉に甘えて「ボゴソート」O(n!)

91 :デフォルトの名無しさん:2001/05/28(月) 23:56
>>88
そうです。それ。
安定じゃなきゃいけないんです。

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

92 :デフォルトの名無しさん:2001/05/29(火) 00:03
最もメモリ消費量とスピードの天秤が取れてるは
クイックそーち戸?

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

94 :デフォルトの名無しさん:2001/05/29(火) 10:00
>>12
デマイズソートって何ですか?
Google にも引っかかりません

95 :デフォルトの名無しさん:2001/05/29(火) 11:39
>>94
>>12が生み出した変形バブルソート。

96 :93:2001/05/29(火) 18:54
>>87
予備的なソートならバケツソートの方が簡単かも?
89 の方が正解か?
基数ソートやバケツソートはキーの比較が楽なのがメリット。

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

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

97 :92改:2001/05/29(火) 20:18
最もメモリ消費量とスピードのバランスが取れてるのは
クイックソート?

98 :デフォルトの名無しさん:2001/05/29(火) 20:26
http://www.soi.wide.ad.jp/class/97001/slides/04/021.html
馬鹿ソート

99 :87:2001/05/29(火) 22:01
オール0対策はかなり重要です。

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

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

100 :デフォルトの名無しさん:2001/05/29(火) 22:20
ビンソートはどうなんですか?

101 :デフォルトの名無しさん:2001/05/29(火) 22:40
スタック版クイックソートのスタックの大きさって、
配列要素の値のビット数分でいいって、どっかの本に載ってたけど、
どういう根拠でしょう?

102 : :2001/05/29(火) 22:50
リボルバーソートがベストでしょう

103 :93:2001/05/30(水) 00:30
>>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)

104 :デフォルトの名無しさん:2001/05/30(水) 00:41
ビンソートはどうですかー

105 :デフォルトの名無しさん:2001/05/30(水) 01:09
基数ソートってラディックスソートのこと?

106 :デフォルトの名無しさん:2001/05/30(水) 02:03
漏れがなにか読み落としてるのかもしれんが、stable な quick ソートは
簡単にインプリメントできるぞ。前に Lisp で書いたことがあるし、c++
でも別段大過なく書けると思う。

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

107 :デフォルトの名無しさん:2001/05/30(水) 02:26
lispのコードで良いから書いて見てくれ>106

108 :デフォルトの名無しさん:2001/05/30(水) 02:47
>>106
それから、マージしていくの?

109 :デフォルトの名無しさん:2001/05/30(水) 03:40
>>106
>リストだと新規の領域は一切必要ない。
これってリストの破壊操作をするってことですか?

110 :デフォルトの名無しさん:2001/05/30(水) 05:22
>106
早くその安定なクイックソートというのを見せてくれ。

111 :デフォルトの名無しさん:2001/05/30(水) 08:45
>>101
分割・再帰のたどり方が賢い(小さいブロックを先に片づける)、
プラス、tail recursion が最適化されているならその通り。
タコな実装だとワーストケースで要素数に比例するスタックを消費する。

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

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

112 :デフォルトの名無しさん:2001/05/30(水) 12:00
ビンソートはどうですか?

113 :デフォルトの名無しさん:2001/05/30(水) 13:06
>>104 >>112
確かに比較しないで済むけど
メモリをどのぐらい確保してやるつもり?
無理だと思うのだけど。

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

114 :93:2001/05/30(水) 14:40
>>113
まずは >>87-88 を読んでください。

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

115 :113:2001/05/30(水) 14:49
>>114
あ、ソートする対象の文字列の長さが同じなわけ?

116 :デフォルトの名無しさん:2001/05/30(水) 15:12
>>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;
}

117 :デフォルトの名無しさん:2001/05/30(水) 15:46
>>93
各ノードがノード値に対応するデータのバケツを持つ
バイナリツリーに挿入してゆくってのはどう?
左右に落っこちるときに、「何文字目までは等しかった」というのを
保存しておけば、比較の回数も減らせるし書く比較のコスト削減もできる。

118 :117:2001/05/30(水) 15:53
>>比較の回数も減らせるし書く比較のコスト削減もできる。
各比較のコストは減るけど、回数は減らせないか。

119 :109:2001/05/30(水) 21:15
参考までに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 ...))

120 :デフォルトの名無しさん:2001/05/30(水) 22:50
>>119
これはもしかして安定?

121 :デフォルトの名無しさん:2001/05/30(水) 23:31
ビンソートはどうですかー

122 :デフォルトの名無しさん:2001/05/31(木) 01:15
ためになるぞage

123 :デフォルトの名無しさん:2001/05/31(木) 01:17
>>120
ちがうよ

124 :デフォルトの名無しさん:2001/05/31(木) 17:57
>>87
結局どうなった?

125 :デフォルトの名無しさん:2001/05/31(木) 20:27
Byトニックそ〜と

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

127 :デフォルトの名無しさん:2001/05/31(木) 23:24
ビンソートはどうですか?

128 :デフォルトの名無しさん:2001/05/31(木) 23:28
バケツソートマンセー

129 :デフォルトの名無しさん:2001/05/31(木) 23:51
>>124
ごめんなさい。
色々お知恵を頂いておいてアレなんですが
暇が無くて一行も書けてません。

ごめんなさい。sage

130 :デフォルトの名無しさん:2001/06/01(金) 01:10
ビーンソートー

131 :デフォルトの名無しさん:2001/06/01(金) 15:01
はるか昔にサイエンス誌に載っていたネタだが、
パスタ素子による並列物理演算ソート、マンセー

132 :デフォルトの名無しさん:2001/06/01(金) 18:21
>>131

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

33 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.02 2018/11/22 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)