- ベストアンサー
クイックソートのソート
2 8 7 1 3 5 6 4 という数字が並んでいて ４を基準に左から昇順にクイックソートするとしたら 2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4 2 1 7 8 3 5 6 4 (1) 2 1 3 8 7 5 6 4 2 1 3 8 7 5 6 4 2 1 3 4 8 7 5 6 8 というふうになりますが (1)の状態は８と７が交換されていますが これは間違いなのでしょうか 教科書に載っていたのですが
- saya19
- お礼率7% (20/264)
- その他([技術者向] コンピューター)
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
その教科書のプログラムって、どんなアルゴリズムになっていますか? ・アルゴリズムが一般のクイックソートとは違う。 プログラム、(1)は、アルゴリズムに忠実。 ・アルゴリズムは一般のクイックソートと同じ。 プログラムがアルゴリズム通りでない。 (1)は、プログラムに書かれた通り。(≠アルゴリズムとは違う) ・アルゴリズムは一般のクイックソートと同じ。 プログラムもアルゴリズム通り。 (1)は、実際のプログラムと違う。 が考えられます。 この例では、 1) 左から4より大きい値を探す→8 2) その続きから4より小さい値を探す→1 3) 1),2)を交換 となっているように思います。 クイックソートだと通常は 2') 「右から」4より小さい値を探す→「3」 となります。
その他の回答 (1)
- osamuy
- ベストアンサー率42% (1231/2878)
見た感じ、 ＞2 8 7 1 3 5 6 4 ――から ＞2 1 7 8 3 5 6 4 (1) ――になったのなら、「８と７が交換」じゃなくて、「8と1が交換」のような。 教科書が間違っていることはありますが、質問文だけでは判断がつけられないかと。 教科書の出版社名や正しい書籍名、乗っている箇所のページ番号を明らかにしたほうが、回答を得られやすいと思います。 ちなみに、ネットで検索したqsortだと、こんな感じ： http://ideone.com/qxvhF
関連するQ&A
- クイックソートの考え方？
そこで、クイックソートのアルゴリズムで躓いています。 10,20,11,19,13,17,14,16,15 真中の値 13 を基準値として使う。 左から基準値と比較してより大きい値は 20。 右から基準値と比較して20 の手前までのより小さい値11。 両者を置換。 10,11,20,19,13,17,14,16,15 真中の値 13 を基準値として使って比較。 左から基準値と比較してより大きい値は 20。 右から基準値と比較して20 の手前までのより小さい値はない。 基準値と20とを置換。 10,11,13,19,20,17,14,16,15 真中の値 20 を基準値として使って比較。 左から基準値と比較してより大きい値はない。 右から基準値と比較してより小さい値は15。 両者を置換。 10,11,13,19,15,17,14,16,20 真中の値 15 を基準値として使って比較。 左から基準値と比較してより大きい値は19。 右から基準値と比較してより小さい値は14。 両者を置換。 10,11,13,14,15,17,19,16,20 真中の値 15 を基準値として使って比較。 左から基準値と比較してより大きい値はない。 右から基準値と比較してより小さい値はない。 これで15が真中と確定。 この後は、「同じ過程を再帰的に二つのサブセットに適用」するのは同じ。 これは、単に、クイックソートの処理手順を追えばわかる話です。 問題は、「なぜ、『右から基準値と比較して20 の手前まで』なのだ？」ということ。 そうでないと、「堂々巡りに陥るからだ！」というのはわかります。 が、私の理解はそこで立ち往生したままです。 還暦を迎えた私の頭は、オーバーヒート気味。 「そこは、このように考えたらよい」という回答をお願いします。 ※自らの理解力と理解度の問題で質問するのは非常に恐縮。 ※しかし、後一歩の理解の壁を超えたいので質問します。
- ベストアンサー
- Visual Basic
- バブル・ソート、クイック・ソート
N個（N=4,5,6）のデータが全て等しいデータ列（例えばN個の数字全部が1のとき）をバブルソートで並び替えたとき、データの交換回数は何回か。また、同じデータ列をクイックソートで並び替えたときはどうか。 という問題があるのですが、どう比較するのかがわかりません。詳しい方、説明よろしくお願いします。
- 締切済み
- C・C++・C#
- クイックソートがわかりません
2 12 4 9 7 8 5 3 6 11 15 1 をクイックソートで1ステップごとに配列の状態を書いたらどうなりますか？ 上の配列の場合３つのグループに分けて考えるんですか？
- ベストアンサー
- C・C++・C#
- クイックソートについて
下記のソースプログラムの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; }
- 締切済み
- 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#
- qsort/クイックソートについて
構造体の配列をqsortで昇順に並び替えるプログラムを作成しています。 対象は数値項目で、単純にNo順に並び替えるイメージです。 クイックソートは、配列の内容によって処理時間が変わると聞いたので、一番遅くなる場合の時間を調べたいのですが、どのような並びだと一番遅くなるのでしょうか？
- ベストアンサー
- 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#
- 構造体配列のクイックソート
こんにちわ。 構造体配列のリストを ポインタのつなぎ変えによるクイックソートで 以下のようなソートをしたいのですが、悩んでおります。 struct info { int count; struct info *prev; struct info *next; }; int main () { struct info info[5]; /* 初期値設定 */ quick_sort(info, 0, 5); return 0; } 上記のようにして、クイックソートをしたいのですが、 よくあるクイックソートだと 例えば初期値を ＜配列のindex＞要素の値を <0> <1> <2> <3> <4> 5 1 4 3 2 などと定義した場合 普通のクイックソートだと <0> <1> <2> <3> <4> 1 2 3 4 5 というように並び変えられてしまい ＜配列のindex＞と 要素の値の組み合わせが変わってしまいますが、 この組み合わせを変えず、 struct info *if; if = info; for (i=0; i<MAX; i++){ printf("%d", if->count); if = if->next; } printf("\n"); とすることで、indexとしては昇順になっていないが *nextをたどっていくことでちゃんと目的の値の昇順になっている というのを実現したいのですが、ポインタのつなぎ変えか何かが 間違っているようで うまいことできていません。 どなたかご教授いただけますでしょうか。 申し訳ありませんが、よろしウお願いいたします。
- 締切済み
- C・C++・C#
- クイックソートの比較回数について
中央値をピボットとするクイックソートで、入力データ数が１０２４で昇順データの場合はＯ(nlogn)の関係より10240回の比較回数が得られる、というのは合っているでしょうか？ ご回答お願い致します。
- ベストアンサー
- C・C++・C#
