アルゴリズムオタク

1 ：デフォルトの名無しさん：2006/03/07(火) 23:06:03

アルゴリズムを考えるのが好きな人、自分以外にいませんか？
エレベーターを待っているときは、動きを制御するアルゴリズムを考えたり
既存のサブルーチンのアルゴリズムを考えたり、ゲームをやってても敵の
動きのアルゴリズムを考え、ストーリーなどは全く頭に入らない
愛読書は「アルゴリズムとデータ構造？」
言語なんて関係ない！アルゴリズムが好き！

765 ：デフォルトの名無しさん：2008/01/14(月) 13:19:16

擬似乱数の多くは線形合同法だから　0〜5が欲しいなら余りを求めるんじゃなくて割り算するのよ

実際は、2^ビット幅/6 と掛け算して、上位ワードを採用するんだけどね

766 ：デフォルトの名無しさん：2008/01/14(月) 13:44:14

一体いつの時代の話ですか

767 ：デフォルトの名無しさん：2008/01/14(月) 14:23:17

>>763
多分勘違いをしていると思うが、% 10000 で [0 .. 9999] にするとき、RAND_MAX が 32767 なら、
[0 .. 2767] が４通りになり、 [2768 .. 9999] が３通りになる。
>762 は、この４通りの部分がゼロ方向に集まることを指しているのだと思う。
[0 .. RAND_MAX] を [0 .. 9999] に線形に写像すれば、４通りの部分が全範囲にわたって均等に分布するようになる。
それでも４通りの部分をなくそうと思ったら、擬似乱数スレにあるように、RAND_MAX - (RAND_MAX % 10000) 以上を棄却するとよい。すると、どちらの方法でも均等になる（元の乱数が均等なら）。

768 ：デフォルトの名無しさん：2008/01/14(月) 15:50:12

[0,1,2, ..,N-1] のN個の整数から一つ選ぶ乱数を次のように実装すると
(int)(rand() / (1.0 + RAND_MAX) * N)

rand() は理想的な乱数生成器だとして、N = RAND_MAX - 1 ならば、
0になる確率が2/RAND_MAX、それ以外は1/RAND_MAXになるよね。
線形な写像でも誤差のせいで均等にならない場合もあると。

>>763 が言ってるのはこのことではないような気もするが

769 ：デフォルトの名無しさん：2008/01/14(月) 16:52:22

>>766 いつの時代ですかって、CのライブラリだろうがDelphiだろうが
みんな標準で入ってる乱数は線形合同法だよ。

770 ：デフォルトの名無しさん：2008/01/14(月) 16:53:12

あ、でも、間違えてる　乱数と掛け算するんだった。

771 ：デフォルトの名無しさん：2008/01/14(月) 17:16:02

Ｄｅｌｐｈｉｗｗｗｗ
一体いつの時代の話ですかｗｗｗｗｗｗｗｗｗｗｗ

772 ：デフォルトの名無しさん：2008/01/14(月) 18:34:49

文字列で指定した式を解析するのに
二分木で逆ポーランドに変換してからやる方法をさっき知って感動した

773 ：デフォルトの名無しさん：2008/01/14(月) 21:12:50

いつも思うんだけどさ
ポーランド記法が既に逆ナンであって
逆ポーランドって言ってしまうと
元に戻ってないか？ってことなんだ

774 ：デフォルトの名無しさん：2008/01/15(火) 05:47:15

>767,768
そういう意味だったのか。
でもなんか中途半端というか偏りを散らした(写像変換した)だけで
本質的な解決策じゃないように感じる。
それに、整数 -> 整数 の変換に実数キャストが挟まるのが凄く無駄に思える。
実数の実装も考慮してないし。
棄却するパターンの方が数学的に美しい。と思う。

775 ：デフォルトの名無しさん：2008/01/15(火) 07:19:20

>>758
大抵の実装は線形合同法。線形合同法の乱数は、そもそも特性が悪い。
そして下位ビット程特性が悪いんだ。
だから、余りを使って下位を採用すると隔たりが普通より大きくなるんだよ。

0〜5の乱数が欲しいなら余りじゃなくて上位を採用しなければいけない。

というのと
rand() % 6; 　は割り算が必要だけど

rand() / (RAND_MAX + 1.0) * 6;
は (RAND_MAX +1)は通常は２のべき乗だから、掛け算＋シフトで計算出来るから
大抵のCPUで後者が高速という

２つの理由がある。

776 ：デフォルトの名無しさん：2008/01/15(火) 07:31:37

gcc -O3 on core2duoで実測してみたけど後者が遅かった記憶がある。

777 ：デフォルトの名無しさん：2008/01/15(火) 07:37:03

>>776
それはgccのRAND_MAXがint型の最大値に近いから、じゃない？

778 ：デフォルトの名無しさん：2008/01/15(火) 07:53:45

>>776 まさか、このまま実行したんじゃないの？
イメージとしては
(long)rand() * ( 1L<<32L )/6L )>>32L;

アセンブラコードだと EDXに2^32/6を入れて
　 MUL EDX
　 MOV EAX,EDX

779 ：デフォルトの名無しさん：2008/01/15(火) 08:14:15

>>778
あー
ゲームとかではあるかもしれないけど、アルゴリズムスレの扱う範疇からは外れてるね

移植性が無さ過ぎる

780 ：デフォルトの名無しさん：2008/01/15(火) 08:31:31

君は実にばかだ

781 ：デフォルトの名無しさん：2008/01/15(火) 08:32:09

よく言われる

782 ：デフォルトの名無しさん：2008/01/15(火) 12:09:53

>>775
「偏る」を「へだたる」って読んでる？

783 ：デフォルトの名無しさん：2008/01/15(火) 14:09:24

さすがにそれはなかろう

784 ：デフォルトの名無しさん：2008/01/15(火) 14:19:39

>>774
>実数の実装も考慮してないし。

え？　intへのキャストを外すだけだろ。
rand() / (RAND_MAX + 1.0) は区間[0,1)
（rand() / (double)(RAND_MAX) なら区間[0,1]）
の実数の乱数だからな。

>>768 のひどい誤差は整数変換のせいなので
むしろ実数の方が均一でより理想的なんだが。

785 ：デフォルトの名無しさん：2008/01/15(火) 18:40:21

>>775
なにが高速だって？

786 ：デフォルトの名無しさん：2008/02/06(水) 02:28:50

実数の配列A,Bから
最も値の近い要素の組A[k],B[l]を求める良い方法はないですか？

787 ：デフォルトの名無しさん：2008/02/06(水) 02:42:39

Aの各要素にA由来という印とインデックスを付加
Bの各要素にB由来という印とインデックスを付加
二つを合わせて配列CとしてCをソート
Cを先頭から走査して隣り合う要素の由来が違うもので差が最小のところを探す
ってのは？
まぁ合わせないでAB別々にソートしてもできるけど

788 ：786：2008/02/06(水) 03:04:22

なるほど、つまり
AB別々にソートしてからマージの要領で
比較していけばいいんですね。
ありがとうございました。

789 ：デフォルトの名無しさん：2008/02/06(水) 10:55:18

ソートアルゴリズムに興味があるんですが、
Ο記法とか計算時間の算出部などの計算式の意味がさっぱりわかりません。
Ο(n log n)とか意味がわかりません・・・
文系で最後に数学に触れたのは高2だったので、とっくに忘れているし元々数学は得意ではありません。
自分もそのうち効率は悪くても自分なりのソートアルゴリズムを考えてみたいと思っているのですが、
何から勉強をはじめたらいいでしょうか？

790 ：デフォルトの名無しさん：2008/02/06(水) 11:34:34

初心者向けのアルゴリズム入門の本なら、Ο記法の説明してあるのもある。
さすがに、log の意味から書いてあるのは少ないと思うが、
それくらいは高校の教科書読んで勉強してこいよ。

791 ：デフォルトの名無しさん：2008/02/06(水) 12:22:49

>>789
nは要素数でO(n log n)はnが増減した時の計算量の増減。
O(n^2)ならnが倍になると計算量が4倍になるってだけ。(3倍なら9倍)
計算量はあくまで計算量なんでアルゴリズムによって単位量あたりの
計算の複雑さは違うからね。
nlognなやつでもクイックソートとヒープソートは速度が大分違う。
メモリの局所性の問題とかもあったりする。

余計なお世話だと思うがソートは優秀なものが出尽くしてしまっているから
今更考え出すより既存のものを学んだ方が良いよ。

792 ：デフォルトの名無しさん：2008/02/07(木) 01:10:13

==俺様用しおり=========================

今日はQTクラスタリングというのを知ったので
このスレにメモっておく。

793 ：デフォルトの名無しさん：2008/02/07(木) 20:12:15

ソートアルゴリズムを知らない状態から自分なりのものを作ると高確率でセレクションソートになる気がする。

794 ：デフォルトの名無しさん：2008/02/07(木) 23:13:29

高校の頃、自力で挿入ソートに辿り着きましたが。
マージャンプログラム作ってて発見したよ。

795 ：デフォルトの名無しさん：2008/02/07(木) 23:21:37

>>791
いろいろ間違ってるよね。O は計算量とは無関係な概念でしょ。

796 ：デフォルトの名無しさん：2008/02/07(木) 23:59:09

は？

797 ：デフォルトの名無しさん：2008/02/08(金) 00:06:36

f(n) = O( g(n) ) であるとは、ある正数 C と正整数 N が存在して
任意の n ≧ N に対して f(n) ≦ C g(n) が成立することをいう

が、オーダ記法の定義でしょ。

計算量をオーダ記法で表現することは多いけど、別に関係はないよね。
オーダ記法で計算量を表さない分野だってあるよ。

798 ：デフォルトの名無しさん：2008/02/08(金) 00:16:49

>>797
ほー勉強になるが全く意味がわからんわｗ
アルゴリズムって難しいね

799 ：デフォルトの名無しさん：2008/02/08(金) 04:02:58

オーダ記法は計算量の理論の研究の中から生まれたもの
だから密接な関係があると言うのが普通
概念として独立させることができるとしても

800 ：デフォルトの名無しさん：2008/02/08(金) 07:55:37

>>799
> オーダ記法は計算量の理論の研究の中から生まれたもの
このことのソースは？

私の認識では、そんなことは年代的に絶対に有り得ない。

計算量の理論は通常はコルモゴロフの1950年か
チューリングの1936年をスタートだと考えるはず。

一方、オーダ記法自体はバッハマンの1894年が初出で、
広く使われるようになったのはランダウの1909年くらいから。

オーダ記法のほうが古い歴史を持っていると思うのだけれど。

801 ：デフォルトの名無しさん：2008/02/08(金) 08:08:46

＞計算量の理論は通常はコルモゴロフの1950年か
＞チューリングの1936年をスタートだと考えるはず。
ダウト

802 ：デフォルトの名無しさん：2008/02/08(金) 08:18:45

では、あなたはいつからだと考えるのが自然だと思うの？

803 ：799：2008/02/08(金) 18:11:40

Wikipedia を見てみたが，確かに私の勘違いだったようだ．スマン．

804 ：デフォルトの名無しさん：2008/02/08(金) 18:18:29

ソースはWikipediaかよ

805 ：デフォルトの名無しさん：2008/02/08(金) 18:44:38

>>804
まあ大目に見てやれ。
その前は脳内ソースだったんだから。

806 ：デフォルトの名無しさん：2008/02/09(土) 20:21:35

こんなのみつけた。ソートを可視化するスクリプトなのか？
http://d.hatena.ne.jp/ytakamiya/20080125

807 ：デフォルトの名無しさん：2008/02/10(日) 16:00:22

Wikipediaにも画像あるし

っつーか10年くらい前に
技術評論者のSoftwareDesign(いまもあるのか？)が記事で
CQ出版のInterfaceが既に過去に取り扱ってた画像を
そっくりそのまま盗用してしまってお詫びしていた

808 ：デフォルトの名無しさん：2008/02/10(日) 20:46:42

>>807 でっていう。

809 ：デフォルトの名無しさん：2008/02/14(木) 07:09:16

suffix arrayは名前の通り、後ろからのインデックスを作っていく様ですが
なぜ前からじゃないんでしょうか

810 ：デフォルトの名無しさん：2008/02/14(木) 07:45:21

>>809
文字列系アルゴリズムでは prefix より suffix のほうが有用だ
（と思われている）から。

811 ：デフォルトの名無しさん：2008/02/14(木) 13:06:56

BM法とか

812 ：デフォルトの名無しさん：2008/02/14(木) 21:33:07

>>809
prefix tree, prefix list などがあるよ。

813 ：デフォルトの名無しさん：2008/02/18(月) 21:23:04

あるアルゴリズムの概念はわかっていても、それをどういう風に実装するかとなると、
自分のレベルが低いため、難しくて実装することができません。
やり方を暗記してしまえば問題ないのですが、
暗記に頼るのではなく、考えてちゃんと実装できるようにしたほうがいいでしょうか？
それとも暗記しとけばいいでしょうか？

814 ：デフォルトの名無しさん：2008/02/18(月) 21:31:54

意味がわからん

815 ：デフォルトの名無しさん：2008/02/18(月) 22:45:51

>813
同じアルゴリズムを毎回毎回実装するなんて愚かしい。そういうものはライブラリとして持っておくべき。
ということで、実装方法を暗記しても意味がない。

結局、何かやりたいことを実現する＝アルゴリズムを考えて実装する、になるし何もかも既存のアルゴリズムが
流用できる、なんてなるわけないから自分で考える必要はでてくる。
その練習として、有名どころのアルゴリズムを自分で実装してみて他の実装と比べてみるというのはいいことだと思う。

816 ：デフォルトの名無しさん：2008/02/18(月) 23:44:27

実装方法が分かって、うまく動けばそれで満足するけどね。
実装できないと言うよりも
適切なアルゴリズムが分かってないんじゃないのかな。
あるいは、目的がぼんやりしているとか。

まぁいずれにしても、アルゴリズムは暗記でいい派だね。
さらには、辞書とか検索で調べられる程度の情報だけでいい。

817 ：デフォルトの名無しさん：2008/02/19(火) 00:38:36

暗記でもいいから一回自分で書いてみたらいいと思うよ。

818 ：デフォルトの名無しさん：2008/02/19(火) 02:25:49

>>813
質問が二つ。

(1) 「自分のレベルが低い」というのは、プログラム能力が低いのか、
それともアルゴリズムを実装に起こす能力が低いのかどっち？
前者なら慣れればなんとかなる。後者ならそもそもアルゴリズムを
十分に理解できていない可能性が高い。

(2) あなたの立場と考えてるアルゴリズムは何？
極端なケースでは、研究者が自分の専門分野のアルゴリズムを
暗記しているようでは全然ダメ。

819 ：デフォルトの名無しさん：2008/02/19(火) 03:36:37

ソートアルゴリズムで言えばクイックソートやバブルソートとかの名前は知ってるけど、
どういう動作するのか、どうプログラムしていいのかとか分からないって状態なんじゃね？

とても概念がわかってるとは言えないと思うけど。

820 ：813：2008/02/19(火) 20:53:16

レス遅くなりすみません。昨日はあのまま寝てしまって・・・

>>819さんの指摘していただいてるような感じです。
ただ、どういう動作をするのかは理解しているつもりなんですが、
書き起こせないってことはやはり概念を理解していないんですかね・・・

>>818
1の質問についてですが、両方ですかねぇ・・・
プログラムでどういう風に書けばいいかわからないみたいな感じです。
特にループ部分などが・・・ループのネストなんてやったことなくて・・・

2についてですが、
立場はただの趣味でやっているみたいなもんですかね。
将来的にプログラマを目指したいとは思っています。
アルゴリズムは探索やソートなどの基本的なものです。

基本的にソートや探索などの関数は、プログラム側で用意されていますし、
>>815さんの仰るとおり外部ライブラリとしてもっておけばいいのですが、
一応理解したうえで使うべきものなのかなぁと思って質問しました。

821 ：デフォルトの名無しさん：2008/02/19(火) 21:02:26

ただのバブルソートだけでもいいからとにかく書いてみれ

自分で手を動かさない香具師は向いてない

822 ：デフォルトの名無しさん：2008/02/19(火) 21:42:40

そのレベルでは，何をするにしてもお話にならないので，
とりあえず何でも良いから山ほどプログラム書くところからだね．

823 ：813：2008/02/19(火) 22:43:50

>>821-822
どうもありがとうざいます。
そうですね。とりあえずプログラムを書きまくってみることにします。

824 ：デフォルトの名無しさん：2008/02/21(木) 00:09:25

新しいソートアルゴリズム発見した！
とはいっても、どうせ同じようなのを他の人が見つけてるだろうけど…

数学的に厳密な書き方を知らないので雰囲気で書くけど、
m個の離散値を取る（たとえば整数1〜mまで、など）集合に属する値のソートの場合、
O(n×m)でソートが出来る。

例えば0〜127の整数10000個を降順ソートするプログラムはこちら

int array[10000] = {};
for(int i = 0; i < 10000; i++) { array[i] = rand() % 128; }

// データ構造を配列から2次元マップに変更
bool map[10000][128] = {}; // 全部false
for(int i = 0; i < 10000; i++) {
for(int j = 0; j < array[i]; j++) { map[i][j] = true; }
}

// ソート
bool result[10000][128] = {}; // 全部false
for(int i = 0; i < 128; i++) {
int count = 0;
for(int j = 0; j < 10000; j++) { if(map[j][i]) result[count++][i] = true; }
}

// 結果を配列に変換
for(int i = 0; i < 10000; i++) {
for(int j = 127; j >= 0; j--) { if(result[i][j]) { array[i] = j; break; } }
}

コンパイル試してませんが…

825 ：デフォルトの名無しさん：2008/02/21(木) 00:34:34

実装が壊滅的に最悪最低で酷くて、
書いたやつは救いようが無いビンソートにしか見えない

826 ：デフォルトの名無しさん：2008/02/21(木) 00:37:02

酷評すぎてワロタ

827 ：デフォルトの名無しさん：2008/02/21(木) 01:02:25

>>824
何このゴミ

828 ：デフォルトの名無しさん：2008/02/21(木) 01:48:20

>>825
同じ事オモタ

829 ：デフォルトの名無しさん：2008/02/21(木) 07:31:17

空間計算量 O(nm) って劣化にも程が

830 ：デフォルトの名無しさん：2008/02/21(木) 10:21:12

ネタだろ？

831 ：デフォルトの名無しさん：2008/02/21(木) 11:57:59

アルゴリズムにソースコードの実装は関係ないだろ、かわいそうにｗ
この実装だと時間・空間計算量O(nm)だけど、
mを定数だと考えると、条件付きO(n)ソートになるな。
最も実用上どうかと思うけど、発想は面白そうだな。可視的にやればうけそう

832 ：824：2008/02/21(木) 16:03:55

今までにない発想で面白いと思ったんだけど、
想像以上に叩かれてｼｮﾝﾎﾞﾘ。スレ汚しすまんでした

833 ：デフォルトの名無しさん：2008/02/21(木) 17:53:30

筋の悪いバケットソートでしかないしなあ

834 ：デフォルトの名無しさん：2008/02/21(木) 18:04:54

作ってみた。
ビンソートと同列だから目新しさは全くないけど、
ドットを左に寄せていくとソートいう発想はなかなかいいな。
ttp://void-main.org/test/824.html

835 ：デフォルトの名無しさん：2008/02/21(木) 19:04:42

もっと簡単な方法を数分で思いついた。

int[] array = new int[10000], count = new int[128]; // 全部ゼロ

for (int i = 0; i < 10000; i++)
　array[i] = (int)(Math.random() * 128);

for (int i = 0; i < 10000; i++)
　count[array[i]]++;

for (int p = 0, i = 0; i < 128; i++)
　for (int j = 0; j < count[i]; i++, p++)
　　array[p] = i;

836 ：デフォルトの名無しさん：2008/02/21(木) 19:11:45

>>835
それは普通のバケットソート

837 ：デフォルトの名無しさん：2008/02/21(木) 23:45:18

アムロの親父スレ

838 ：デフォルトの名無しさん：2008/02/22(金) 05:21:04

自分のことを、誰も思いついてないような画期的なアルゴリズムを簡単に思いつけるような天才だと思ってんの？

839 ：デフォルトの名無しさん：2008/02/22(金) 11:58:34

>>824 >>838
子曰、學而不思則罔。思而不學則殆。

840 ：デフォルトの名無しさん：2008/02/22(金) 12:55:53

自分で考えるのは大事だけど、ここでこんなの思いついたって発表するが痛いってことだろ。
バカだから文脈読めないけど、難しい言葉使って少しでもかしこく見せたいってかｗ

841 ：デフォルトの名無しさん：2008/02/22(金) 13:04:58

なぜ努力もせずにただ考えようとするんだろう

842 ：デフォルトの名無しさん：2008/02/22(金) 17:01:40

基本も分からず、応用は出来ない

843 ：デフォルトの名無しさん：2008/02/22(金) 17:02:23

>>840

> 自分で考えるのは大事だけど、ここでこんなの思いついたって発表するが痛い

いや、それはいいんじゃね？

844 ：デフォルトの名無しさん：2008/02/22(金) 17:04:06

>>841
こういうのを「ゆとり」と言うんだろう

845 ：デフォルトの名無しさん：2008/02/22(金) 17:04:54

それこそ正にチラシの裏に書いておけってやつじゃね

846 ：デフォルトの名無しさん：2008/02/22(金) 17:28:58

でもそれをきっかけに他の住人が何か閃く可能性だってあるじゃん

847 ：デフォルトの名無しさん：2008/02/22(金) 18:28:52

遺伝的プログラムで
個々の優劣が明らかに出来る集団で
各順位の分布を初期からほぼ一定にする様なアルゴリズムってかDNA組合せ無いっすか?
自然淘汰してる様で実は歴史は繰り返すみたいなの

松竹梅な比率
1:3:4 第1世代
↓
1:3:4 第N世代

848 ：デフォルトの名無しさん：2008/02/22(金) 20:19:20

松竹梅それぞれの内から次世代を作れば出来なくは無いと思うけど、なんか意味あんの？

849 ：847：2008/02/22(金) 21:54:22

あ、優劣は生殖能力って事で
例えば各個体に付松なら６回、竹２回、梅１回の試行して次世代も同個体数

確立以上に存在するABO式血液型OO型のナゾを逆方向から見た考察です。

850 ：デフォルト名無しさん：2008/02/22(金) 23:47:58

５＋６/３を２ステップで求めることできる？？

851 ：デフォルトの名無しさん：2008/02/23(土) 10:12:50

>>850
step1 『アルゴリズムオタク』スレで質問する
step2 答えを待つ

852 ：デフォルトの名無しさん：2008/02/23(土) 10:40:16

>>850
質問１　括弧がないけど 5 + (6/3) でいいのかな？
質問２　何を１ステップに数えるの？メモリへのロードとかは？

853 ：デフォルトの名無しさん：2008/02/23(土) 11:02:58

メモリアクセスを除外すると、演算回数が2回なんだから2ステップだけどそれは自明だしね。

854 ：デフォルトの名無しさん：2008/02/23(土) 11:23:09

値のロードを入れると3つの値をロードした瞬間3ステップだしなあ

855 ：デフォルトの名無しさん：2008/02/23(土) 11:29:57

全部固定値なんで何を言いたいのか判らん

a+(b/3) を a,b入力値で　四則演算で求めろとか？
加算＋シフト演算で出すのは２ステップじゃ無理っぽいな

856 ：デフォルトの名無しさん：2008/02/24(日) 11:39:06

>>751
激しくカメレスで恐縮だが、あのソートアルゴリズムは
量子コンピュータ向きなのではないだろうか。えっ、違う？

857 ：デフォルトの名無しさん：2008/02/24(日) 11:59:52

おぬしも相当悪よのう

858 ：デフォルト名無しさん：2008/02/25(月) 21:03:57

８５０です。
教科書で問題として実際に出ているんです・・・・。
おれの頭じゃ無理で・・・

859 ：デフォルトの名無しさん：2008/02/25(月) 21:21:59

>>858
>>852 >>855
質問しといてレスをスルーすんな

860 ：デフォルトの名無しさん：2008/02/26(火) 11:02:00

test

861 ：デフォルトの名無しさん：2008/02/26(火) 19:57:29

エクスプローラのように文字列中の数値を考慮して並び替えるのに
定番の方法ってあるんですかね。
ぐぐっても参考になりそうなのが見つからなかった。
自分で適当に書いてみたが
数値がでかすぎるとオーバーフローしてソート順が狂う。

862 ：デフォルトの名無しさん：2008/02/26(火) 20:59:19

小数点や 3E5 みたいな１０のベキ表現が無いなら右寄せしてから比較すればいいんだけど
そうじゃないなら多倍長浮動小数点を自前で作るしかないね

863 ：デフォルトの名無しさん：2008/02/26(火) 21:07:31

右寄せって何ですか？

用途がファイル名のソートなので
少数とかは考慮しないで大丈夫です。

864 ：デフォルトの名無しさん：2008/02/27(水) 16:39:07

intのランダム数列に対して、ヒープソートとバブルソートをやって、所用時間を比較してるんですけど、
何度やってもバブルソートがヒープソートの半分くらいの時間でソートしてしまいます。
1〜100000のランダム数列に対して、
heap: 167.83 sec
bubb: 83.2852 sec
という感じです。ヒープソートの実装がまずいのでしょうか？
実装はwikipediaからパクりました。

865 ：デフォルトの名無しさん：2008/02/27(水) 16:43:21

864ですが、ソース貼ってもいい？