数组排序使用C

Question

我不是C专家，我已经通过论坛阅读，但我还是需要一些建议关于对C.

排序的问题，我有双打的4个动态数组中的所有C.他们是相同的大小，并且可以说n。我想要做的是使用其中一个数组作为第一序列和第二个数组作为我的第二序列对它们进行排序。所以如果数组是* x，* y，* w和* z。我想根据* x的值对它们进行排序，然后* y。

我必须这样做，因为数组非常大。

任何帮助将不胜感激。

Answer 1

的容易的方法来做到这将是你的映射四个单独的阵列到结构类型的单个阵列等

struct rec { 
    double x; 
    double y; 
    double w; 
    double z; 
}; 

struct rec *arr = malloc(sizeof *arr * N); // where N is the number of 
              // elements in each array 

if (!arr) 
    // malloc failed, handle error somehow 

for (size_t i = 0; i < N; i++) 
{ 
    arr[i].x = x[i]; 
    arr[i].y = y[i]; 
    arr[i].w = w[i]; 
    arr[i].z = z[i]; 
} 

，然后创建一个比较函数传递给qsort：

int cmpRec(const void *lhs, const void *rhs) 
{ 
    struct rec *l = lhs; 
    struct rec *r = rhs; 

    if (l->x < r->x) 
    return -1; 
    else if (l->x > r->x) 
    return 1; 
    else 
    { 
    if (l->y < r->y) 
     return -1; 
    else if (l->y > r->y) 
     return 1; 
    else 
     return 0; 
    } 

    return 0; 
} 

现在你可以使用qsort库函数来进行排序结构的数组：

qsort(arr, N, sizeof *arr, cmpRec); 

一旦数组进行排序，您可以将结果映射回到你的四个原始阵列。

Answer 2

如果你不能用

typedef struct Point { 
    double x; 
    double y; 
    double w; 
    double z; 
} Point; 

使用的qsort使用qsort与

typedef struct UglyThing { 
    double x; 
    int i; 
} UglyThing; 

创建大小为n的数组，填补x，其中x的值，我用指数。 调用qsort。最后，我将存储排列顺序。 根据排列顺序交换另外三个数组。 然后在y方向上对小数组（“使用相同的x”）进行同样的操作。

如果这个丑陋的诡计是不可能的，那么除了重新发明轮子，我没有看到任何其他解决方案。

（编辑：我刚才看到安德鲁说了一句很接近这个答案...对不起！） 再见，

弗朗西斯

Answer 3

显然，使用标准qsort()对此进行排序不会起作用;没有一种传递四个数组的机制。同样清楚的是，如果数据结构为结构数组，那么使用qsort()将是可行的。

问题1：创建一个结构数组，加载它，对它进行排序，然后卸载回原始数组是可行的吗？

问题2：另一选项是排序整数数组：

int indexes[n]; 
for (int i = 0; i < n; i++) 
    indexes[i] = i; 

qsort(indexes, n, sizeof(indexes[0]), comparator); 

的comparator功能将必须能够访问x和y数组作为文件范围的变量：

int comparator(void const *v1, void const *v2) 
{ 
    int i1 = *(int *)v1; 
    int i2 = *(int *)v2; 
    extern double *x, *y; 
    if (x[i1] > x[i2]) 
     return +1; 
    else if (x[i1] < x[i2]) 
     return -1; 
    else if (y[i1] > y[i2]) 
     return +1; 
    else if (y[i1] < y[i2]) 
     return -1; 
    else 
     return 0; 
} 

然后，您可以使用x[indexes[i]]等访问阵列，以排序顺序访问i th元素。

这是可以接受的吗？

如果那也不方便，那么你最终会写你自己的排序;这不是非常痛苦，但需要一些照顾。

---

我花了一些时间适应现有的排序测试框架到这种情况。完整的代码非常大，因为它包含了很多测试支持代码。核心功能（比较，交换，分割和快速排序）的位置（122线，包括注释和空行）：

/* SO 20271977 - sort arrays x, y, z, w (type double, size n) in parallel based on values in x and y */ 

/* 
** To apply this to the real code, where there are 4 arrays to be sorted 
** in parallel, you might write: 
** 
** Array4 a; 
** a.x = x; 
** a.y = y; 
** a.z = z; 
** a.w = w; 
** a.n = n; 
** quicksort_random(&a); 
** 
** Or even: 
** 
** quicksort_random((Array4){ .n = n, .x = x, .y = y, .z = z, .w = w }); 
** 
** combining designated initializers and compound literals. Or you could write a 
** trivial wrapper so that you can call: 
** 
** quicksort_random_wrapper(n, x, y, z, w); 
*/ 

/* SOF so-20271977.h */ 
#include <stddef.h> 
typedef struct Array4 
{ 
    size_t n; 
    double *x; 
    double *y; 
    double *z; 
    double *w; 
} Array4; 

extern void quicksort_random(Array4 *A); 
/* EOF so-20271977.h */ 

#include <assert.h> 
#include <stdlib.h> /* lrand48() */ 

/* 
** Note that a more careful implementation would use nrand48() instead 
** of lrand48() to prevent its random number generation from interfering 
** with other uses of the x-rand48() functions. 
*/ 

typedef size_t (*Part)(Array4 *A, size_t p, size_t r); 

static void quicksort_partition(Array4 *A, size_t p, size_t r, Part partition); 
static size_t partition_random(Array4 *A, size_t p, size_t r); 

/* Quick Sort Wrapper function - specifying random partitioning */ 
void quicksort_random(Array4 *A) 
{ 
    quicksort_partition(A, 0, A->n - 1, partition_random); 
} 

/* Main Quick Sort function */ 
static void quicksort_partition(Array4 *A, size_t p, size_t r, Part partition) 
{ 
    if (p < r) 
    { 
     size_t q = (*partition)(A, p, r); 
     assert(p <= q && q <= r); 
     if (q > 0) 
      quicksort_partition(A, p, q-1, partition); 
     quicksort_partition(A, q+1, r, partition); 
    } 
} 

static inline int compare(Array4 const *A, size_t p, size_t r) 
{ 
    if (A->x[p] < A->x[r]) 
     return -1; 
    else if (A->x[p] > A->x[r]) 
     return +1; 
    if (A->y[p] < A->y[r]) 
     return -1; 
    else if (A->y[p] > A->y[r]) 
     return +1; 
    else 
     return 0; 
} 

static inline size_t random_int(size_t p, size_t r) 
{ 
    return(lrand48() % (r - p + 1) + p); 
} 

static inline void swap(Array4 *A, size_t i, size_t j) 
{ 
    double d; 
    d = A->x[i]; 
    A->x[i] = A->x[j]; 
    A->x[j] = d; 
    d = A->y[i]; 
    A->y[i] = A->y[j]; 
    A->y[j] = d; 
    d = A->z[i]; 
    A->z[i] = A->z[j]; 
    A->z[j] = d; 
    d = A->w[i]; 
    A->w[i] = A->w[j]; 
    A->w[j] = d; 
} 

static size_t partition_random(Array4 *A, size_t p, size_t r) 
{ 
    size_t pivot = random_int(p, r); 
    swap(A, pivot, r); 
    size_t i = p-1; 
    size_t j = p; 

    while (j <= r) 
    { 
     if (compare(A, j, r) <= 0) 
      swap(A, j, ++i); 
     j++; 
    } 
    return i; 
} 

测试框架（相当精细的离谱，如果不是，我已经有了一个变种它手头）是369线，包括空白行和注释行 - 及以上的所有的代码：

#include <assert.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <time.h> 

#define FLTFMT "%13.6f" 

typedef struct Array4 
{ 
    size_t n; 
    double *x; 
    double *y; 
    double *z; 
    double *w; 
} Array4; 

static int trace = 0; 

static void *xmalloc(size_t size) 
{ 
    void *space = malloc(size); 
    if (space == 0) 
    { 
     fprintf(stderr, "Out of memory (%zu)\n", size); 
     exit(1); 
    } 
    return space; 
} 

void quicksort_last(Array4 *A); 
void quicksort_random(Array4 *A); 
void selectionsort(Array4 *A); 

static inline int compare(Array4 const *A, size_t p, size_t r) 
{ 
    if (A->x[p] < A->x[r]) 
     return -1; 
    else if (A->x[p] > A->x[r]) 
     return +1; 
    if (A->y[p] < A->y[r]) 
     return -1; 
    else if (A->y[p] > A->y[r]) 
     return +1; 
    else 
     return 0; 
} 

static void dump_array(char const *tag, Array4 const *A) 
{ 
    printf("%s [%zu..%zu]:\n", tag, (size_t)0, A->n-1); 
    for (size_t i = 0; i < A->n; i++) 
     printf("(" FLTFMT ", " FLTFMT ", " FLTFMT ", " FLTFMT ")\n", 
       A->x[i], A->y[i], A->z[i], A->w[i]); 
} 

static void chk_sort(Array4 const *A) 
{ 
    for (size_t i = 0; i < A->n - 1; i++) 
    { 
     //if (compare(A, i, i+1) > 0) 
     { 
      if (A->x[i] > A->x[i+1]) 
      { 
       printf("Out of order: A.x[%zu] = " FLTFMT ", A.x[%zu] = " FLTFMT "\n", 
         i, A->x[i], i+1, A->x[i+1]); 
      } 
      else if ((A->x[i] == A->x[i+1] && A->y[i] > A->y[i+1])) 
      { 
       printf("Out of order: A.x[%zu] = " FLTFMT ", A.x[%zu] = " FLTFMT ", " 
         "A.y[%zu] = " FLTFMT ", A.y[%zu] = " FLTFMT "\n", 
         i, A->x[i], i+1, A->x[i+1], i, A->y[i], i+1, A->y[i+1]); 
      } 
     } 
    } 
} 

static inline void set(Array4 *A, size_t p, double d) 
{ 
    A->x[p] = d; 
    A->y[p] = d + drand48() - 0.5; 
    A->z[p] = d/2.0; 
    A->w[p] = d * 2.0; 
} 

static void load_random(Array4 *A) 
{ 
    size_t size = A->n; 
    for (size_t i = 0; i < size; i++) 
    { 
     A->x[i] = drand48() * size; 
     A->y[i] = drand48() * size + drand48() - 0.5; 
     A->z[i] = drand48() * size/2.0; 
     A->w[i] = drand48() * size * 2.0; 
    } 
} 

static void load_ascending(Array4 *A) 
{ 
    for (size_t i = 0; i < A->n; i++) 
     set(A, i, i); 
} 

static void load_descending(Array4 *A) 
{ 
    for (size_t i = 0; i < A->n; i++) 
     set(A, i, A->n - i); 
} 

static void load_uniform(Array4 *A) 
{ 
    for (size_t i = 0; i < A->n; i++) 
     set(A, i, A->n); 
} 

static void load_organpipe(Array4 *A) 
{ 
    for (size_t i = 0; i <= A->n/2; i++) 
     set(A, i, i); 
    for (size_t i = A->n/2 + 1; i < A->n; i++) 
     set(A, i, A->n - i); 
} 

static void load_invorganpipe(Array4 *A) 
{ 
    size_t range = A->n/2; 
    for (size_t i = 0; i < A->n/2; i++) 
     set(A, i, range - i); 
    for (size_t i = A->n/2 + 1; i < A->n; i++) 
     set(A, i, i - range); 
} 

typedef void (*Load)(Array4 *A); 
typedef void (*Sort)(Array4 *A); 
typedef size_t (*Part)(Array4 *A, size_t p, size_t r); 

static void test_one_sort(Array4 *A, Sort sort, char const *s_tag, 
          char const *l_tag, char const *z_tag) 
{ 
    if (trace) 
    { 
     printf("%s-%s-%s:", z_tag, l_tag, s_tag); 
     dump_array("Before", A); 
    } 
    clock_t start = clock(); 
    (*sort)(A); 
    clock_t finish = clock(); 
    double sec = (finish - start)/(double)CLOCKS_PER_SEC; 
    printf("%s-%s-%s: %13.6f\n", z_tag, l_tag, s_tag, sec); 
    chk_sort(A); 
    if (trace) 
    { 
     printf("%s-%s-%s:", z_tag, l_tag, s_tag); 
     dump_array("After", A); 
    } 
    fflush(stdout); 
} 

static Array4 *alloc_array(size_t size) 
{ 
    Array4 *A = xmalloc(sizeof(*A)); 
    A->n = size; 
    A->x = xmalloc(size * sizeof(A->x[0])); 
    A->y = xmalloc(size * sizeof(A->y[0])); 
    A->z = xmalloc(size * sizeof(A->z[0])); 
    A->w = xmalloc(size * sizeof(A->w[0])); 
    return A; 
} 

static Array4 *dup_array(Array4 *A) 
{ 
    size_t size = A->n; 
    Array4 *B = alloc_array(size); 
    if (B != 0) 
    { 
     B->n = size; 
     memmove(B->x, A->x, size * sizeof(A->x[0])); 
     memmove(B->y, A->y, size * sizeof(A->y[0])); 
     memmove(B->z, A->z, size * sizeof(A->z[0])); 
     memmove(B->w, A->w, size * sizeof(A->w[0])); 
    } 
    return B; 
} 

static void free_array(Array4 *A) 
{ 
    free(A->x); 
    free(A->y); 
    free(A->z); 
    free(A->w); 
    free(A); 
} 

static void test_set_sorts(Array4 *A, char const *l_tag, char const *z_tag) 
{ 
    struct sorter 
    { 
     Sort function; 
     char const *tag; 
    } sort[] = 
    { 
     { quicksort_last, "QS.L" }, 
     { quicksort_random, "QS.R" }, 
     { selectionsort, "SS.N" }, 
    }; 
    enum { NUM_SORTS = sizeof(sort)/sizeof(sort[0]) }; 
    for (int i = 0; i < NUM_SORTS; i++) 
    { 
     Array4 *B = dup_array(A); 
     test_one_sort(B, sort[i].function, sort[i].tag, l_tag, z_tag); 
     free(B); 
    } 
} 

static void test_set_loads(size_t size, char const *z_tag) 
{ 
    struct loader 
    { 
     Load function; 
     char const *tag; 
    } load[] = 
    { 
     { load_random, "R" }, 
     { load_ascending, "A" }, 
     { load_descending, "D" }, 
     { load_organpipe, "O" }, 
     { load_invorganpipe, "I" }, 
     { load_uniform, "U" }, 
    }; 
    enum { NUM_LOADS = sizeof(load)/sizeof(load[0]) }; 
    Array4 *A = alloc_array(size); 
    for (int i = 0; i < NUM_LOADS; i++) 
    { 
     load[i].function(A); 
     test_set_sorts(A, load[i].tag, z_tag); 
    } 
    free_array(A); 
} 

/* Main Quick Sort function */ 
static void quicksort_partition(Array4 *A, size_t p, size_t r, Part partition) 
{ 
    if (p < r) 
    { 
     size_t q = (*partition)(A, p, r); 
     assert(p <= q && q <= r); 
     if (q > 0) 
      quicksort_partition(A, p, q-1, partition); 
     quicksort_partition(A, q+1, r, partition); 
    } 
} 

static size_t partition_random(Array4 *A, size_t p, size_t r); 
static size_t partition_last(Array4 *A, size_t p, size_t r); 

/* Quick Sort Wrapper function - specifying random partitioning */ 
void quicksort_random(Array4 *A) 
{ 
    quicksort_partition(A, 0, A->n - 1, partition_random); 
} 

/* Quick Sort Wrapper function - specifying partitioning about last element */ 
void quicksort_last(Array4 *A) 
{ 
    quicksort_partition(A, 0, A->n - 1, partition_last); 
} 

static inline size_t random_int(size_t p, size_t r) 
{ 
    return(lrand48() % (r - p + 1) + p); 
} 

static inline void swap(Array4 *A, size_t i, size_t j) 
{ 
    double d; 
    d = A->x[i]; 
    A->x[i] = A->x[j]; 
    A->x[j] = d; 
    d = A->y[i]; 
    A->y[i] = A->y[j]; 
    A->y[j] = d; 
    d = A->z[i]; 
    A->z[i] = A->z[j]; 
    A->z[j] = d; 
    d = A->w[i]; 
    A->w[i] = A->w[j]; 
    A->w[j] = d; 
} 

static size_t partition_random(Array4 *A, size_t p, size_t r) 
{ 
    size_t pivot = random_int(p, r); 
    swap(A, pivot, r); 
    size_t i = p-1; 
    size_t j = p; 

    while (j <= r) 
    { 
     if (compare(A, j, r) <= 0) 
      swap(A, j, ++i); 
     j++; 
    } 
    return i; 
} 

static size_t partition_last(Array4 *A, size_t p, size_t r) 
{ 
    size_t i = p-1; 
    size_t j = p; 

    while (j <= r) 
    { 
     if (compare(A, j, r) <= 0) 
      swap(A, j, ++i); 
     j++; 
    } 
    return i; 
} 

/* Selection Sort algorithm */ 
void selectionsort(Array4 *A) 
{ 
    size_t r = A->n; 
    for (size_t p = 0; p < r; p++) 
    { 
     for (size_t i = p; i < r; i++) 
     { 
      if (compare(A, p, i) > 0) 
       swap(A, p, i); 
     } 
    } 
} 

/* 
** To apply this to the real code, where there are 4 arrays to be sorted 
** in parallel, you might write: 
** 
** Array4 a; 
** a.x = x; 
** a.y = y; 
** a.z = z; 
** a.w = w; 
** a.n = n; 
** quicksort_random(&a); 
** 
** Or even: 
** 
** quicksort_random((Array4){ .n = n, .x = x, .y = y, .z = z, .w = w }); 
** 
** combining designated initializers and compound literals. Or you could write a 
** trivial wrapper so that you can call: 
** 
** quicksort_random_wrapper(n, x, y, z, w); 
*/ 

int main(void) 
{ 
    srand48((long)time(0)); 

    for (size_t i = 10; i <= 40; i += 10) 
    { 
     char buffer[10]; 
     snprintf(buffer, sizeof(buffer), "%zuK", i); 
     test_set_loads(1000*i, buffer); 
    } 

    return 0; 
}