• ベストアンサー

クイックソートがわかりません

2 12 4 9 7 8 5 3 6 11 15 1 をクイックソートで1ステップごとに配列の状態を書いたらどうなりますか？ 上の配列の場合３つのグループに分けて考えるんですか？

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

  • ベストアンサー
  • wormhole
  • ベストアンサー率28% (1619/5654)
回答No.2

2 12 4 9 7 8 5 3 6 11 15 1 2 1 4 9 7 8 5 3 6 11 15 12 2 1 4 3 7 8 5 9 6 11 15 12 2 1 4 3 5 8 7 9 6 11 15 12 2 1 3 4 5 8 7 9 6 11 15 12 1 2 3 4 5 8 7 9 6 11 15 12 1 2 3 4 5 6 7 9 8 11 15 12 1 2 3 4 5 6 7 9 8 11 15 12 1 2 3 4 5 6 7 8 9 11 15 12 1 2 3 4 5 6 7 8 9 11 12 15 だと思うけど、これ見ただけじゃわからないと思うんですが。 http://sorting.at/ こういうの見た方がわかりやすいんじゃないかなぁ

その他の回答 (1)

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

クイックソートの「なにが」わからないんでしょうか? アルゴリズムがわからないなら調べればいいだけの話ですし, 実際の動作がわからないというならプログラムを書いて動かしてみるのがベストだと思いますよ.

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

関連するQ&A

  • クイックソート

    次の配列 2 12 4 9 7 8 5 3 6 11 15 1 をクイックソートで並び変えるとどうなりますか？ やり方教えてください

  • クイックソートがうまくいかない

    クイックソートとはこういう仕様のソートのことです。 (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; }

  • 何度もすいません。クイックソートのプログラムを教えてください。

    課題の丸投げです。本当にすいません。 学校の課題で、整数配列をクイックソートにより降順に並べる関数を実装したプログラムを作る。という課題で int qsort(int date[], int size)という関数が与えられていて、sizeは配列の大きさを示す。またソートが成功した場合は１を、失敗した場合は０を返値とする。ということなんですがsizeを使ってクイックソートをどうやったら良いのか分からないので教えてください。 課題の丸投げですが、すぐ返事ほしいです。 よろしくお願いします。

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

    下記のソースプログラムの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; }

  • クイックソートがうまくいかない

    クイックソートの仕様はこうです。 (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; }

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

    構造体の配列をqsortで昇順に並び替えるプログラムを作成しています。 対象は数値項目で、単純にNo順に並び替えるイメージです。 クイックソートは、配列の内容によって処理時間が変わると聞いたので、一番遅くなる場合の時間を調べたいのですが、どのような並びだと一番遅くなるのでしょうか？

  • クイックソートって？？

    どこに載せればいいのかわからなかったので ここに載せてみました。 クイックソートってなんですか？？ 簡単なアルゴリズムで答えてください！？ 　　（自分も何言っているのかわらない？？） 簡単に言えばクイックソートってナに？？　　です。 よろしくお願いします。 わかるように簡単でね！！

  • クイックソートのソート

    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)の状態は８と７が交換されていますが これは間違いなのでしょうか 教科書に載っていたのですが

  • アプレットのクイックソート分割について教えて下さい

    JAVA アプレットでクイックソートの基本的な仕組みである分割についてのアプレットを作成したく色々と調べているのですが，再帰呼び出しを使ってソートするクイックソートの情報は沢山あるですが， 中央値を用いて中央値より大きいグループAと中央値よりも小さいグループBというように二つのグループに分ける分割のアプレットのサンプルプログラムは探していますが見つかりません． 分割について詳しいかたがいましたら情報を下さい， 宜しくお願いします．

  • 構造体配列のクイックソート

    こんにちわ。 構造体配列のリストを　ポインタのつなぎ変えによるクイックソートで 以下のようなソートをしたいのですが、悩んでおります。 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をたどっていくことでちゃんと目的の値の昇順になっている というのを実現したいのですが、ポインタのつなぎ変えか何かが 間違っているようで　うまいことできていません。 どなたかご教授いただけますでしょうか。 申し訳ありませんが、よろしウお願いいたします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する