对文件进行快速排序

Question

我想对文件使用快速排序，但没有任何反应。我的 quiksort 工作，我已经尝试使用随机生成的数组。

typedef double *TABLEAU;


TABLEAU charge_tableau(char *s, int nb_elts) {
    FILE *f = NULL;
    TABLEAU t=malloc(nb_elts*sizeof(double));
    f=fopen("data22", "r");
    int i;
    for(i=0; i<nb_elts; i++)
        fscanf(f,"%lf", t+i);
    fclose(f);
    return t;
}


 void permuter(TABLEAU t, int i, int j){
    int tmp;
    tmp=t[i];
    t[i]=t[j];
    t[j]=tmp;
}


/* quicksort */
int partition(TABLEAU t, int m, int n){
    int pivot, i, j;
    pivot = t[m];
    i = m+1;
    for(j= m+1; j < n; j++){
        if(t[j] <= pivot){
            permuter(t, i, j);
            i++;
        }
    }

    permuter(t, m, i-1);
    return i-1;
}


 void triRapide(TABLEAU t, int nb_elts, int m, int n){
    int indPivot;
    if(m<n){
        indPivot = partition(t, m, n);
        triRapide(t, nb_elts, m, indPivot-1);
        triRapide(t, nb_elts, indPivot+1, n);
    }
 }


int main() {

    TABLEAU t;
    int nb_elts=10, m, n;
    t=charge_tableau("data22", nb_elts);
    triRapide(t, nb_elts,m,n);
    return 0;

}

文件是这样的:

0.612248 0.052802 0.442505 0.189728 0.750432 0.508627 0.491031 0.762011 0.119391 0.603284 0.394294 0.893904 0.842861 0.966140 0.920210 0.973909 0.489751 0.250233 0.671843 0.657750 0.799485 0.947670 0.492462 0.816764 0.351214 0.852527 0.424567 0.701987 0.287918 0.040396 0.928470 0.800661

问题出在我的函数 TABLEAU charge_tableau(char *s, int nb_elts)

Answer 1

您从 main() 对函数 tri_rapide() 的初始调用将未初始化变量 m 和 n 的不确定值作为参数传递。看起来你想要这个：

triRapide(t, nb_elts, 0, nb_elts);

此外，您的 partition() 函数声明 pivot 具有类型 int，但类型 TABLEAU 是 double * 的别名。因此，您截断了枢轴元素的值。对于您的特定数据，这将在每种情况下截断 all 有效数字，因此在每次分区时，除枢轴以外的所有元素都将分配给上分区（在您的实现中，不需要移动它们）。

还要注意，函数 triRapide() 的第二个参数绝对没用。除了在递归时传递它之外，您什么都不做。

对文件进行快速排序

Quicksort on a file

c

quicksort