• 締切済み

クイックソートの処理速度に関する実験 要素１万個、

クイックソートの処理速度に関する実験 要素１万個、２万個、３万個の配列変数にランダムな値を代入し、・その後クイックソートで小さい順に並べ替える #include<stdio.h> #include<stdlib.h> #include<time.h> #define ASIZE 10000 #define RAND_SEED 0x1131000 void my_sort(int left, int right, int a[]); int main(void){ clock_t start, end; int i,a[ASIZE]; srand(RAND_SEED); for(i=0;i<ASIZE; i++){ a[i]=rand(); } start=clock(); my_sort(0, ASIZE-1, a); end=clock(); printf("%.3f秒でした" ,(end-start)/(double)CLOCKS_PER_SEC); getchar(); return 0; } void my_sort(int left, int right, int a[]){ ここに入れるプログラムがわかりません return; }

みんなの回答

  • asuncion
  • ベストアンサー率33% (2126/6288)
回答No.4

そもそも、 ＞#define ASIZE 10000 ＞int i,a[ASIZE]; このコードで、 ＞要素１万個、２万個、３万個の配列変数にランダムな値を代入 この仕様に対応できているのでしょうか。 それから、乱数の種は、固定値ではなくて例えば時刻とかにするのが 一般的ではないか、と個人的には思います。あ、どうでもいい話か。

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

qsort が「クイックソート」であるという保証はどこにもありません＞#2.

  • nda23
  • ベストアンサー率54% (777/1415)
回答No.2

C言語のqsortを見ましたか？ 次のように説明があるはずです。 void qsort( void *データ配列, unsigned int 要素数, unsigned int 1要素の大きさ, int (*大小判定関数)( void *要素1,void *要素2) ) 掲題の例では以下のようになります。 データ配列 = a 要素数 = right - left 1要素の大きさ = sizeof(int) 大小判定関数 → 自作 (1)最初に大小判定関数の事前定義が 　必要です。 　int 大小判定関数(const void *,const void *); (2)大小判定関数の実装 　static int 大小判定関数(const void *要素1, 　　　　　　　　　　　　　　　　const void *要素2) 　{ 　　　//要素1 < 要素2 なら負の値を返す 　　　if ( *((int *)要素1) < *((int *)要素2) ) return -1; 　　　//要素1 > 要素2 なら正の値を返す 　　　if ( *((int *)要素1) > *((int *)要素2) ) return 1; 　　　//要素1 == 要素2 なら0を返す 　　　return 0; 　} (3)my_sortの実装 　ここまで来ればお分かりでしょうから、 　あとは書きません。 　尚、データ形式が合わないとコンパイルで 　エラーとなるので、適宜キャストしてあげる 　必要があります。 コンパイラは何をお使いか分かりませんが、 日本語のシンボルが使えるものの場合は できるだけ日本語シンボルを使うべきだと 考えます。

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

「クイックソートをする」プログラムを入れてください.

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

関連するQ&A

  • クイックソートの交換回数

    クイックソートを行うプログラムを書いています。 これを、比較回数と交換回数を表示できるように改良したいのですが、うまくいきません。カウントする場所は間違えてないと思うのですが、出力の場所が悪いせいか、大量の出力結果が表示されます。 うまく表示させる方法を教えてください。 ～time.c～ #include <stdio.h> #include <stdlib.h> #include <time.h> #include "sfmt.h" #define MAX 5000 void quick_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(); //測定対象プログラム quick_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; } ～quick.c～ #include <stdio.h> int hikaku = 0, koukan = 0; int divide_array(int x[], int start, int end) { int i, j, tmp; i = start; j = end -1; while(1){ while(x[i] < x[end])i++; hikaku++;　//比較カウント while(x[j] > x[end] && j>i)j--; hikaku++; //比較カウント if(i >= j) break; tmp = x[i]; x[i] = x[j]; x[j] = tmp; koukan++; //交換カウント i++; j--; } tmp = x[i]; x[i] = x[end]; x[end] = tmp; printf("比較回数: %d\n", hikaku); printf("交換回数: %d\n", koukan); return i; } ～quick2.c～ int divide_array(int x[], int start, int end); void quick_sort(int a[], int start, int end); void quick_sort(int a[], int start, int end) { int s; if(start >= end) return; s = divide_array(a, start, end); quick_sort(a, start, s-1); quick_sort(a, s+1, end); }

  • クイックソートについて

    下記のソースプログラムのquick_sort_coreの部分がわかりません。 わかる方助けてください。 あとこのソースを降順にした場合の変更点も教えていただけると助かります。 #include <stdio.h> /* printf()利用のため */ #include <stdlib.h> /* rand()利用のため */ #include <time.h> /* clock()利用のため */ #define N 10 /* 整列対象要素数 */ /** * 配列の中身を表示する関数 * @param a 表示する配列 * @param n 配列の要素数 */ void print_array(const int a[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } /** * 整列されているかどうか確認する関数 * @param a 確認対象配列 * @param n 配列の要素数 */ void is_sorted(const int a[], int n) { int i; for (i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { printf("昇順に整列されていません\n"); return; } } printf("昇順に整列されています\n"); } /** * クイックソートの本体 * @param a 整列対象配列 * @param l 対象の最初の要素番号 * @param r 対象の最後の要素番号 */ void quick_sort_core(int a[], int l, int r) { /* ここを実装する */ } /** * これまでの整列関数のインターフェースにあわせるクイックソート呼び出し関数 * @param a 整列対象配列 * @param n 配列の要素数 */ void quick_sort(int a[], int n) { quick_sort_core(a, 0, n - 1); } int main(void) { int i; int n = N; /* 整列対象要素数 */ int a[N]; clock_t start,end; /* 0からRAND_MAXの一様乱数をn個生成し、配列aに格納 */ for (i = 0; i < n; i++) { a[i] = rand(); /* 出力確認(print_array)するときは a[i]=rand()%100 としておくと見やすい */ } /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 開始時刻の取得 */ start = clock(); /* クイックソート関数の呼び出し */ quick_sort(a, n); /* 終了時刻の取得 */ end = clock(); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 実行時間の表示 */ printf("%d 個の要素のクイックソートの実行に %f [秒]かかりました\n", n, (double)(end - start) / CLOCKS_PER_SEC); return 0; }

  • クイックソート

    #include<stdio.h> #include<stdlib.h> #define MAX 10 int comp(const void *i,const void *j); int main(void) { int sort[MAX], i ; for(i=0 ; i<MAX ; i++){ sort[i] = rand(); } qsort(sort, MAX, sizeof(int), comp); for( i=0; i<MAX ; i++) printf("%d\n", sort[i]); return 0; } int comp (const void *i, const void *j) { return *(int*)i - *(int*)j; } これはクイックソートのプログラムなのですが、 int comp (const void *i, const void *j) { return *(int*)i - *(int*)j; } この部分がわかりません。ここでソートしているのですか？

  • マージソート

    マージソートの実行時間を測定するプログラムを書いています。 コンパイルの時にはエラーが出ないのですが、実行するとコマンドプロンプトが強制終了されます。 どこが悪いか、どう直せばいいのか指摘していただけないでしょうか？ よろしくお願いします。 ～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); }

  • クイックソート（C言語）

    こんにちは<_ _> クイックソートについての質問です。 左端を軸にクイックソートでデータを昇順にソートする プログラムを作ったのですがうまく動きません #include<stdio.h> void quick(int *,int,int); #define N 10 int main(void) { static int a[]={41,24,76,11,45,64,21,69,19,36}; int k,b=0; quick(a,0,N-1); for(k=0;k<N;k++) printf(" %d",a[k]); return 0; } void quick(int a[],int left,int right) { int s,t,i,j; t=right; i=left+1; j=a[left]; if(right>left){ while(1){ while(a[++i]>j); while(a[--t]<j && t>0); if(i>=t){ break; } s=a[i]; a[i]=a[t]; a[t]=s; } s=a[i]; a[i]=j; a[left]=s; quick(a,left,t-1); quick(a,t+1,right); } } 値の入れ替え、軸の入れ替えもしましたが結果として 「41 41 76 69 45 64 41 19 0 36」 このような結果で出力されてしまいます・・・ 時間に余裕のある方いましたらご指導をお願いします。 よろしくお願いします。<_ _>

  • クイックソートについて

    クイックソートのプログラムなんですが、 セグメンテーション違反で実行出来ません。 どこがおかしいのでしょうか？ int main(void) { FILE *fp; int a[10],b=0,n; clock_t start; double jikan; if( (fp = fopen ("quicksort.txt","r") ) == NULL ) { printf("ファイルが見つかりません : quicksort.txt\n"); exit(1); } while( fscanf(fp, "%d", &a[b]) != EOF ) { b++; } start = clock(); quick_sort(a,n); jikan = clock() - start; for(n = 0; n < b ; ++n) { printf("%d ",a[n]); } printf("計算時間 %.3f 秒 \n", jikan/CLOCKS_PER_SEC); return 0; } int partition(int a[], int l, int r) { int i,j,pivot,t; i = l-1; j = r; pivot = a[r]; for(;;) { while( a[++i] < pivot ) ; while( i < --j && pivot < a[j] ) ; if( i >= j ) break; t=a[i]; a[i]=a[j]; a[j]=t; } t=a[i]; a[i]=a[r];a[r]=t; return i; } void quick_sort_1(int a[],int l,int r) { int v; if( l >= r ) return; v = partition( a, l, r); if( l < v-1 ) quick_sort_1( a, l, v-1); if( v+1 < r ) quick_sort_1( a, v+1, r); } void quick_sort(int a[],int n) { quick_sort_1( a, 0, n-1); }

  • クイックソートのアルゴリズムが分かりません＞＜；

    C言語初心者の学習を終えて、アルゴリズムの構造を学んでいる段階のものです。バブルソートを実装することは成功したのですが、クイックソートが実装できません＞＜ 以下は文字列をバブルソートできるアルゴリズムです。 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define MAXCHARSINONELINE 400 #define LINETABLESIZE 100 char linetable[LINETABLESIZE][MAXCHARSINONELINE]; int resultindex[LINETABLESIZE]; int maxtableindex = 0; void addToTable(char *); void initresult(); void mysort(); int mycompare(int, int); void myswap(int, int); char mark[2]; int start; int end; int main(void) { char line[MAXCHARSINONELINE]; char *ret; int i; do { ret = fgets(line,MAXCHARSINONELINE,stdin); if( ret != NULL ) { addToTable(line); } } while(ret != NULL); fprintf(stderr,"sorting...\n"); start = clock(); /* for(i=0; i<10000; i++){ */ initresult(); mysort(); /* } */ end = clock(); fprintf(stderr,"[%f sec]\n",(float)(end-start)/CLOCKS_PER_SEC); fprintf(stderr,"[results]\n"); for( i = 0; i < maxtableindex; i++ ) { printf("(L.%3d):%s",resultindex[i]+1, linetable[ resultindex[i] ]); } return 0; } void addToTable(char *data) { if( maxtableindex >= LINETABLESIZE ) { fprintf(stderr,"Table is full.!\n"); exit(0); } strncpy( linetable[maxtableindex], data, MAXCHARSINONELINE ); maxtableindex++; } void initresult() { int i; for( i = 0; i < maxtableindex; i++ ) { resultindex[i] = i; } } void mysort() { int i,j,k; for( i = maxtableindex-1; i > 0; i-- ) { for( j = 0; j < i; j++ ) { /* printf("--\n"); for(k = 0; k < maxtableindex; k++) { if((k == j) || (k == j + 1)) { strcpy(mark,"*"); } else { strcpy(mark," "); } printf("%s %s", mark, linetable[resultindex[k]]); } printf("--\n"); */ if( mycompare(j, j + 1) > 0) { /* printf("swap %d <----> %d\n",j ,j + 1); */ myswap(j, j + 1); } } } } int mycompare(int i, int j) { return strcmp(linetable[resultindex[i]], linetable[resultindex[j]]); } void myswap(int i, int j) { int tmp; tmp = resultindex[j]; resultindex[j] = resultindex[i]; resultindex[i] = tmp; } このプログラムを改編して、クイックソートにしたいのですが、どこをどうすればよいのでしょうか。 長くなってすみません。 ご回答をお願いします。

  • クイックソートをC++で作りたいのですが・・・

    題の通り、C++でクイックソートを作りたいのですが、以下のコードではセグメンテーションエラーで動きませんでした。partition関数があやしいと思い、色々と試してみたのですが、やはりできなかったので、質問させていただくことにしました。 結果としては、print関数で昇順に表示出来ればいいのですが・・・。 以下のコードのどこをどう変えれば良いのか、ご指摘の方、何卒よろしくお願い致します。 #include <iostream> #include <vector> using namespace std; class Array { private: vector<int> array; public: void insert( int value ){ array.push_back( value ); } int getSize( ){ return (int)array.size( ); } void quick_sort( ){ quick_sort( 0, (int)array.size( ) - 1 ); } void quick_sort( int left, int right ); int partition( int left, int right ); void swap(int *a,int *b){int tmp=*a;*a=*b;*b=tmp;} void print( ); }; // クイックソートにより配列の添字 left ～ right の部分を整列する関数 void Array::quick_sort( int left, int right ) { if ( left >= right ) { return; } int v = partition( left, right ); quick_sort( left, v - 1 ); quick_sort( v + 1, right ); } //この関数を考える // 配列の添字 left ～ right の部分を，pivot の値より小さい要素と，大きい要素に分割し pivot の位置を返す関数 int Array::partition( int left, int right ) { int i=left; //左からの処理位置 int j=right; //右からの処理位置 int pivot=array[(int)(left+right)/2]; //基準 int tmp=0; while(true){ while(array[i]<pivot){i++;} while(array[j]>pivot){j--;} if(i>=j){return i;} tmp=array[i]; array[i]=array[j]; array[j]=tmp; i++; j++; } } // 配列の内容を表示する関数 void Array::print( ) { for ( int i = 0; i < (int)array.size( ); i++ ) { cout << array[i] << " "; } cout << endl; } int main( ) { Array a1; a1.insert( 56 ); a1.insert( 34 ); a1.insert( 57 ); a1.insert( 64 ); a1.insert( 3 ); a1.insert( 87 ); a1.insert( 85 ); a1.insert( 37 ); a1.insert( 21 ); a1.insert( 4 ); a1.insert( 68 ); a1.insert( 62 ); a1.insert( 42 ); a1.insert( 55 ); a1.insert( 63 ); a1.insert( 95 ); a1.insert( 7 ); a1.insert( 32 ); a1.insert( 78 ); a1.insert( 11 ); cout << "要素数: " << a1.getSize( ) << endl; cout << "ソート前: "; a1.print( ); a1.quick_sort( ); // ここで，ソートを行う関数を呼び出す cout << "ソート後: "; a1.print( ); return 0; }

  • クイックソート

    クイックソートのプログラムを作ったのですがうまくいきません　汗 コンパイル時に sample1.c: In function ‘quicksort’: sample1.c:31: error: expected expression before ‘]’ token sample1.c:32: error: expected expression before ‘]’ token sample1.c:32: error: too few arguments to function ‘quicksort’ とでます。 まだアルゴリズムやCは勉強始めたばかりで基本的なところでつまって いるかもしれません。ご教授おねがいします。 /*クイックソート*/ #include<stdio.h> #define MAXDATA 10 #define swap(type,a,b) {type m; m = a; a = b; b = m;} void quicksort(int a[],int left ,int right) { int i,j,pivot; pivot = a[left]; i = left + 1; j = right; while(i <= j){ while(a[i]<pivot) i++; while(a[j]>pivot) j--; if(i<j){ swap(int,a[i],a[j]); i++; j--; } } swap(int,a[left],a[j]); quicksort(a[],left,j-1); quicksort(a[],j+1,right); } int main(void) { int k,j,sort[MAXDATA]; for(k=0;k < MAXDATA;k++) {printf("sort[%d]:",k); scanf("%d",&sort[k]);} for(k=0;k < MAXDATA;k++) printf("%3d",sort[k]); puts("ソートしますか？ Yes:1 No:0 ///"); scanf("%d",&j); if(j==1){ quicksort(sort,0,MAXDATA-1); for(k=0;k < MAXDATA;k++) printf("%3d",sort[k]); } putchar('\n'); return(0); }

  • クイックソートプログラムでセグメンテーション違反がでるのですが

    クイックソートのプログラムを作成したのですが、 実行するとセグメンテーション違反が発生して、上手くいきません。何処に原因があるのでしょうか？ また、セグメンテーションン違反とはどういったころなのでしょうか？ アドバイス宜しくお願いします。 #include <stdio.h> int quick_sort(int *a,int start,int end); int partition(int *a,int start,int end); main() { int n; int a[n]; int i; printf("ソートしたい要素の個数は？\n"); scanf("%d",&n); for(i=0;i<=n-1;i++) a[i]=0; for(i=0;i<=n-1;i++){ printf("%dのデータを入力してください。\n",i+1); scanf("%d",&a[i]); } printf("ソート前のデータは以下の通り\n"); for(i=0;i<=n-1;i++) printf("%d ",a[i]); quick_sort(*a,1,n-1); printf("ソート後のデータは以下の通り\n"); for(i=0;i<=n-1;i++) printf("%d ",a[i]); } int quick_sort(int *a,int start,int end) { int pivot; if(end-start>0){ pivot=partition(a,start,end); quick_sort(a,start,pivot-1); quick_sort(a,pivot+1,end); } } int partition(int *a,int start,int end) { int i,j,pivot,tmp; i=start-1; j=end; pivot=a[end]; while(1){ while(a[++i]<pivot); while(i<--j && a[j]>pivot); if(i>=j) break; tmp=a[i]; a[i]=a[j]; a[j]=tmp; } a[end]=a[i]; a[i]=pivot; return i; }

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する