- 締切済み
アプレットのクイックソート分割について教えて下さい
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- BLUEPIXY
- ベストアンサー率50% (3003/5914)
JAVA のデモ JDK1.5.0\demo\applets\SortDemo の中に QSortAlgorithm.java があります。 このソースをご覧下さい。
関連するQ&A
- クイックソートの再帰呼び出し後の記述について（特に配列の範囲）
アルゴリズムをすこしかじってみているのですが、いきなり躓いてしまいました。詳しい方にお聞きします。クイックソートの再帰呼び出し後のプログラムの記述がよくわかりません。（特に配列の範囲） ＱｕｉｃｋＳｏｒｔ（Ｈｅａｄ，Ｔａｉｌ）というプログラムがあるとします。最初の一連の処理が終わり、再帰呼び出しの部分で、 ＱｕｉｃｋＳｏｒｔ（Ｈｅａｄ，Ｌｅｆｔ－１）という前半部分を指定した再帰呼び出しとＱｕｉｃｋＳｏｒｔ（Ｒｉｇｈｔ＋１，Ｔａｉｌ）という後半部分を指定した再帰呼び出しがされるとします。ここまでは分かるのですが、この再帰呼び出しのプログラムの実行を記述するとなるとどうなるのでしょうか？特に分からないのはこの再帰呼び出しでさらに再帰呼び出しされるＱｕｉｃｋＳｏｒｔのカッコ内の配列の範囲がどのようになるのか、何か特別な記述はされるのかということです。あとソートの必要のないレベルまで来た場合の処理（記述）も分かりません。どなたかご教授願えないでしょうか？
- 締切済み
- その他（プログラミング・開発）
- クイックソートで・・・
C言語で再帰を利用してクイックソートを書いたのですが、データ数が大きくなるとプログラムが途中で終了してしまいます。これってスタック領域がなくなってしまったからでしょうか？お願いします。
- ベストアンサー
- C・C++・C#
- クイックソートのプログラム
クイックソートのプログラムを作ったのですが、 コンパイルは通っても実行で乱数を取得して、取得した乱数を表示し、 Exception in thread "main" java.lang.StackOverflowError というエラーが出てしまいます。 このエラーはどういう意味ですか？
- ベストアンサー
- Java
- クイックソート
クイックソートのプログラムを作ったのですがうまくいきません 汗 コンパイル時に 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・C++・C#
- クイックソートがうまくいかない
クイックソートの仕様はこうです。 (1)バラバラにランダムで入力した配列から基準値を設定する。 (2)前から順番に辿って行って基準値よりも大きいならば、基準値よりも後に移動、小さいならば、基準値よりも前に移動させる。（私のプログラムの場合は基準値を配列の一番目の数に設定しています。） (3)小さいほうと大きいほうの二つのグループに分かれたらまたそれらのグループごとにクイックソートにかける。 (4)二つのグループを分けることができなくなればソート完了。 動作させてみたところ関数QuickSortの中の「基準値より大きいか小さいかの仕分けの処理」の後で、再帰処理があるのですが、再帰ではなく無限ループになってしまっているようです。 自分では、この処理で無限ループをとめているつもりです。 if(youso==1) { return; } なぜこのようになってしまうのでしょうか お手数ですが、よろしくお願いいたします。 #include<stdio.h> #include<stdlib.h> #include<time.h> #include<string.h> #define N 10 int k,q; void QuickSort(char mi,char hai[10],int youso) { char shoubox[10]; char bigbox[10]; int i,len,len2; k=0,q=0; /*もし配列haiの大きさが1ならば終了*/ if(youso==1) { return; } /*配列の２番目から最後まで基準値からの大小により仕分けしていく。大きいならば、配列bigboxに小さい*/ /*ならば配列shouboxにそれぞれ入れる。*/ for(i=1;i<youso;i++) { if(hai[i]>mi) { bigbox[k++]=hai[i]; } else { shoubox[q++]=hai[i]; } } /*仕分け処理はここまで*/ /*小さいほうの配列と大きいほうの配列をそれぞれクイックソートにかける再帰処理。*/ QuickSort(shoubox[0],shoubox,q); QuickSort(bigbox[0],bigbox,k); /*それぞれのソートが完了したら、配列haiに「小さいほうの配列」→「基準値」→「大きいほうの配列」 の順に値を代入していく。*/ len=strlen(shoubox); for(i=0;i<len;i++) { hai[i]=shoubox[i]; } hai[len]=mi; len2=strlen(bigbox); for(i=(len+1);i<len+len2;i++) { hai[i]=bigbox[i]; } /*代入処理ここまで。*/ } int main(void) { char array[N]; char m; int i,val,j; srand(time(NULL)); /*(1～10)までの数字をランダムに入力する処理*/ for(i=0;i<N;i++) { do{ val=rand()%10; for(j=0;j<i;j++) { if(val+'0'==array[j]) { break; } } }while(j<i); array[i]=val+'0'; } /*ランダムに値を入力する処理ここまで*/ m=array[0]; /*値配列の最初を基準値mに設定*/ QuickSort(m,array,N); /*基準値、配列、要素数を実引数として、クイックソートを呼び出す。*/ /*昇順に並べ替えた配列arrayを出力する。*/ for(i=0;i<N;i++) { printf("array[%d]=%c\n",i,array[i]); } return 0; }
- 締切済み
- C・C++・C#
- クイックソートがうまくいかない
クイックソートとはこういう仕様のソートのことです。 (1)バラバラの配列から基準値を設定する。 (2)前から順番に辿って行って基準値よりも大きいならば、基準値よりも後に移動、小さいならば、基準値よりも前に移動させる。（私のプログラムの場合は基準値を配列の一番目の数に設定しています。） (3)小さいほうと大きいほうの二つのグループに分かれたらまたそれらのグループごとにクイックソートにかける。 (4)二つのグループを分けることができなくなればソート完了。 自分で確かめてみたのですが、どうやら関数QuickSortの中でさらに再帰的にQuickSortにかけるときにバグが発生しているようです。ですが、なぜバグが起きるのかわかりません。 お手数ですが、よろしくお願いいたします。 #include<stdio.h> #include<stdlib.h> #include<time.h> #include<string.h> #define N 10 void QuickSort(char mi,char *hai,int youso) { char *shoubox; char *bigbox; int k=0; int q=0; int i,len,len2; /*もし配列haiの大きさが1ならば終了*/ if(strlen(hai)==1) { return; } /*配列の２番目から最後まで基準値からの大小により仕分けしていく。大きいならば、配列bigboxに小さい*/ /*ならば配列shouboxにそれぞれ入れる。*/ for(i=1;i<youso-1;i++) { if(hai[i]>mi) { bigbox[k++]=hai[i]; } else { shoubox[q++]=hai[i]; } } /*仕分け処理はここまで*/ /*小さいほうの配列と大きいほうの配列をそれぞれクイックソートにかける再帰処理。*/ QuickSort(shoubox[0],shoubox,q); QuickSort(bigbox[0],bigbox,k); /*それぞれのソートが完了したら、配列haiに「小さいほうの配列」→「基準値」→「大きいほうの配列」 の順に値を代入していく。*/ len=strlen(shoubox); for(i=0;i<len;i++) { hai[i]=shoubox[i]; } hai[len]=mi; len2=strlen(bigbox); for(i=(len+1);i<len+len2;i++) { hai[i]=bigbox[i]; } /*代入処理ここまで。*/ } int main(void) { char array[N]; char m; int i,val,j; srand(time(NULL)); /*(1～10)までの数字をランダムに入力する処理*/ for(i=0;i<N;i++) { do{ val=rand()%10; for(j=0;j<i;j++) { if(val+'0'==array[j]) { break; } } }while(j<i); array[i]=val+'0'; } /*ランダムに値を入力する処理ここまで*/ m=array[0]; /*値配列の最初を基準値mに設定*/ QuickSort(m,array,N); /*基準値、配列、要素数を実引数として、クイックソートを呼び出す。*/ /*昇順に並べ替えた配列arrayを出力する。*/ for(i=0;i<N;i++) { printf("array[%d]=%c\n",i,array[i]); } return 0; }
- 締切済み
- C・C++・C#
- JAVAアプレットが動かない
JAVAの勉強がてら「JAVAアプレット入門」という本をかって勉強をはじめようとおもったのですが、サンプルCDについているJAVAアプレットのサンプルプログラムが全く動きません。 そのまま使っているので動かないはずないと思うのですがうごきません。 そこで、不意に思ったのですが、ひょっとして現在ではJAVAアプレットは過去の技術でドノブラウザもサポートしていないということはありますか？ iOSやアンドロイドでは、つかえない（フラッシュと同じような扱いを受けている）という認識があるもので・・・ アプレットという技術は現在もいきているのでしょうか？おとなしくJAVAスクリプトにきりかえたほうがよいでしょうか？
- ベストアンサー
- Java
- Ｃ言語 クイックソートについて
以下の数字を用いて・・・・ num[10] = {21, 46, 87, 9, 32, 33, 57, 87, 12, 43} クイックソートで整列する時，データの入れ替え状況，配列の内容の変化について，データの入れ替え過程をプログラムでない形で説明をお願いします。アルゴリズムの特徴がわかる説明と入れ替え過程を示してほしいです。 以下の数字を用いてお願いします。 例: ●●で分割: { } ●●で分割: { } ・ ・ ・ ・ 整列後: { }
- 締切済み
- C・C++・C#
- JAVAアプレットの仕組みについて
ＨＴＭＬに埋め込まれたＪＡＶＡアプレットが画像を表示するように記述されている場合、ＪＡＶＡアプレットは画像をサーバーからダウンロードして表示しているんですよね？ ＪＡＶＡアプレットがサーバーからファイルをダウンロードできるように、 ＪＡＶＡアプレットがサーバー上にファイルを作り出すこともできるのですか？ 今、計算プログラムをダウンロードで配布して、実行して得られた計算結果を投稿してもらう仕組みを作っているのですが、 ＪＡＶＡアプレットにサーバー上のファイルを操作する能力があるのなら、ＪＡＶＡアプレットを読み込み実行するだけで配布と投稿の作業が一まとめにできてしまうと思いました。 ＪＡＶＡアプレットはサーバー上のファイルをどこまで操作できるのでしょうか？
- ベストアンサー
- Java
- クイックソート
今クイックソートのプログラム作成をしていますが、分からない箇所が幾つかあります。下は、作成した時のプログラムリストです。 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.ソートにかかった比較・コピーの回数を表示 //これも分かりません。 } 分かる人がいましたら教えて下さい。お願いします。
- 締切済み
- Java
お礼
ご丁寧にありがとうございます。 助かります。