O（n)のソートアルゴリズムを発見した

1 ：デフォルトの名無しさん：2008/05/31(土) 15:57:02

やばい！論文書きます

2 ：デフォルトの名無しさん：2008/05/31(土) 15:57:45

>>3-
そーっとしておいてあげてください

3 ：デフォルトの名無しさん：2008/05/31(土) 16:01:07

O(1)のソートアルゴリズムがある件

4 ：デフォルトの名無しさん：2008/05/31(土) 16:05:02

バケツソートとか普通にあるだろ。

5 ：１：2008/05/31(土) 16:08:25

対象データに仮定が必要ないんだぜ

6 ：デフォルトの名無しさん：2008/05/31(土) 16:20:56

特許とれ。

7 ：デフォルトの名無しさん：2008/05/31(土) 16:20:59

こういう単純な処理は標準ライブラリに限る。
ただ、自前で実装しないといけない場合がよくある。
そういう用途のソートアルゴリズムがほしいわけです。(簡単で高速で特に欠点ないやつ)

8 ：デフォルトの名無しさん：2008/05/31(土) 17:01:59

夏だなあ・・・

9 ：デフォルトの名無しさん：2008/05/31(土) 17:40:02

もうネタ出尽してるのに人気あるよなソート

10 ：デフォルトの名無しさん：2008/05/31(土) 17:46:22

たまに思い出したように湧いてくるよね。
とっとと駆除しないと。

11 ：デフォルトの名無しさん：2008/05/31(土) 18:10:14

いや待て、古典アルゴリズムなら無理だが、
量子アルゴリズムなら可能かもしれないだろ？
>>1 は古典アルゴリズムと明言していない。
ならまだ可能性はあるんじゃないのか？

12 ：デフォルトの名無しさん：2008/05/31(土) 19:49:34

量子アルゴリズムが効果的に使えてその辺で買えるコンピュータがあればくれ。

13 ：デフォルトの名無しさん：2008/05/31(土) 20:27:10

>>12
http://music8.2ch.net/test/read.cgi/classical/1211529290/

14 ：デフォルトの名無しさん：2008/05/31(土) 22:14:49

listコンテナにもつかえるsortアルゴリズムというと
バブルソートだけですか？

15 ：デフォルトの名無しさん：2008/05/31(土) 22:29:42

古典コンピュータ以外でのO(n)のアルゴリズムが発見されたとしても、lg(n)時間減るだけじゃなあ。
元々多項式時間なだけに価値があるかどうか。

16 ：デフォルトの名無しさん：2008/05/31(土) 22:36:36

>>14
マージソートとか

17 ：デフォルトの名無しさん：2008/05/31(土) 22:43:27

O(n)のソートを開発したぜ。ただしある特定の配列のみ適用可能。

def sort(arr)
    for i in 0..arr.length-2
        if arr[i] > arr[i+1]
            raise "not sorted!"
        end
    end
    return arr
end

sort [1,2,3]

18 ：デフォルトの名無しさん：2008/05/31(土) 22:44:32

それなら、

def sort(arr)
  [1,2,3]
end

でよくね？

19 ：デフォルトの名無しさん：2008/05/31(土) 23:28:58

ソート対象のデータに全順序以外の仮定がない場合，
ソートの計算時間の下限がO(NlogN)なのはすでに証明済みだったような？

20 ：デフォルトの名無しさん：2008/05/31(土) 23:29:07

双方向リストってクイックソート使えても良さそうだと思うんだけど、
何で使えないのん？

21 ：デフォルトの名無しさん：2008/05/31(土) 23:32:48

作ってないから。

22 ：デフォルトの名無しさん：2008/06/01(日) 10:39:49

>>1しょぼいな
俺なんかナップサック問題を多項式時間で解くアルゴリズムを発見したぞ。

でもそれを記述するにはこの余白はあまりにも少なすぎ

23 ：デフォルトの名無しさん：2008/06/01(日) 12:36:02

0-1でなきゃ貪欲法で元々多項式時間じゃないか。

24 ：デフォルトの名無しさん：2008/06/01(日) 13:14:15

>>23 最適解じゃないし。そんなの解いたとは言わん

25 ：デフォルトの名無しさん：2008/06/01(日) 13:15:54

>>22
書き始めていいよ
埋まりそうになったら次スレ用意する

26 ：デフォルトの名無しさん：2008/06/01(日) 13:30:45

>>24
0-1でなきゃ、の意味も掴めないのか？一般化ナップサックの話だよ

27 ：デフォルトの名無しさん：2008/06/01(日) 13:41:20

suckと申したか

28 ：デフォルトの名無しさん：2008/06/01(日) 17:30:36

卑猥だな

29 ：デフォルトの名無しさん：2008/06/02(月) 03:24:44

おまいら、コンビニの前でチンチンの(自己申告の)でかさを競い合ってるDQNとかわらんぞ。

30 ：デフォルトの名無しさん：2008/06/02(月) 15:55:20

>>26
おいおい、0-1でないと意味ないだろ。
お前、月に行くとして酸素ボンベ半分とか、拳銃0.8個とかナップザックに詰めて
持っていくのかよ。月　を　な　め　る　な

31 ：デフォルトの名無しさん：2008/06/03(火) 23:20:58

月に拳銃は要るのかどうかは知らんがﾜﾛﾀ

32 ：デフォルトの名無しさん：2008/06/06(金) 01:40:47

>>22
フェルマー乙

33 ：デフォルトの名無しさん：2008/06/30(月) 15:13:53

オレもありとあらゆるデータを1bitにするアルゴリズムを持ってるよ。

34 ：デフォルトの名無しさん：2008/07/07(月) 01:06:52

非可逆のハッシュなら俺も持ってる。

35 ：デフォルトの名無しさん：2008/08/18(月) 00:53:00

>>20
ttp://www.geocities.jp/m_hiroi/light/pyalgo08.html

36 ：デフォルトの名無しさん：2008/12/15(月) 07:17:28

>>35
xyzzyの人ですか

37 ：デフォルトの名無しさん：2008/12/15(月) 22:47:57

>>35
別に普通にできるだろ？
ttp://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/8332.txt

38 ：デフォルトの名無しさん：2008/12/16(火) 01:06:33

要素数が少なくなったらO(N^2)に切り替えるというのも、
分割する際についでに数を数えておけば最初の１回以外は何とかなる。
std::list::sort にした方がノードの交換効率もいいし最初でもO(N^2)交換ができるが、
std::sort を使えなくする必要性はないと思われる。

39 ：デフォルトの名無しさん：2008/12/16(火) 01:07:24

×O(N^2)交換
○O(N^2)ソート

40 ：デフォルトの名無しさん：2008/12/16(火) 01:11:06

カウントはO(N)だから最初にやってしまってもいいな

41 ：デフォルトの名無しさん：2008/12/16(火) 20:37:44

age

42 ：デフォルトの名無しさん：2008/12/16(火) 21:15:02

>>38
std::sortはクイックソートである必要はないという建前だから。
例えば、最初はクイックソートするけど、
分割していって要素数が減ったら別のソートをやるということがあるでしょ。

43 ：デフォルトの名無しさん：2008/12/16(火) 22:13:20

>>38 はまさにその話だろ？
リストは普通にO(N^2)ソートできるから問題ない。
std::sort では要素数少ない時は
交換回数の少ない選択ソートが使われる事が多いが、
別に双方向リストでも選択ソートは可能だ。
ttp://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/8359.txt

44 ：デフォルトの名無しさん：2008/12/16(火) 22:50:06

std::sort は O(N logN) で余分なバッファを使わなければ何でもいいのだが、
まさにこれはその要件を満たしてる。
まあ、実際には pivot の扱いを変えないと std::sort としては使えないんだが、
そこは std::sort にするならそう実装すればいいってことで。
（昔書いたコードの使い回しなんで・・・）

当然 std::list::sort として実装した方が効率的なので
std::list::sort が存在することに何も問題は無いんだが、
std::sort を random access iterator に限定して
bidirectional iterator に対してわざわざ使えなくする必要性は無いよね。

45 ：デフォルトの名無しさん：2008/12/17(水) 01:42:19

そんなことほかにも考えているやついるんじゃないかと思ってググってみたら案の定。
http://www.kmonos.net/wlog/68.html#_2116061224
この人の場合、クイックの後で併用するソートの計算量が良くないねという結論で終わっている。

46 ：デフォルトの名無しさん：2008/12/17(水) 19:39:49

なるほど。ヒープソートも使ってんのか。
それじゃしかたないかもね・・・。

47 ：デフォルトの名無しさん：2008/12/18(木) 00:24:05

そろそろだと思うんだ。


Big-O　ショー　タァーイム！！


Comb Sort11最高。

48 ：デフォルトの名無しさん：2008/12/18(木) 00:33:45

gap ありだと bidirectional iterator に適用し辛いな。
余計なバッファを使う必要がある。

49 ：デフォルトの名無しさん：2008/12/18(木) 00:38:10

シェルソートと似たようなアルゴリズムなのに
何でシェルソートより速いんだろうな。

50 ：デフォルトの名無しさん：2008/12/18(木) 01:13:43

コムソートは平均でも最悪でもほぼO(n log n)でしょ？
理論的限界もO(n log n)じゃなかったっけ？
実装簡単だしメモリ食わないし好きだ。

51 ：デフォルトの名無しさん：2008/12/18(木) 08:52:35

コムソートは欲しいときにすぐ書けるのがいい。
安定でないのが玉にキズだけど。

52 ：デフォルトの名無しさん：2008/12/18(木) 14:29:09

ソートって、データの全てのペア(nC2)についての
比較情報だけ（少し無駄がある）あれば、理論的にはOKだよね？

53 ：デフォルトの名無しさん：2008/12/18(木) 16:16:49

その比較演算が全順序関係になっていると保証できればOK

54 ：デフォルトの名無しさん：2008/12/18(木) 19:10:45

じゃんけん風味だと終わんないもんな

55 ：デフォルトの名無しさん：2008/12/18(木) 23:14:10

>>52
だから普通のソート法は最悪でもO(N^2)のオーダーなわけだ。
ボゴソートのような無茶苦茶なものは除いて・・・。

56 ：デフォルトの名無しさん：2008/12/19(金) 00:24:14

bidirectional iterator に適用できる
メモリ使用量 O(lonN) 以下の
最悪計算時間が O(NlogN) のソート法ってないもんかねえ・・・。
ないことが証明されてたりするのかね。

57 ：デフォルトの名無しさん：2008/12/19(金) 07:09:13

ボゴソートは要らない子

58 ：デフォルトの名無しさん：2008/12/20(土) 03:55:59

>>57
そんな彼が好きなんです。

59 ：デフォルトの名無しさん：2009/01/20(火) 20:49:47

ソート済みのデータでも容量がGBやTBクラスだと
どうやって取り扱ったら良いのか分かりません＞＜

60 ：デフォルトの名無しさん：2009/01/21(水) 05:44:47

ISAMとか真似すれば？

61 ：デフォルトの名無しさん：2009/01/31(土) 15:46:45

B木とかそういうので扱えばいいんじゃないかな