C言語の二次元配列のソートについて教えてください。



以下の配列があります。配列に入っている数値を基に降順にソートしたいと思います。ただし、ソート結果から2次元配列の添え字がわかる必要があります。どのようにすればよろしいでしょうか?

また、降順ソート後、数値の大きい配列から選択します。選択された配列の添え字は次の選択には利用できません。例を挙げると以下はソート例の一部です。最初にD[1][3]を選択します。次にD[2][3]を選択肢にしますが、すでに添え字の3は利用されているので選択不可とします。次のD[1][1]は添え字1が使われていますので同様に不可です。D[2][2]の添え字ははじめての選択になるため2番目の選択となります。これも同様に添え字が最終的にわかる必要があります。

D[1][3]=10;
D[2][3]=8;
D[1][1]=7;
D[2][2]=6;



配列の例
D[0][0]=0;
D[0][1]=3;
D[0][2]4;
D[0][3]=1;
D[1][0]=2;
D[1][1]=7;
D[1][2]3;
D[1][3]=10;
D[2][0]=2;
D[2][1]=5;
D[2][2]=6;
D[2][3]=8;

以上2つの質問ですが、どちらか一方の回答のみでも結構です。よろしくお願いします。

回答の条件
  • 1人5回まで
  • 登録:2009/12/31 11:44:51
  • 終了:2009/12/31 16:26:55

ベストアンサー

id:zzz_1980 No.1

zzz_1980回答回数492ベストアンサー獲得回数642009/12/31 14:40:49

ポイント100pt
#include <stdio.h>
#include <stdlib.h>

  typedef struct DATA {
    int d,x,y;
  } DATA;
int compare(DATA *,DATA *);

int compare(DATA *n,DATA *m)
{
  return(n->d<m->d?1:-1);
}

int main(int argc,char *argv[])
{
  int i,j,D[3][4],flags[4];
  DATA data[12];
  D[0][0]=0; D[0][1]=3; D[0][2]=4; D[0][3]=1;
  D[1][0]=2; D[1][1]=7; D[1][2]=3; D[1][3]=10;
  D[2][0]=2; D[2][1]=5; D[2][2]=6; D[2][3]=8;
  for(i=0;i<3;i++){
    for(j=0;j<4;j++){
      data[i*4+j].d=D[i][j];
      data[i*4+j].x=i; data[i*4+j].y=j;
    }
  }
  for(j=0;j<4;j++){
    flags[j]=0;
  }
  qsort(data,12,sizeof(DATA),compare);
  for(i=0;i<12;i++){
    if((flags[data[i].x]==0)&&(flags[data[i].y]==0)){
      printf("d[%d][%d]=%d\n",data[i].x,data[i].y,data[i].d);
      flags[data[i].x]=1; flags[data[i].y]=1;
     }
  }
}


実行結果

% ./xx
d[1][3]=10
d[2][2]=6
d[0][0]=0
%
id:mai_mai_mail

早速の回答ありがとうございます。VS2005 VC コンソールアプリでComplieしてみました。

以下のエラーとなります。構造体 DATAにVoidはつかられませんし、エラーを回避する方法はございますでしょうか。ご教授ください。

エラー 1 error C2664: 'qsort' : 4 番目の引数を 'int (__cdecl *)(DATA *,DATA *)' から 'int (__cdecl *)(const void *,const void *)' に変換できません。(新しい機能 ; ヘルプを参照)

2009/12/31 15:03:13
  • id:km1967
    質問の意味が分からない。
    表示時に降順になっていれば良いということか?
  • id:kn1967
    http://q.hatena.ne.jp/1262227490#c167472
    >km1967 2009-12-31 13:25:06
    >質問の意味が分からない。
    >表示時に降順になっていれば良いということか?

    意味が判らないなら逝ってよし。

    kn1967 も mai_mai_mail さんからは直接回答拒否を受けているが、
    (私が間違った回答をしたのだから、それはそれで当然。)
    そこまでマネするとは猪口才な。
  • id:mai_mai_mail
    分かりづらい質問で申し訳ございません。zzz_1980さんが回答されたCodeは私の意図したものです。まだ、コンパイルエラーが取れずに試行錯誤中です。
  • id:kn1967
    やはり、まだ勘違いしておられるのですか・・・ハァ・・・。

    km1967の思惑通りですね。

    ご質問内容は十分伝わってます。
    伝わってますから回答がついているのであって、
    私には回答権が無いので書けなかっただけです。
    (ヒントくらいと思いましたが、過去にヒントだけを書き込んでも、
     伝わらなかったから、その方法はあきらめているのです。)
  • id:mai_mai_mail
    kn1967さん

    こんにちは。コメントに好感を感じました。こちらの独りよがりな対応ですが、回答拒否をはずさせていただきました。よろしくお願いします。
  • id:Jane_Style
    iはiのみ、jはjのみで添え字を使っているかの判定じゃないのですね
    実行結果はこんな感じで
    D:[1][3] = 10
    D:[2][2] = 6
    D:[0][1] = 3
    若干勘違いしてたみたいですしもう(通らないにしろ)回答も出てますから回答はやめておきます

    それにしても変なプログラムだなぁ
    普通のソートにマスク処理を入れればいいだけなのに
  • id:mai_mai_mail
    Jane_Styleさん

    コメントありがとうございます。以下のコメントの意味がわからなかったので補足します。
    >iはiのみ、jはjのみで添え字を使っているかの判定じゃないのですね

    i,jの2つの添え字の結果から次のプログラムのパラメーターに利用します。

    よろしくお願いします。
  • id:zzz_1980
    qsort をやめて普通にソートしてください。
    //qsort(data,12,sizeof(DATA),compare);
    for(i=12;i>0;i--){
    for(j=0;j<i;j++){
    if(data[j].d<data[j+1].d){
    DATA tmpdata;
    tmpdata=data[j];
    data[j]=data[j+1];
    data[j+1]=tmpdata;
    }
    }
    }
  • id:mai_mai_mail
    ZZZ_1980さん

    ありがとうございました。できました。助かりました。
  • id:Jane_Style
    >i,jの2つの添え字の結果から次のプログラムのパラメーターに利用します。
    回答コメントより了解しております。
    修正箇所も2箇所ですからそんなに悲惨なことにはなりませんけれど
    参考程度にプログラム置いておきましょうか?
  • id:mai_mai_mail
    Jane_Styleさんへ

    もし宜しければ後学のためにご回答いただけるとうれしいです。よろしくお願いします。
  • id:Jane_Style
    #include <stdio.h>
    static int sort_tbl[4][3];   /*ソート後のテーブル*/
    static int D[3][4] = {
      { 0, 3, 4, 1 },
      { 2, 7, 3, 10 },
      { 2, 5, 6, 8 }
    };
    void main( void )
    {
      int Cnt, i, j;
      int max, maxi, maxj;
      int mask1 = 0x00;  /*添え字をつかったかどうかのマスク*/

      for( Cnt = 0; Cnt < 4; Cnt++ ) {
       sort_tbl[Cnt][0] = -1;            /* 初期化*/
       max = maxi = maxj = -1;
       /*最大値を検索*/
       for( i = 0; i < 3; i++ ) {
         for( j = 0; j < 4; j++ ) {
          if( ( D[i][j] > max ) &&        /*現在の最大値以上*/
            ( ( mask1 & ( 1 << i ) ) == 0 ) &&   /*添え字を使っていない*/
            ( ( mask1 & ( 1 << j ) ) == 0 ) ) {   /*添え字を使っていない*/
            max = D[i][j];
            maxi = i;
            maxj = j;
          }
         }
       }
       if( max > -1 ) {              /*初期値でなければテーブルに反映*/
         sort_tbl[Cnt][0] = max;
         sort_tbl[Cnt][1] = maxi;
         sort_tbl[Cnt][2] = maxj;
         D[maxi][maxj] = 0;
         mask1 = mask1 | ( 1 << maxi );        /*使用した添え字をマスクに追加*/
         mask1 = mask1 | ( 1 << maxj );        /*使用した添え字をマスクに追加*/
       }
      }
      for( Cnt = 0; Cnt < 4; Cnt++ ) {
       if( sort_tbl[Cnt][0] > -1 ) {           /*初期化状態でなければ出力*/
         printf( "D:[%d][%d] = %d\n",
             sort_tbl[Cnt][1],sort_tbl[Cnt][2],sort_tbl[Cnt][0] );
       }
      }
    }
    実行結果は解と同じです
    普通の降順ソートにマスク処理を入れただけのもの
    2回も3*4ループする必要はないですからこっちのほうが早いはずです
    それではがんばってください
  • id:mai_mai_mail
    Jane_Styleさんへ

    ありがとうございます。意図したとおりできました。ありがとうございます。速そうですね。使わせていただきます。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません