使用其他数组排序数组

Question

我试图实现一种算法，它使用长度为n的数组对长度的数组r进行排序。我没有看到我的代码错在哪里。我没有得到预期的结果。结果应该看起来像一个填充莫顿曲线的空间。但正如你所看到的，结果包含很多零。我不知道他们来自哪里？你能帮我找到错误吗？这里是我的可执行代码：

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 

#define DIM 2 

// Sort list "r" using list "mInt" 
void sort(unsigned int *mInt, double *r, int n){ 
    unsigned int i, j, ph0; 
    double ph1, ph2; 

    for(i = 1; i <= n-1; i++) 
     for(j = 1; j <= n-i; j++) 
     if(mInt[j-1] >= mInt[j]) 
     { 
      // 1 
      ph1 = r[DIM*(j-1)+0]; 
      ph2 = r[DIM*(j-1)+1]; 
      ph0 = mInt[j-1]; 

      // 2 
      mInt[j-1] = mInt[j]; 
      r[DIM*(j-1)+0] = r[DIM*j+0]; 
      r[DIM*(j-1)+1] = r[DIM*j+1]; 

      // 3 
      mInt[j] = ph0; 
      r[DIM*j+0] = ph1; 
      r[DIM*j+1] = ph2; 
     } 
} 

// Create morton key 
inline unsigned int mortoncode(unsigned int x, unsigned int y){ 
    int answer = 0; 
    for (unsigned int i = 0; i < (sizeof(unsigned int)* 8)/2; ++i) { 
     answer |= (((x & ((unsigned int)1 << i)) << 2*i) | ((y & ((unsigned int)1 << i)) << (2*i + 1))); 
    } 
    return answer; 
} 

// Find max/min values 
double maxValue(double *r, int n, int d){ 
    double max = r[d]; 
    for(int k=0; k<n; k++){ 
     if(max < r[DIM*k+d]){ 
      max = r[DIM*k+d]; 
     } 
    } 
    return max; 
} 
double minValue(double *r, int n, int d){ 
    double min = r[d]; 
    for(int k=0; k<n; k++){ 
     if(min > r[DIM*k+d]){ 
      min = r[DIM*k+d]; 
     } 
    } 
    return min; 
} 

int main(int argc, char **argv){ 
    FILE *f = fopen("data.dat", "w"); 
    int n = 100; 
    double r[n*DIM]; 

    // Initialize data 
    double x1 = 0; 
    double y1 = 0; 
    for(int k=0; k<n; k++){ 
     r[DIM*k+0] = x1; 
     r[DIM*k+1] = y1; 
     x1 += 0.1; 
     if(k % 10 == 0){ 
      y1 += 0.1; 
      x1 = 0; 
     } 
     printf("%lf %lf\n", r[DIM*k+0], r[DIM*k+1]); 
    } 

    // Get max/min values 
    double rMin[DIM]; 
    double rMax[DIM]; 
    for(int d=0; d<DIM; d++){ 
     rMin[d] = minValue(r, n, d); 
     rMax[d] = maxValue(r, n, d); 
    } 

    // Convert double data to integers 
    printf("\n"); 
    unsigned int rInt[n]; 
    for(int k=0; k<n; k++){ 
     for(int d=0; d<DIM; d++){ 
      int idx=DIM*k+d; 
      double map = floor(((2097151)/(rMax[d]-rMin[d]))*r[idx]-rMin[d]); 
      rInt[idx] = (int)map; 
     } 
     printf("%d %d\n", rInt[DIM*k+0], rInt[DIM*k+1]); 
    } 

    // Convert rInt[x_1,y_1,x_2,y_2,...] to Morton key 
    printf("\n"); 
    unsigned int rMor[n]; 
    for(int k=0; k<n; k++){ 
     int idx = DIM*k; 
     rMor[k] = mortoncode(rInt[idx+0], rInt[idx+1]); 
    } 

    // Sort data 
    sort(rMor, r, n); 

    for(int k=0; k<n; k++){ 
     printf("%lf %lf\n", r[DIM*k+0], r[DIM*k+1]); 
     fprintf(f, "%lf, %lf\n", r[DIM*k+0], r[DIM*k+1]); 

    } 

    return 0; 
} 

Answer 1

我相信@BarmakShemirani有了答案半打意见前，你声称：

RINT就是n * DIM大。

但你写道：

unsigned int rInt[n]; 

修复，我不使用它，而是通过使r和rMor到结构的单一阵列，并呼吁它qsort()测试你的sort()程序。他们基本上产生相同的结果，除了重复的索引，其中一个相对翻转为其他放出来：

  qsort       your sort 
index  r0  r1   index  r0  r1 
2456659099 0.400000 0.500000 2456659099 0.400000 1.000000 
2456659099 0.400000 1.000000 2456659099 0.400000 0.500000 

修改后的代码：

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 

#define DIM 2 

typedef struct element { 
    unsigned int m; 
    double r[DIM]; 
} ELEMENT; 

// Sort element structure on member 'm' 

int comparator(const void *p, const void *q) { 

    ELEMENT *a = (ELEMENT *) p; 
    ELEMENT *b = (ELEMENT *) q; 

    return (a->m > b->m) - (a->m < b->m); // compare idiom 
} 

// Create morton key 
unsigned int mortoncode(unsigned int x, unsigned int y) { 
    int answer = 0; 

    for (unsigned int i = 0; i < (sizeof(unsigned int) * 8)/2; i++) { 
     answer |= (((x & (1u << i)) << 2 * i) | ((y & (1u << i)) << (2 * i + 1))); 
    } 

    return answer; 
} 

// Find max/min values 
double maxValue(ELEMENT data[], int n, int d) { 
    double max = data[0].r[d]; 

    for (int k = 0; k < n; k++) { 
     if (max < data[k].r[d]) { 
      max = data[k].r[d]; 
     } 
    } 

    return max; 
} 

double minValue(ELEMENT data[], int n, int d) { 
    double min = data[0].r[d]; 

    for (int k = 0; k < n; k++) { 
     if (min > data[k].r[d]) { 
      min = data[k].r[d]; 
     } 
    } 

    return min; 
} 

int main(int argc, char **argv) { 
    FILE *f = fopen("data.dat", "w"); 
    int n = 100; 
    ELEMENT data[n]; 

    // Initialize data 
    double x1 = 0; 
    double y1 = 0; 

    for (int k = 0; k < n; k++) { 
     data[k].r[0] = x1; 
     data[k].r[1] = y1; 
     x1 += 0.1; 
     if (k % 10 == 0) { 
      y1 += 0.1; 
      x1 = 0; 
     } 
     printf("%lf %lf\n", data[k].r[0], data[k].r[1]); 
    } 
    printf("\n"); 

    // Get max/min values 
    double rMin[DIM]; 
    double rMax[DIM]; 

    for (int d = 0; d < DIM; d++) { 
     rMin[d] = minValue(data, n, d); 
     rMax[d] = maxValue(data, n, d); 
    } 

    // Convert double data to integers 

    unsigned int rInt[DIM * n]; 

    for (int k = 0; k < n; k++) { 
     for (int d = 0; d < DIM; d++) { 
      int idx = DIM * k + d; 
      double map = floor((2097151/(rMax[d] - rMin[d])) * data[k].r[d] - rMin[d]); 
      rInt[idx] = (int) map; 
     } 

     printf("%d %d\n", rInt[DIM * k + 0], rInt[DIM * k + 1]); 
    } 
    printf("\n"); 

    // Convert rInt[x_1, y_1, x_2, y_2, ...] to Morton key 

    for (int k = 0; k < n; k++) { 
     int idx = DIM * k; 
     data[k].m = mortoncode(rInt[idx + 0], rInt[idx + 1]); 
    } 

    // Sort data 
    qsort(data, n, sizeof(ELEMENT), comparator); 

    for (int k = 0; k < n; k++) { 
     printf("%u %lf %lf\n", data[k].m, data[k].r[0], data[k].r[1]); 
     fprintf(f, "%lf, %lf\n", data[k].r[0], data[k].r[1]); 
    } 

    return 0; 
} 

任何时候，你会发现自己创建并行阵列像r和rMor，这通常表示您错过了一个真正的数据结构。