• ベストアンサー

ヒープソートの比較回数

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

質問者が選んだベストアンサー

  • ベストアンサー
  • imak
  • ベストアンサー率50% (3/6)
回答No.1

C=N×logN こんなんでいいんでしょうか? ヒープソートのオーダですけど。

manfgataro
質問者

お礼

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

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. その他（プログラミング・開発）

関連するQ&A

  • ヒープソート

    c言語 でランダムに文字を出力し、 それをヒープソートして昇順し、ならべかえる簡単なプログラムを教えていただけませんか？

  • 比較の回数を少なくする方法

    例えば、１０個のリンゴがあるとします。リンゴの大きさに同じ物は無いと仮定します。（大きさはユニーク） その１０個のリンゴの大きさに順位を付けたいのですが、絶対的な値を取得する「計り」の様な装置は無く、天秤にのせて重さの比較をする事により、順位を求めたいです。（天秤にはリンゴをひとつずつしか乗せられないとします。） 比較の作業をなるべく少なくしたいです。どのように比較したらよいでしょうか？ また、示した例ではリンゴは１０個でしたが、リンゴの数がｎ個になった時の比較の回数の求め方も知りたいです。 以下、完結できてませんが自分のこれまでの考えです。 　ＡＢＣＤＥＦＧＨＩＪ Ａ□■■■■■■■■■ Ｂ□□■■■■■■■■ Ｃ□□□■■■■■■■ Ｄ□□□□■■■■■■ Ｅ□□□□□■■■■■ Ｆ□□□□□□■■■■ Ｇ□□□□□□□■■■ Ｈ□□□□□□□□■■ Ｉ□□□□□□□□□■ リンゴをA～Jとした場合、■の部分の比較をすれば良いかと考え、 比較回数は、N＊N/2 - Nかなと思ったのですのですが、もっと少ない比較で答えを求める事が可能かと思いました。 なぜかと言うと、例えば、A：B比較後にB：C比較の結果がA＜B、B＜CならA-C比較は不用になると考えたからです。 A：B、B：C比較の結果がA＞B、B＜Cになれば、A：Cの比較は必要になるので確立的要素も必要になるのかとも思います。 どのようなご指導でもかまいません、○○について調べろなどのキーワードをくださるだけでもありがたいです。 以上、よろしくご指導の程、お願い申し上げます。

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

    大量にある画像に人間が優劣を判定し、その結果をソートしたいです。（順位を付けたい） 画像はすでにデジタルデータ化されてパソコンの中にあります。 二つの画像を人間に見せて判断を求める事を繰り返すプログラムを作成しようと思うのですが、人間が行う操作（比較の判断）をなるべく少なくする為には、どのようなソートのアルゴリズムを選択したら良いでしょうか？ ソートのアルゴリズムの説明などを読むと、例えば、「バブルソート」及び「選択ソート」ではｎ(ｎ－１)／２の比較が必要になるそうですが、この比較の回数が最も少ない方法を探しています。 また、例えばA,B,Cの比較に置いて、 A＞B、B＞Cの比較後にはAとCは比較せずともA＞Cの関係が成り立つのですが、こういった事も考慮した上での比較回数の最も少ないソートの方法が知りたいです。 以上、ご指導のほど、よろしくお願い申し上げます。

  • ヒープソート

    何回も申し訳ございません。ヒープソートを使用して、K番目に小さい配列の要素を見つけるプログラムを作成していますが、セグメンテーションフォルトが出力され、途方に暮れています。どなたか助けていただけないでしょうか？ #include<stdio.h> #include<stdlib.h> #include<time.h> void heap(int c,int size,int *s){ int child,p; int tmp; child=s[c]; while(1){ p=(c-1)/2;//calculate an index of their parent if(c<0) break; if(c!=0){ if (s[c]>s[c-1]) { c=c-1; } } if (s[p]<=s[c]) break; // break if a parent is smaller than a child tmp=s[p]; s[p]=s[c]; s[c]=tmp; c=p;//declare a parent node as a child node } } void heap_sort(int c,int size,int *s){ int tmp,i,j; //make the first heap for(i=size-1;i>=0;i--){ heap(i,size,s); } //exchange root s and the last s, and sort them for(i=size-1;i>=0;i--){ tmp=s[0]; s[0]=s[i]; s[i]=tmp; for(j=i;j>=0;j--){ heap(j-1,j,s); } } } main() { int num,i,k; int high; int low=0; int s[20]; struct timeval t1,t2; printf("How many elements?:"); scanf("%d",&high); printf("?n"); printf("What number?:"); scanf("%d",&k); printf("?n"); srand((unsigned)time(NULL)); for(i=0;i<high;i++){ s[i]=rand()%10; printf("%d ",s[i]); } printf("?n"); gettimeofday(&t1,0); heap_sort(high-1, high,s); gettimeofday(&t2,0); printf("Time=%dmicrosec?n", t2.tv_usec-t1.tv_usec); printf("The %dth smallest is %d?n ", k,s[k]); }

  • 例年に比較して、豪雨の回数が多いですか？

    最近、「これまでに経験したことのないような大雨になる」すなわち豪雨が多いような気がします。（これまでに・・・・という発表は、今年からである、ことは知っています） 先月（７月）以来、北九州、山陰、北陸・信越、東北と、各地でこれまでに経験・・・という豪雨が、例年に比較して多いように思います。 教えて頂きたい事項は、下のとおりです。 １．例年に比較して、豪雨の回数が多いですか？　例年並みですか？ ２、もし、例年に比較して多い場合、例年と比べて、何（どういう原因）が異なっているのですか？

  • クイックソート キー比較回数をカウント

    クイックソートでキー比較回数をカウントする。 以下のように書いたのですが、 22行目(C++;)の状態ではまだ何かが足りないらしいのですが、何が足りないのか教えてください。 /* ここからプログラム */ #include <stdio.h> #define N 10 /* 配列aの要素数 */ static int a[N] = { 7, 20, 1, 18, 9, 15, 24, 10, 3, 12}; int main() { __int i, j; /* ループカウンタ */ __int temp; /* 交換用 */ __int pivot; /* 基準値 */ __int C = 0; /* キー比較回数C */ __int M = 0; /* データ置換回数M */ __i = 0; /* iを先頭要素番号 */ __j = N - 1; /* jを末尾要素番号 */ __pivot = a[j / 2]; /* 任意の要素を取り出し基準値 */ __while (i <= j){ ____C++; /* 22行目,キー比較回数カウント */ ____while (a[i] < pivot) /* a[i] >= pivot が見つかるまで */ ______i++; /* iを増加 */ ____while (a[j] > pivot) /* a[j] <= pivot が見つかるまで */ ______j--; /* jを減少 */ ____if (i < j && a[i] != a[j]) { /* i < j かつ a[i]≠a[j] ならば */ ______temp = a[i]; /* a[i]とa[j]を交換 */ ______a[i] = a[j]; ______a[j] = temp; ______M++; /* データ置換回数回数カウント */ ______i++; /* iを増加 */ ______j--; /* jを減少 */ ____} ____if (i == j || a[i] == a[j]){ /* i = j かつ a[i] = a[j] ならば */ ______i++; /* iを増加 */ ______j--; /* jを減少 */ ____} __} /* ここから結果表示 */ __for (i = 0; i < N; i++) ____printf("%3d ", a[i]); __printf("\n"); __printf(" キー比較回数 : %3d回\n データ置換回数: %3d回\n", C, M); /* ここまで結果表示 */ __return 0; } /* ここまでプログラム */

  • クイックソートの比較回数について

    中央値をピボットとするクイックソートで、入力データ数が１０２４で昇順データの場合はＯ(nlogn)の関係より10240回の比較回数が得られる、というのは合っているでしょうか？ ご回答お願い致します。

  • 比較回数と交換回数表示について

    クイックソートとバブルソートの比較回数と交換回数を確認するため以下のようなプログラムを作成しました。 #include <stdio.h> #define SIZE 32 short bubble_sort(short s[],int x); short quick_sort(short s[],int y,int z); void show(short s[],int n); short bubble_sort(short s[],int x){ //バブルソート int i,j,count,sum; short tmp; count=0; sum=0; for(i=0; i<SIZE; i++){ for(j=i+1; j<SIZE; j++){ count++; if(s[i] > s[j]){ tmp=s[i]; s[i]=s[j]; s[j]=tmp; sum++; } } } show(s,SIZE); printf("\n比較回数:%d回\n交換回数:%d回\n",count,sum); } short quick_sort(short s[],int left,int right){ //クイックソート int i, j,tmp,count,sum; int point; i = left; j = right; point = s[(left + right) / 2]; count=0; sum=0; while (right!=1) { count++; while (s[i] < point) i++; count++; while (point < s[j]) j--; if (i >= j) break; tmp=s[i]; s[i]=s[j]; s[j]=tmp; i++; j--; sum++; } show(s,SIZE); printf("\n比較回数:%d回\n交換回数:%d回\n",count,sum); if (left < i - 1) quick_sort(s, left, i - 1); if (j + 1 < right) quick_sort(s, j + 1, right); } void show(short s[], int n) { int i; for (i = 0; i < n ; i++){ printf("%d ", s[i]); } printf("\n"); } int main(void){ short s[SIZE] ={25,29,1,32,14,22,26,3,15,27,5,7,24,12,31,23,6,20,10,8,18,16,11,30,13,2,4,21,17,19,9,28}; printf("ソート前:\n"); show(s,SIZE); printf("バブルソート後:\n"); bubble_sort(s,SIZE); printf("\n"); short t[SIZE] ={25,29,1,32,14,22,26,3,15,27,5,7,24,12,31,23,6,20,10,8,18,16,11,30,13,2,4,21,17,19,9,28}; printf("ソート前:\n"); show(t, SIZE); printf("ソート中:\n"); quick_sort(t,0,SIZE-1); printf("クイックソート後:\n"); show(t,SIZE); } これを動かして頂ければ分かるとは思いますが、バブルソートの時のような結果（途中経過なしで最終結果と比較回数と交換回数の表示）を クイックソートでも出したいのですが、うまく出せずに困っています。 どのようにすれば良いのかご指導いただけませんでしょうか？また、実行環境が会社にしかないので、 できれば結果も頂けるとありがたいです。失礼ですみませんがよろしくお願い致します。

  • バブルソートの交換回数、連結（リンク）リストの短所

    バブルソートの交換回数を表す一般的な式（nを用いた式）が分かりません。 具体的には n個のメンバーの場合1ラウンドあたりn/2回の交換なので 全ラウンドでの交換は[(n/2)*{(n-1)/2}]/2=n*(n-1)/8回となるらしいのです。 でも例えば例題で「96 23 87 8 76」というn=5の数字群をバブルソートで並び替えるには、上の式だと並び替える回数は2.5回になってしまいます。小数が出るのはおかしいと思うのですが・・・ この場合交換回数は地道に数えるしかないのでしょうか。 ちなみに比較回数はn(n-1)/2なので10と出せました。 あと連結（リンク）リストの長所は検索できたのですが短所についての記述が見つかりません。 短所はあるのでしょうか、あるならどのような内容なのでしょうか。 一方でもいいので宜しくお願いします。

  • ヒープソートの問題について

    分からない問題があります。 どなたかお教え下さい。よろしくお願いします。 Max-Heapify (A,i) 1. L <- 2i 2. R <- 2i+1 3. if L<= heap-size[A] かつ A[L] > A[i] 4. then largest <- L 5. else largest <- i 6. if R<= heap-size[A] かつA[R] > A[largest]) 7. then largest <-R 8. if largest !=i 9. then 値の交換A[i] <-> A[largest] 10. Max-Heapify (A,largest) Build-Max-Heap (A) 1. heap-size[A] <- length[A] 2. for i<- ⌊length[A] /2⌋ downto 1 3 do Max-Heapify (A,i) Heap-Sort (A) 1. Build-Max-Heap (A) 2. for i<- length[A] downto 2 3 do 値の交換 A[1]<->A[i] 4 heap-size[A] = heap-size [A] – 1 5 Build-Max-Heap (A) 上に示す疑似コードを参考に、以下の問いに答えなさい。ただし、length[A]、heap-size[A]は配列Aの要素数、配列Aに格納されているヒープの要素をそれぞれ示す。 a. ヒープに格納される要素数をnとし、要素の添字の範囲を求めなさい。 b. 配列A=<3,9,8,15,4,2,5,1,7,10>からBuild-Max-Heapによりmax-ヒープを生成したときの結果を示しなさい。 c. 上のHeapsortは、配列を正しくソートするか？しないなら、正しくソートするようにするにはどのように修正すればよいか？理由と共に答えなさい。 d. マージソートと比較してヒープソートの良い点を述べなさい。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する