質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.80%

double配列のクイックソート

解決済

回答 4

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 625

void_null

score 15

196個の要素のあるdouble配列をクイックソートで大きい順に並べようとしています.しかし,実行するとsegmentation fault が起こります.常に起こるわけでもなく,上手く行くときもあるのですが,その時もどうも惜しい感じで,完全にソートされません.実はソートは自分で組む気は無く,インターネットで漁ったものを利用したのですが,segmentation faultが起こったので,quick_sort関数のifの条件式を left<right から (right-left)>1 と変えたのですが,やはりそれが完全にソートされない原因でしょうか.

コード必要な部分のみ記述します.

呼び出し部分も追記します.
eigenValとeigenVec[]が1対1対応で,eigenVec[]も一緒にソートされて欲しいためにsortIndex[]は置いています.

#define CTGRY        46
#define FTRDIM        196

void swap (double *x, double *y) {
  double temp;

  temp = *x;
  *x = *y;
  *y = temp;
}

int partition (double *array, int left, int right,int *sortIndex) {
  int i, j, pivot;
  i = left;
  j = right + 1;
  pivot = left;

  do{
    do { i++; } while (array[i] > array[pivot] );
    do { j--; } while (array[pivot] > array[j] );

    if (i < j) { 
        swap(&array[i], &array[j]);
        sortIndex[i]=j;
        sortIndex[j]=i;    
    }
  }while(i<j);

  swap(&array[pivot], &array[j]);
  sortIndex[pivot]=j;
  sortIndex[j]=pivot;

  return j;
}

void quick_sort (double *array, int left, int right,int *sortIndex) {
  int pivot;

  if (right>left) {
    pivot = partition(array, left, right,sortIndex);
    quick_sort(array, left, pivot-1,sortIndex);
    quick_sort(array, pivot+1, right,sortIndex);
  }
}

void ReadEigenVV( double EigenVal[CTGRY][FTRDIM], double EigenVec[CTGRY][FTRDIM][FTRDIM] )
{
    FILE *fp;
    int sortIndex[FTRDIM];
    fp=fopen(EIGENVV,"r");
    if(fp==NULL){
        printf("cannot open %s",EIGENVV);
        exit(0);
    }
    int i,j,k;
    for(i=0;i<FTRDIM;i++) sortIndex[i]=i;

    for(i=0;i<CTGRY;i++){
        for(j=0;j<FTRDIM;j++)
            fscanf(fp,"%lf",&EigenVal[i][j]);

        quick_sort(EigenVal[i],0,FTRDIM-1,sortIndex);

        for(j=0;j<FTRDIM;j++)
            for(k=0;k<FTRDIM;k++)
                fscanf(fp,"%lf",&EigenVec[i][sortIndex[j]][k]);

        for(j=0;j<FTRDIM;j++)
            printf("%d:%lf\n",j,EigenVal[i][j]);

    }

}

qsortを使ってみてはとの提案があったのでその方法でも書いてみましたが,こちらはこちらでsegmentation faultは起きてしまいます...

#define    EIGENVV        "eigenvv.dic"
#define CTGRY        46
#define FTRDIM        196

typedef struct
{
    double eigenVal;
    double eigenVec[FTRDIM];
}eigenSet;


int compare(const void *a,const void *b){
    double A= ((eigenSet *)b)->eigenVal;
    double B= ((eigenSet *)a)->eigenVal;

    if(A>B){
        return -1;
    }else if(A<B){
        return 1;
    }else{
        return 0;
    }
}

void ReadEigenVV( double EigenVal[CTGRY][FTRDIM], double EigenVec[CTGRY][FTRDIM][FTRDIM] )
{
    FILE *fp;
    fp=fopen(EIGENVV,"r");
    if(fp==NULL){
        printf("cannot open %s",EIGENVV);
        exit(0);
    }
    int i,j,k;
    eigenSet eSet[FTRDIM];

    for(i=0;i<CTGRY;i++){
        for(j=0;j<FTRDIM;j++)
            fscanf(fp,"%lf",&EigenVal[i][j]);
        for(j=0;j<FTRDIM;j++)
            eSet[j].eigenVal=EigenVal[i][j];

        for(j=0;j<FTRDIM;j++)
            for(k=0;k<FTRDIM;k++)
                fscanf(fp,"%lf",&EigenVec[i][j][k]);
        for(j=0;j<FTRDIM;j++)
            for(k=0;k<FTRDIM;k++)
                eSet[j].eigenVec[k]=EigenVec[i][j][k];


        qsort(eSet,FTRDIM,FTRDIM*sizeof(eigenSet),compare);

        for(j=0;j<FTRDIM;j++)
            EigenVal[i][j]=eSet[j].eigenVal;
        for(j=0;j<FTRDIM;j++)
            for(k=0;k<FTRDIM;k++)
                EigenVec[i][j][k]=eSet[j].eigenVec[k];    

        for(j=0;j<FTRDIM;j++)
            printf("%d:%lf\n",j,EigenVal[i][j]);

    }

}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 4

checkベストアンサー

+4

実はソートは自分で組む気は無く,

であれば、qsort()関数を使いましょう。要素の比較関数を書いて、引数に渡すだけです。

man qsortより:

#include <stdlib.h>

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

quick_sort の呼び出しはどうなっていますか?

    double array[FTRDIM];
    int sortIndex[FTRDIM];

    quick_sort(array, 0, FTRDIM - 1, sortIndex);


right には、ちゃんと FTRDIM -1 を与えていますか?
sortIndex には FTRDIM個の要素がありますか?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

次のように、index も swap しないといけないのではありませんか?

void swap2(int *x, int *y) { int t = *x; *x = *y; *y = t; }

        swap(&array[i], &array[j]);
        swap2(&sortIndex[i], &sortIndex[j]);
    }
  }while(i<j);

  swap(&array[pivot], &array[j]);
  swap2(&sortIndex[pivot], &sortIndex[j]);


そうでないと、quick_sort を呼び出した後の sortIndex には、
重複する値があり、無くなっている値もあります。
そうすると、EigenVec には値が入らないところが出てきます。

どこで Segmentation fault が起こるのか、デバッガーで分かりませんか?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

qsortを使ってみてはとの提案があったのでその方法でも書いてみましたが,こちらはこちらでsegmentation faultは起きてしまいます...

        qsort(eSet,FTRDIM,FTRDIM*sizeof(eigenSet),compare);

qsort関数第3引数は全体サイズでなく一つの要素のサイズです。この場合はsizeof(eigenSet)です。FTRDIM*の部分がいりません。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.80%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る