シェルソートの順位性
- シェルソートは内容をソートする処理を行う際、同一の値の順序が崩れる可能性がある
- シェルソートにおいては、n2を先にソートしてからn1をソートする処理を行うが、n1のソート時に同一の値の順序が崩れると、n2のソートが無駄になってしまう
- シェルソートの場合、n1とn2の配列を個別にソートする必要があり、同一の値の順序が保証されない可能性がある
- ベストアンサー
シェルソートの順位性
このカテゴリーのNo.137（#35189）の続きなのですが、シェルソートについてご存知の方お願いします。 上記の質問にて、ヒープソートは完全二分割木型で、同一の値であってもその順序は保証されない、ということがわかりました。 そこで、配列の内容をソートする処理をシェルソートで組んでみました。 やろうとしているのは、n1、n2 の２つの配列に値を入れ、n1 が同じ値だったら n2 の値を使ってソートする、という処理です。 しかし実際には、n3、n4と無制限に続く２次元配列なので各配列を個別にソートしなければならず、n2 を先にソートしてから n1 をソートする、という処理を入れています。 ところがこれだと、n1 のソート時に同一の値の順序が崩れると、せっかく行った n2 のソートが無駄になってしまいます。 シェルソートの場合、こういうことは起こるのでしょうか。 よろしくお願いします。
- その他（プログラミング・開発）
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
ソートには2種類あり、 安定なソート(キーになる値が同値の場合もとの順位が保証される)と 安定でないソートがあります(元の順位が保証されない) 安定なソートでないと多分上記の用件は満たせないでしょう ソートのアルゴリズムについてはweb上で検索するなり、その手の書籍を買えば 色々載っているでしょう シェルソートは安定ではないので同値の順位は崩れてしまいますので 安定なソートを使う必要があると思います 参考URLに各種ソートアルゴリズムのソースコードがあります
関連するQ&A
- ヒープソートは２重ソートできない？
ソートに関して詳しい方、相談にのっていただけたらと思います。 ＣＧＩを使ってヒープソートするロジックを組みました。 そのルーチンはただ単項データをソートするだけでなく、たとえば、配列変数 n1 と 配列変数 n2 にそれぞれデータが入っていたとき、n1 をソートすると、それに連動して n2 の中身も一緒にソートされます。 言うならば、バラバラに並んだビデオテープを番号順に並べ替えると、一緒にタイトルも並べ変わる感じです。 ところが、配列 n1 をソートしていてたまに同じ数字が入っていることがあります。そういうときは n2 の順にしたいのです。 そこで、先に n2 をソートしてから n1 をソートするといいのではと考え、そのようにプログラムを組んでみました。 ところが実際には、n1 をソートした瞬間に、せっかく並べ替えた n2 の内容がバラバラになってしまうのです。 「n1 の内容が同じ場合は n2 を昇順に並べる」という処理を記述していても、実際には n2 の内容はバラバラです。 これはヒープソートを使用している限り仕方のないことなのでしょうか。あるいは何らかの解決方法を知っている方、よろしくお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- 多次元配列のソートの仕方について
Arrayクラスにsortというメソットについて質問です。 配列が多次元の場合、そのどれか１次元についてソートしたいのですが使い方がわからなく質問しました。 たとえば、a[n][m]という配列で a[0][0]=4 a[0][1]=3 a[0][0]=4 a[0][1]=3 a[1][0]=5 a[1][1]=5 → a[1][0]=7 a[1][1]=4 a[2][0]=7 a[2][1]=4 a[2][0]=5 a[2][1]=5 だとします。 この配列をmの値が１のときについて最初の[n]をソートしたいです。 そして、mの値が0の値も[1]でソートしたものと一緒にソートしたいです。
- 締切済み
- Java
- 挿入ソートとマージソート
挿入ソートとマージソートの問題を解いているのですが、 途中で行き詰ってしまいました。 （問題文） サイズnの入力に対して、挿入ソートの実行には8n~2ステップかかり、 マージソートの実行には64nlnnステップかかる。 挿入ソートがマージソートに勝るnの値を求めよ。 補足：ln=eを底とするlog （挿入ソートがマージソートに勝る＝挿入ソートがマージソートより実行時間が早い） 8n~2 <= 64nlnn 8lnn=n e~n=n~8 こういう感じで自分なりに考えてみたのですが、nの値をどのように出して良いのかわからず困っています。 どなたかご教授いただける方いましたらよろしくお願いします。
- ベストアンサー
- その他([技術者向] コンピューター)
- バブルソート
int a[] = {8,45,15,90,62,73,22}をバブルソートを使用して、降順で並べ替える。 以下の説明では、配列の要素数（ここでは７）をＮとしている。 (1) a[N-1] と a[N-2] を比較し、a[N-1] が a[N-2] より大きい場合は、a[N-1] と a[N-2] を入れ替える。 同様に a[ j] が a[ j-1] より大きければ、a[ j] と a[ j-1] を入れ替える。 この操作を、j=N-1からiまで繰り返す。ただし、iは(1)の処理回数を表す値である。(初回を0とする） (2) (1)を i=0 から N-2 まで繰り返す。 (3) 以下の<実行例>を参考に、配列ａのようその各値を標準出力する。 <実行例> 90 73 62 45 22 15 8 という問題なのですが、どうやってもうまく並び替えられません。 a[N-1] の処理はいらないのではないのですか？ どのようにプログラムを書いたらいいのか教えて下さい。 あつかましいですが、できたら解説付きでお願いします。
- ベストアンサー
- Java
- 2次元配列のソート
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 2次元配列のソート $aは2次元配列で、2次元目は連想配列です。 $aの実際の値は以下です。 ('苗字'=>'いけだ', '名前'=>'せいじ'), ('苗字'=>'たなか', '名前'=>'えつし') 2次元目の'名前'でソートを実行し、以下のように整列させるソースを教えてください。 ('苗字'=>'たなか', '名前'=>'えつし'), ('苗字'=>'いけだ', '名前'=>'せいじ') xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
- ベストアンサー
- PHP
- 二次元配列のソート PHP
タイトルのとおりソートを行ってくれる関数を探しております。 $buf[][]の二次元配列の変数を日付の降順に並べ替えたいのですが、そういった関数は用意されていますか？ sort()、rsort()では不可能かと思います。 以下、二次元配列の値です。配列三番目の日付の降順で再格納したいです。 ( [0] => Array ( [0] => 1[1] => name1 [2] => 2006-08-18 ) [1] => Array ( [0] => 2 [1] => name2[2] => 2006-08-28 ) [2] => Array ( [0] => 3[1] => name3 [2] => 2006-08-18 ) [3] => Array ( [0] => 4 [1] => name4[2] => 2006-08-18 ) よろしくお願いいたします。
- ベストアンサー
- PHP
- クイックソートがうまくいかない
クイックソートとはこういう仕様のソートのことです。 (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#
- 多次元配列のソート
過去に同様の質問があったのですが、未回答でしたので質問させていただきます。 多次元配列のうちの一つの列の値でソートし、その他の列にも結果を連動させたいのですが方法が分かりません。 たとえば、a[n][m]という配列で a[0][0]=C a[0][1]=う a[0][0]=A a[0][1]=あ a[1][0]=A a[1][1]=あ → a[1][0]=B a[1][1]=い a[2][0]=B a[2][1]=い a[2][0]=C a[2][1]=う というように、n列でソートしm列でもその結果で並べ替えたいです。 恐らくComparatorインタフェースを使用すると可能かと思うのですが、方法を教えて頂けないでしょうか。
- ベストアンサー
- Java
- クイックソートがうまくいかない
クイックソートの仕様はこうです。 (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#
- シェルソート（Cプログラミング）
シェル・ソート 基本挿入法により、データを昇順にソートする。 というプログラムを実行したいと思ったのですが、エラーがでてしまいコンパイルできません。 書いたプログラムは以下の通りです。 #include<stdio.h> #include<math.h> #define N 100 int main (void) { int a[N],i,j,t; for (i=0;i<N;i++) a[i]=rand(); for (i=1;i<N;i++){ for (j=j-1;j>=0;j--){ if (a[j]>a[j+1]){ t=a[j]; a[j]=a[j+1]; a[j+1]=t; } else break; } } for (i=0;i<N;i++) printf("%8d",a[i]); } エラーメッセージは以下のようにでました。 警告 W8065 sample.c 10: プロトタイプ宣言のない関数 'rand' の呼び出し(関数 main ) 警告 W8070 sample.c 22: 関数は値を返すべき(関数 main ) どうすれば出来るのでしょうか、お答えよろしくお願いします。
- ベストアンサー
- C・C++・C#
お礼
回答が遅くなりました。 ありがとうございました。