ヒープソートの比較回数を表す一般式がわからないのでどなたか教えてください。
 C=… のかたちでお願いします。

A 回答 (1件)

C=N×logN


こんなんでいいんでしょうか?
ヒープソートのオーダですけど。
    • good
    • 0
この回答へのお礼

それでかまいません。有り難うございました。

お礼日時:2001/08/27 00:12

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qax^2+bx+c=0の求解プロセスをDFDで表したいのですが・・・

ax^2+bx+c=0の求解プロセスをDFDで表したいのですが、aが0か、判別式が正か負か0かなどによって、その後の処理が変わってきますよね?
DFDの場合、そのような分岐はどう書けばよいのでしょうか?

Aベストアンサー

もしかしたらすでに解決されているかもしれませんが…

DFDは、本来、そういうレベルの処理をするものではありません。
フローチャートが処理の流れの記述に偏った反省から、
DFDは、処理ではなくデータの流れる方向を記述するものとなっています。
このぐらいの問題規模なら、むしろフローチャートの方が合ってるでしょう。

まあただ「本来向いていない」と言っても、
そちらには書く必要があるのだと想像します。

一応、分岐を表す記号はあります。
+を○で囲んだ記号を、二つの出力の間に書けば、
「二つの出力のどれかになる」ことを表します。
本では「分離」と言っています。
(ただし、デマルコは「基本的に使わないようにした方がよい」と書いています)

また、「プロセス」から複数の矢印を出すだけでもかまわないと思います。
矢印の側に「判別式が正の場合」「負の場合」など注釈を書いておけばいいでしょう。

Qヒープソートについて

 ヒープでは親子関係を考えると親が子より小さい値をとりますよね。
 それとは逆にヒープソートでは親が子より大きい値をとるとなっていますが何故でしょうか?
 ヒープソートもヒープと同様に親が子より小さい値をとると何か不便なのでしょうか?

Aベストアンサー

それは目的が昇順のソートか降順のソートかによって違うだけです。
昇順のソートをする場合、最大値を最後尾にもって行きますが、このためにはヒープの先頭に最大値が来るようなヒープでなければなりません。

Q比較回数が少なくなるソート

大量にある画像に人間が優劣を判定し、その結果をソートしたいです。(順位を付けたい)
画像はすでにデジタルデータ化されてパソコンの中にあります。

二つの画像を人間に見せて判断を求める事を繰り返すプログラムを作成しようと思うのですが、人間が行う操作(比較の判断)をなるべく少なくする為には、どのようなソートのアルゴリズムを選択したら良いでしょうか?

ソートのアルゴリズムの説明などを読むと、例えば、「バブルソート」及び「選択ソート」ではn(n-1)/2の比較が必要になるそうですが、この比較の回数が最も少ない方法を探しています。

また、例えばA,B,Cの比較に置いて、
A>B、B>Cの比較後にはAとCは比較せずともA>Cの関係が成り立つのですが、こういった事も考慮した上での比較回数の最も少ないソートの方法が知りたいです。

以上、ご指導のほど、よろしくお願い申し上げます。

Aベストアンサー

比較回数を最小にするという意味なので、
ソーティング・ネットワーク問題に類しています。
この問題は、任意に数については結論が出ていないと思うので、
質問への直接の答えは「ない」ということになるかと思います。
マージソートやクイックソートの比較部を外部化して、
人間へのインターフィスを作るのが現実的かと思います。

Qヒープソートを教えてください

本を読んで作ってみたのですが、ソートしてくれません。。

void down(int from, int to);
void heapsort(char s[][WC],int n);

void down(int from, int to){
int i=1, j;
char s[NS][WC],val;

val = s[from][WC];
i = from;

while(i <= to/2){
j = i*2;
if(j+1 <= to && strcmp(s[j],s[j+1])>0)
j++;
if(strcmp(s[j],s[from])>0)
break;
strcpy(s[i],s[j]);
i = j;
}

s[i][WC] = val;
}

void heapsort(char s[][WC],int n) {
int i;
char tmp[WC];
for(i = n/2; i >= 1; i--)
down(i, n);
for(i = n; i >=2; i--){
strcpy(tmp,s[1]);
strcpy(s[1],s[i]);
strcpy(s[i],tmp);
down(1, i-1);
}
}

本を読んで作ってみたのですが、ソートしてくれません。。

void down(int from, int to);
void heapsort(char s[][WC],int n);

void down(int from, int to){
int i=1, j;
char s[NS][WC],val;

val = s[from][WC];
i = from;

while(i <= to/2){
j = i*2;
if(j+1 <= to && strcmp(s[j],s[j+1])>0)
j++;
if(strcmp(s[j],s[from])>0)
break;
strcpy(s[i],s[j]);
i = j;
}

s[i][WC] = val;
}

void heapsort(char s[][WC],int n) {
int i;
char tmp[WC];
for(i = ...続きを読む

Aベストアンサー

ぱっと見で down() が変ですね。

void down(int from, int to){
int i=1, j;
char s[NS][WC],val; ← この配列sは何のためにここで宣言しているのでしょう?

val = s[from][WC]; ← val に取り出した値は何のためのもの?

heapsortでソートを行うためにヒープを作るためのものだと思いますが、
heapsortの引数の s[] がまるきり無視されているので、downで
やっていることは何の意味もないことです。

Tacosaonも書かれてますが、先に一次元の整数配列がきちんとできるように
したほうがよいと思います。

Qテキストベースで表を描く。例:+ - | = >

メールとかでたまに、エクセルなどの添付ファイルではなく、テキストベースで表を描いてくるやり手の方がいます。
+や-や|や=や>を使ってこんなの(↓)。

下手な例:
+-----------+-----------+
| 項目1  | テスト1 | =>
+-----------+-----------+

こういう図を仕事で効率的に書いてみたいのですが、
作成する方法ってご存知でしょうか。
専用のエディタなどがあるのでしょうか。

通常のメーラーはOEとベッキーです。

宜しくお願いします。

Aベストアンサー

秀丸エディタのマクロ機能「秀丸用 罫線マクロ」を
利用することで、効率的にアスキーアートの表を
作成することができると思います。

●秀丸エディタ
http://www.vector.co.jp/soft/win95/writing/se086280.html

●秀丸用 罫線マクロ
http://www.vector.co.jp/soft/win31/writing/se007473.html

お試しください。


人気Q&Aランキング

おすすめ情報