double配列のクイックソート

Question

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]);

	}
	
}

Answer 1

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

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

man qsortより：

#include <stdlib.h>

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

Answer 2

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

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

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

Answer 3

次のように、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 が起こるのか、デバッガーで分かりませんか？

Answer 4

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

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

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

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