マージソートの要素の比較と交換回数を計測する方法

前へ 次へ
このQ&Aのポイント
  • マージソートの要素の比較と交換回数を計測する方法について説明します。
  • 配列aをマージソートする際、配列bを作業用配列として使用します。
  • マージ処理の実行回数をカウントする配列sを用意し、マージ処理を行うタイミングでカウントします。
回答を見る
  • ベストアンサー

マージソートについて

マージソートの要素の比較と交換回数を計測するプログラムを作っているのですが、マージのどの段階が交換処理になるのかが分からず困っています。 マージ処理の実行回数をカウントする配列ｓを設けて処理をカウントする場合、以下のプログラムだとどのタイミングでカウントすればよいでしょうか？　ちなみに配列aは初めに値を割り振った配列で、配列bは別途で用意した作業用配列です。 最後のfor文やif文付近で配列の値を変化させて計測してみたのですが、計算量に合った動きをしてくれませんorz void merge_sort(int a[], int low, int high){ int mid, i, j, k; if(low >= high) return; mid = (low + high)/2; merge_sort(a, low, mid); merge_sort(a, mid+1, high); for(i = low; i <= mid; i++) b[i] = a[i]; for(i = mid+1, j=high; i <= high; i++, j--) b[i] = a[j]; i = low; j = high; for(k = low; k <= high; k++){ if(b[i] <= b[j]){ a[k] = b [i++]; } else{ a[k] = b[j--]; } } }

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

  • ベストアンサー
  • sirn
  • ベストアンサー率14% (8/55)
回答No.3

ここまでくると完全に回答になってしまうのですが......... マージの部分だけを数えると、出力結果がNlogNになります。 for(k = low; k <= high; k++){ //ここで数える if(b[i] <= b[j]){ a[k] = b [i++]; } else{ a[k] = b[j--]; } }

ise-nobu
質問者

お礼

レスありがとう御座います！ for文の前とif文前で模索していたのですがif文前でしたか。。。 明日もう一度値を変えて検討してみようと思います！

その他の回答 (2)

回答No.2

とりあえず、比較の回数だけカウントすればいいんじゃないでしょうか。 if文の前にcount++;とか入れれば、n*log2(n)ぐらいの数値が出ると思いますが。。

ise-nobu
質問者

お礼

レスありがとう御座います！ 交換というより比較で考えた方がやはりよさそうですかね。。。orz if文前でもう一度検討してみたいと思います！

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

う～ん, 確かにマージソートだと「交換する」というイメージではないですね. 課題かなにかなら, 出した人に聞いてみればいいんじゃないでしょうか. まあ, 「マージ処理の実行回数をカウントする」のになぜ配列が必要なのかもよくわからんけど.

ise-nobu
質問者

お礼

レスありがとう御座います！ 学年の違う講義課題だったので聞くに聞けずで。。。(汗 やはり交換ってイメージは考えにくいですよね。　比較の視点からいろいろまた模索してみたいと思います！

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • マージソート

    マージソートの実行時間を測定するプログラムを書いています。 コンパイルの時にはエラーが出ないのですが、実行するとコマンドプロンプトが強制終了されます。 どこが悪いか、どう直せばいいのか指摘していただけないでしょうか？ よろしくお願いします。 ～qtime.c～ //マージソート実行用プログラム //bcc32 mtime.c merge.c m1.c sfmt.c #include <stdio.h> #include <stdlib.h> #include <time.h> #include "sfmt.h" #define MAX 5000 void merge_sort(int a[], int start, int end); main() { int i , x[MAX] , n; time_t start , end ; int sn; printf("適当な数字の入力 : "); scanf("%d", sn); init_gen_rand(sn); for(i=0; i<MAX; i++) x[i]= (gen_rand32()% MAX);; n=MAX; start = clock(); //測定対象プログラム merge_sort(x, 0, n-1); end = clock(); printf("sort\n"); for(i =0 ; i < n ; i++ ) if ( i == i/100*100) printf("%d\n" , x[i]); printf ("実行時間: %f sec\n" , (double)(end-start) /CLOCKS_PER_SEC); return 0; } ～merge.c～ int b[100]; void merge_array(int x[], int start, int end) { int mid, i, j, k; mid = (start + end) /2; i = start; j = mid + 1; for(k = start; k <= end; k++){ if(x[i] > x[j] && j <= end || i > mid){ b[k] = x[j]; j++; } else{ b[k] = x[i]; i++; } } for(k = start; k <= end; k++){ x[k] = b[k]; } } ～m1.c～ void merge_array(int x[], int start, int end); void merge_sort(int a[], int start, int end); void merge_sort(int a[], int start, int end) { int mid; if(start >= end) return; mid = (start + end) / 2; merge_sort(a, start, mid); merge_sort(a, mid + 1, end); merge_array(a, start, end); }

  • マージソートのプログラム

    ↓が自分の作ったマージソートのプログラムなのですが、コンパイルするとエラーが起きてしまいます。 mergesort()にポインタを引数として渡してる、引数の数が足りない、ということが書いてありますが…。 ちゃんとint型を渡してるし、引数の数も合ってるように思います。 どこがおかしいのでしょう？ #include<stdio.h> #include<stdlib.h> #include<time.h> #define Max 255 int A[Max]; main(){ int n,k; n=inputdata(); int w=1; mergesort(w,n); printdata(n); return(0); } inputdata(){ //配列に乱数を要素として入れていく int n,i; printf("n= "); scanf("%d",&n); //使用者にいくつの要素を入れるか指定してもらう srand(time(NULL)); for(i=1; i<=n; i++){ A[i]=1+rand()%30; } printf("A[%d]={%d,",n,A[1]); for(i=2;i<n;i++) printf("%d,",A[i]); printf("%d}\n",A[n]); return(n); } void mergesort(int p, int r){ int q; if(p<r){ q=(p+r)/2; mergesort(p,q); mergesort(q+1,r); merge(p,q,r); } } void merge(int p, int q, int r){ int i,j,k,B[Max]; i=p; j=q+1; for(k=p;k<=r;k++){ if((j>r) || ((i<=q)&&(A[i]<=A[j]))){ B[k]=A[i]; i++; }else{ B[k]=A[j]; j++; } } for(k=p; k<=r; k++) A[k]=B[k]; } printdata(int n){ int i; printf("A[%d]={%d,",n,A[1]); for(i=2; i<n; i++) printf("%d,",A[i]); printf("%d}\n",A[n]); } ・エラーメッセージ merge1.c: In function ‘main’: merge1.c:12: warning: passing argument 1 of ‘mergesort’ makes pointer from integer without a cast merge1.c:12: error: too few arguments to function ‘mergesort’ merge1.c: At top level: merge1.c:31: error: conflicting types for ‘mergesort’ /usr/include/stdlib.h:294: error: previous declaration of ‘mergesort’ was here merge1.c:41: warning: conflicting types for ‘merge’ merge1.c:37: warning: previous implicit declaration of ‘merge’ was here

  • マージソートについて。

    マージソートについて勉強しており、プログラムを作ってみたのですが どうしてもcc=～～の箇所の数値がおかしく表示されてしまいます #include<stdio.h> int main(void) { int a[5]={20,40,15,35,50}; int b[3]={55,20,65}; int c[8]; int i,z,k; printf("a="); for(i=0;i<5;i++) { printf("%d ",a[i]); } printf("\nb="); for(z=0;z<3;z++) { printf("%d ",b[z]); } while(i <= 5 && z <= 3){ if(i < z){ a[i]=c[k]; i++; } else if(i > z){ b[z]=c[k]; z++; } } while(i<5 && z<3) { i=k; i++; z=k; z++; } printf("\nc=") ; for(k=0;k<8;k++) { printf("%d ",c[k]); } return 0; } ご教授していただければ幸いです。

  • マージソート内の再帰処理にすいて

    #include<stdio.h> #define MAX 4 int temp[MAX]; void marge(int num[],int left,int right) { int i,j,mid,k 　 if(left>=right)return; mid=(left+right)/2; marge(num,left,mid);//(1) maege(num,mid+1,right);//(2) for(i=left;i<=mid;i++) temp[i]=num[i]; for(i=mid+1,j=right;i<=right;i++,j--) temp[i]=num]j]; i=left; j=right; for(k=left;k<=right;k++) if(temp[i]<=temp[j]) num[k]=temp[i++]; else num[k]=temp[j--] } マージソート内はこういった関数を記述してエラーもでないのですが、(1)と(2)の処理がよくわかりません。 (1)は再帰的に処理していってif(left>=right)return;の条件を満たした場合に(2)の処理に入っていきますよね？ その場合、(2)の処理を行う際に(1)が(2)の再帰より前に記述されているので(1)がまた処理されるのでしょうか？ 一連の流れを(1)、(2)を使って表してほしいです。

  • クイックソート

    振り仮名でソートをしたいのですが不等号の「<」など記号など混ぜた時にうまくソートされません。 ロジック的に問題があると思うのですが、平仮名や全角カタカナはソートされてるのです。以下のソースなのですが分かる方ご指摘頂ければ幸いです。 int lo0は固定で0 int hi0は検索結果の数-1となっております。 getKana()は振り仮名をbeanから取得しています。 private void QuickSort(Vector beanValues, int lo0, int hi0) { int low = lo0; int high = hi0; String mid; Object[] records = beanValues.toArray(); if (hi0 > lo0) { mid = ((Bean)records[ ( lo0 + hi0 ) / 2 ]).getKana(); while( low <= high ) { while ((low < hi0) && (((Bean)records[low]).getKana().compareTo(mid) < 0)) { ++low; } while ((high > lo0) && (((Bean)records[high]).getKana().compareTo(mid) > 0)) { --high; } if (low <= high) { swap(beanValues, low, high); ++low; --high; } } if (lo0 < high) QuickSort(beanValues, lo0, high); if (low < hi0) QuickSort(beanValues, low, hi0); } } private void swap(Vector records, int i, int j) { Object T = records.elementAt(i); records.setElementAt(records.elementAt(j), i); records.setElementAt(T, j); } }

  • 非再帰のマージソートについて

    非再帰のマージソートを作成しているのですが、 上手いこと出来なくて困っています。 条件として配列の開始と終了のインデックスを指定して、 その間の要素だけをソートしたいのです。 ex： 　int array[10] = { 9,8,7,6,5,4,3,2,1,0 }; 　MergeSort( array, 2, 6 ); // array[2]～array[6]をソート 　for( int i=0; i<10; i++ ) printf( "%d, ", array[i] ); 　出力） 　　9, 8, 3, 4, 5, 6, 7, 2, 1, 0, 以下のサイトで公開されているマージソートを元に 私なりに弄ってはいるのですが、 メモリを壊してしまうようなエラーが頻発して、 どうもうまくいかないのです・・・。 http://besky-works.spaces.live.com/Blog/cns!555CF2E2F9E31C71!557.entry どなたがおわかりの方がいらっしゃれば、 その方法を教えていただければ助かります。

  • 基準値をランダムに選んでの選択ソート

    配列要素から基準値(pivot)をランダムに選び、K番目に小さい要素を検索するプログラムを書いているのですが、うまくいきません。かなり考えているのですが、何が間違っているのか全然わかりません。どなたか教えていただけないでしょうか？ #include<stdio.h> #include<stdlib.h> #include<time.h> int pivotpoint; void partition3(int *s,int low,int high,int *pivotpoint) { int i,j,randspot; int tmp; int pivotitem; randspot=rand()%(high+1); pivotitem=s[randspot]; j=low; for(i=low+1;i<=high;i++){ if(s[i]<pivotitem){ j++; tmp=s[i]; s[i]=s[j]; s[j]=tmp; } } *pivotpoint=j; tmp=s[low]; s[low]=s[*pivotpoint]; s[*pivotpoint]=tmp; } int selection3(int *s,int low,int high,int k) { if(low==high) return s[low]; else{ partition3(s,low,high,&pivotpoint); if(k==pivotpoint) return s[pivotpoint]; else if(k<pivotpoint) return selection3(s,low,pivotpoint-1,k); else return selection3(s,pivotpoint+1,high,k); } } main() { int num,i,k; int high; int low=0; int s[1000]; struct timeval t1,t2; int seed=2; printf("How many elements?:"); scanf("%d",&high); printf("?n"); printf("What is the kth smallest number?:"); scanf("%d",&k); printf("?n"); srand(seed); for(i=0;i<high;i++){ s[i]=rand(); printf("%d ",s[i]); } printf("?n"); gettimeofday(&t1,0); num=selection3(s,low,high-1,k-1); gettimeofday(&t2,0); printf("Time=%dmicrosec?n", t2.tv_usec-t1.tv_usec); printf("The %dth smallest is %d?n ", k,num); }

  • 配列の中に、リストが入っているものをボトムアップ形式でマージソートして

    配列の中に、リストが入っているものをボトムアップ形式でマージソートしています。 リストは、空のノードの次に文字列が入ったノード、というものです。 sizeは、配列の要素数となっています。 merge_listは、リスト２つをマージするものです。 ２つのリストをマージして、ひとつになったリストを最初のリストが入っていた配列に入れる。 もう片方はＮＵＬＬにする。 順に繰り返していき、配列の要素が１つのみになったらそれを返す・・・ といったアルゴリズムなのですが、うまく配列の中のリストが指定できません。 調べたところ、おそらくプログラム中の矢印があるところに問題があってprintfが実行できないようなんですが、原因がわかりません。 同じ原因によりmerge_listに、マージしたいリストが入っていないようなんですが・・・。 説明下手ですいませんが、どうかよろしくお願いします。 typedef struct list * word_list; struct list { char* word; word_list rest; }; word_list _mergesort(word_list* word_lists, int size) { int i=0, j; while(1){ while(1){ while(word_lists[i] =NULL) //配列に一つ目の要素が見つかるまで回す <-　原因 i++; j = i+1; while(word_lists[j] =NULL)　//配列に二つ目の要素が見つかるまで回す<-　原因 　 j++; 　　　　　　if(j == size) //マージする要素が後ろになかったら終了 　break; //printf("%d,%d\n",i, j); printf("%s\n",word_lists[i] ->rest ->word);　　＜－ここでエラー printf("%s\n",word_lists[j] ->rest ->word); word_lists[i] =merge_list(word_lists[i], word_lists[j]); word_lists[j] =NULL; printf("%s",word_lists[i]->rest ->word); i = j+1; } if(i !=0){ i = 0; }else{ break;　　　　//要素がひとつしかなかったら終了 } } return word_lists[0]; }

  • 選択ソートアルゴリズム（selection sort）について　質問No.1226692のつづき

    BLUEPIXYさん、keikanさんありがとうございました。せっかく教えていただいたのですが、セグメンテーションエラーが出てしまいます。 選択法で基準値(pivot)を使用し、K番目に小さい要素を見つけるプログラムを作成しようとしています。しかし、コンパイル時にセグメンテーションフォルトメッセージが出力されるのですが、どこが間違っているのかわからず、途方にくれています。どなたか教えていただきたく。よろしく御願いいたします。 #include<stdio.h> int s[100]={27,10,12,20,25,13,15,22}; int pivotpoint; int selection(int, int, int); //void partition(int, int, int); main(){ int num; num=selection(0,7,3); printf("The third smallest is %d?n ", num); } int selection(int low,int high,int k) { void partition(int, int, int); //int pivotpoint; if(low==high) return s[low]; else{ partition(low,high,pivotpoint); if(k==pivotpoint) return s[pivotpoint]; else if(k<pivotpoint) return selection(low,pivotpoint-1,k); else return selection(pivotpoint+1,high, k); } } void partition(int low,int high,int pivotpoint) { int i,j; int pivotitem; int tmp; pivotitem=s[low]; j=low; for(i=low+1;i<=high;i++){ if(s[i]<pivotitem){ j++; tmp=s[i]; s[i]=s[j]; s[j]=tmp; } } pivotpoint=j; tmp=s[low]; s[pivotpoint]=s[low]; s[low]=tmp; }

  • 選択法（selection sort）について

    選択法について質問させていただきます。 選択法で基準値(pivot)を使用し、K番目に小さい要素を見つけるプログラムを作成しています。以下は私が作成したプログラムですが、 行き詰まってしまいました。どなたか教えていただけないでしょうか？ちなみに学校の宿題で引数は変えれない状態です。 #include<stdio.h> int selection(int low,int high,int k){ int pivotpoint; int s[]={27,10,12,20,25,13,15,22}; if(low==high) return s[low]; else{ partition(low,high,pivotpoint); if(k==pivotpoint) return s[pivotpoint]; else if(k<pivotpoint) return selection(low,pivotpoint-1,k); else return selection(pivotpoint+1,high, k); } } void partition(int low,int high,int pivotpoint){ int i,j; int pivotitem; int tmp; int s[]={27,10,12,20,25,13,15,22}; pivotitem=s[low]; j=low; for(i=low+1;i<=high;i++){ if(s[i]<pivotitem){ j++; tmp=s[i]; s[i]=s[j]; s[j]=tmp; } } pivotpoint=j; tmp=s[low]; s[pivotpoint]=s[low]; s[low]=tmp; } main(){ int num; int s[]={27,10,12,20,25,13,15,22}; num=selection(0,7,3); printf("the third number is %d?n", num); } エラーメッセージ selection.c:20: error: conflicting types for 'partition' selection.c:10: error: previous implicit declaration of 'partition' was here

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する