• ベストアンサー

ｃ言語のクイックソートなんですが・・・

以下のプログラミングなのですが、＊＊＊のところが分かりません。 どなたか教えていただけないでしょうか？ （よろしければ、前後の必要なところも書いていただけると幸いです） void quicksort(int l, int r) { int i,j,p,w; i=＊＊＊; j=＊＊＊; p=a[(int)((l+r)/2)]; while(i<=j) { while(a[i]<p) i++; while(p<a[j]) ＊＊＊; if(i<=j) { w=a[i];a[i]=a[j];＊＊＊; i++;＊＊＊; } } if(l<j) quicksort(l,j); if(i<r) ＊＊＊; }

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

  • ベストアンサー
  • yama5140
  • ベストアンサー率54% (136/250)
回答No.2

件名で「ｃ言語のクイックソートなんですが・・・」としながら、 ＞＊＊＊のところが分かりません。　←　意味不明です。 ソートには他にも方法があることを知っていて、その中から、質問者様が 「クイックソート」を選んだんですよね。 ★クイックソート（のコード化）が判りません。 ですよね。 ◆参考ＵＲＬなどで、「クイックソート」を理解するっきゃないよね。 　また、「再帰」についても理解が必要かと・・・。 「クイックソート」を理解したら、コード化し、 ・５つ位のデータをもとに、うまくソートできるまで書き直す。 ・このとき、随所に printf()文を入れ、過程を確認する。 ●こうして、これからも使うことがあるだろう「クイックソート」が自分のものになる。 ＞前後の必要なところも書いていただけると・・ （このように書かれると、回答者が回答作っている間、質問者様は炬燵でミカンでも食べているのか、と年寄りは考えてしまう） というか、なんで「困り度」が最高なのだろう？。

参考URL：
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/quick-sort.html
nobeing
質問者

お礼

ありがとうございました。 何とか解決できそうです。

その他の回答 (1)

回答No.1

下記URL参照。

参考URL：
http://okwave.jp/qa3515942.html
nobeing
質問者

お礼

ありがとうございました。 何とか解決できそうです。

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

関連するQ&A

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

    クイックソートのプログラムなんですが、 セグメンテーション違反で実行出来ません。 どこがおかしいのでしょうか？ 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); }

  • クイックソート

    今クイックソートのプログラム作成をしていますが、分からない箇所が幾つかあります。下は、作成した時のプログラムリストです。 class QuickSort{ static int compare = 0; 　　static int copy = 0; 　　 static int swap = 0; static void swap(int a[], int i, int j){ 　　　int tmp; tmp = a[i];copy++; a[i] = a[j];copy++; a[j] = tmp;copy++; swap++;} static void showArray(int a[], int l, int r){//配列の内容を表示するメソッドで、動作:部分配列a[l]～a[r]の要素を表示。これが分かりません。 　　　　int a[l] = {1,2,3,4,5,6,7,8,9,10}; int a[r] = {11,12,13,14,15,16,17,18,19,20};} static void initArray(int a[], int N){ int i; 　　　　a[0]=0; for(i=1;i<N;i++) a[i] = i; for(i=1;i<N;i++){ int j,k; j = (int)(java.lang.Math.random()*(N-1)) + 1; k = (int)(java.lang.Math.random()*(N-1)) + 1; swap(a,j,k);}} public static void (int a[],int l, int r) { if (r+1-l <= 1) return; int e = (l+r+1)/2; int c = 0; return a[c]; } static int partition(int a[], int l, int r, int pivot){// 配列の分割を行うメソッドです。そのあと分割に要した比較回数(=iの増加分+jの減少分)を変数compareに加算し、iの値を戻り値として返さないといけませんが、そこんとこが分かりません。 while (true) { while (a[l] < pivot) l = l + 1; while (a[r] >= pivot) r = r - 1; if (l > r) return l; swap(a, l, r); } } static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } int i=0; int j=0; return i; } static void quicksort(int[] a, int l, int r){//(カットオフなしで)再帰的にクイックソートを行うメソッドです。paritionメソッドを用い、a[l]～a[r]を分割値a[r]で分割するのが条件ですが、ここも全然分かりません。 if(l < r){ int i = l; int j = r; int x = a[(i+j)/2]; do{ while(a[i]<x) i++; while(a[j]>x) j--; if(i<=j) { swap(a,i,j); i++; j--; } }while(i<=j); quickort(a,l,j); quicksort(a,i,r); } } static void swap(int[] a, int s, int t){ int temp = a[s]; a[s] = a[t]; a[t] = temp; return; int i,pivot; } public static void main(String args[]){ //上で作ったメソッドを用いて、ソート過程を表示しながらクイックソートを実行 //手順は次のようになる。 　　　　1.要素を(20個もつ)整数型配列aを宣言 　　　　2.整数型変数Nに配列aの要素数を保存 　　　　3.initArrayメソッドを用いて配列aを初期化 4.showArrayメソッドを用いてソート前の配列aの内容を表示 5.変数compare,copyの値を0に初期化 6.quickSortメソッドを用いて配列aを選択ソート 　　　　7.showArrayメソッドを用いてソート後の配列aの内容を表示 8.ソートにかかった比較・コピーの回数を表示 //これも分かりません。 } 分かる人がいましたら教えて下さい。お願いします。

  • クイックソートのプログラムを実行するとエラーが出る

    プログラミング初心者のものです。 ソースのファイル名はquicksortという名前にして、コンパイル＆実行すると、 「Quicksortが原因でQUICKSORT.EXEにエラーが発生しました。Quicksortは終了します。問題が解決しない場合は、コンピュータを再起動してください。」 と、 「Quicksortが原因でKERNEL32.DLLにエラーが発生しました。Quicksortは終了します。問題が解決しない場合は、コンピュータを再起動してください。」 と言うエラーが出てきて最後まで実行されません。 どうしてでしょうか？ちなみにソースは以下のものです。 #include<stdio.h> #define N 10 void quicksort(int a[],int first,int last) { int i,j,p,w,k; k=(first+last)/2; p=a[k]; i=first; j=last; while(i<=j){ while(a[i]<p){ i++; } while(a[j]>p){ j--; } w=a[i]; a[i]=a[j]; a[j]=w; i++; j--; } if(first>j){ quicksort(a,first,j); } if(last>i){ quicksort(a,i,last); } } main() { int a[]={18,97,59,72,5,38,11,43,67,26}; int i; printf("Before:"); for(i=0;i<N;i++){ printf("%4d",a[i]); } printf("\n"); quicksort(a,0,N-1); printf("After:"); for(i=0;i<N;i++){ printf("%4d",a[i]); } printf("\n"); 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); }

  • クイックソート（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」 このような結果で出力されてしまいます・・・ 時間に余裕のある方いましたらご指導をお願いします。 よろしくお願いします。<_ _>

  • クイックソート後の出力(pascal)

    20個の整数データをクイックソートして出力せよ、という課題が出ました。クイックソートまでは出来た（コンパイルできたのでおそらく）のですが、その順に出力する方法がわかりません。どなたかお教えください。 program sort(input,output); const n = 20; type index = 1..n; var A : array[1..n] of integer; i,x,a : integer; p,j,k : index; function PIVOT(i,j : index):integer; var k:index; begin k:=i+1; while (A[i]=A[k]) and (k<=j) do k:=k+1; if k>j then PIVOT:=0 else if A[i]>=A[k] then PIVOT:=i else PIVOT:=k end; procedure SWAP(var x,y:integer); var temp:integer; begin temp:=x; x:=y; y:=temp end; procedure PARTITION(i,j:index; a:integer; var k:index); var l,r:index; begin l:=i; r:=j; while A[l]<a do l:=l+1; while A[r]>=a do r:=r-1; while l<=r do begin SWAP(A[l],A[r]); l:=l+1; r:=r-1; while A[l]<a do l:=l+1; while A[r]>=a do r:=r-1; end; k:=l end; procedure QUICKSORT(i,j:index); var a:integer; p:index; k:index; begin p:=PIVOT(i,j); if p<>0 then begin a:=A[p]; PARTITION(i,j,a,k); QUICKSORT(i,k-1); QUICKSORT(k,j) end end; begin i:=0; i:=1+1; for i:= 1 to n do begin A[i]:=0; end; i:=0; i:=i+1; for i:= 1 to n do begin readln(x); A[i]:=x end; a:=PIVOT(p,j); PARTITION(p,j,A[a],k); QUICKSORT(p,j) end. QUICKSORT(p,j)とend.　の間に出力方法を書き込みたいのです。

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

    クイックソートの比較交換回数を変数countで計算し、表示させようとしているのですがうまくいきません。 改善策を教えていただけないでしょうか。 /* クイックソート */ void quickSort(randomlist_t data[],int n){ /* 実質的な処理は何もせず、クイックソートを実際に行う関数を呼び出すのみ */ int count = 0; quickSort_1(data,0,n-1,count); printf("count:%d\n",count); } /* 実際にクイックソートを行う関数 */ void quickSort_1(randomlist_t data[],int l,int r,int count){ int v; if(l >= r) /* 整列する要素が1つなら、何もしないでリターンする */ return; v = partition(data,l,r,count); /* 枢軸vを基準に分割する */ quickSort_1(data,l,v-1,count); /* 左の部分の配列a[l]～a[v-1]を整列する */ quickSort_1(data,v+1,r,count); /* 右の部分の配列a[v+1]～a[r]を整列する */ } /* 配列a[l]～a[r]を分割する。枢軸の添え字を返す */ int partition(randomlist_t data[],int l,int r,int count){ int i,j,pivot; randomlist_t t; i = l - 1; j = r; /* ポインタiとjを初期化する */ pivot = data[r].no; /* 一番右端の要素を枢軸にする */ for(;;){ /* ポインタiとjとがぶつかるまで繰り返す */ while(data[++i].no < pivot) count++; /* ポインタiを右へ進める */ while(i < --j && pivot < data[j].no) count++; /* ポインタjを左へ進める */ if(i >= j) break; /* ポインタiとjがぶつかったらループを抜ける */ t = data[i]; data[i] = data[j], data[j] = t; /* iの指す要素とjの指す要素を交換する */ count++; } t = data[i]; data[i] = data[r]; data[r] = t; /* a[i]と枢軸を交換する */ count++; return i; }

  • C言語　クイックソートのアルゴリズム

    クイックソートのプログラムを以下のように書くべきところを 　　　　　・・・ int bin_sort(int array[],int l,int r) { ・・・ pivot=array[(l+r)/2]; ・・・ while(1) { 　 while(array[i]<pivot) i++; while(array[j]>pivot) j--; ・・・ 以下のようにしたところ正しくソートされません。 理由が良く解りません。 int bin_sort(int array[],int l,int r) ｛ 　　　 ・・・ 　　pivot=(l+r)/2;　 ・・・ while(1) { while(array[i]<array[pivot]) i++; while(array[j]>array[pivot]) j--;　 ・・・ どうか宜しくお願いします。

  • クイックソートの分割アルゴリズムについて。

    int partition(int[] a,int i,int j,int x){ int l=i,r=j; // 検索が交差するまで繰り返します while(l<=r){ // 軸要素以上のデータを探します while(l<=j && a[l]<x) l++; // 軸要素未満のデータを探します while(r>=i && a[r]>=x) r--; if(l>r) break; int t=a[l]; a[l]=a[r]; a[r]=t; l++; r--; } return l; } この部分でたとえば数値が{5,9,4,2,8,6}と与えられているとしたらどのような交換手順で分割していくのでしょうか？

  • クイックソート

    振り仮名でソートをしたいのですが不等号の「<」など記号など混ぜた時にうまくソートされません。 ロジック的に問題があると思うのですが、平仮名や全角カタカナはソートされてるのです。以下のソースなのですが分かる方ご指摘頂ければ幸いです。 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); } }

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する