數組排序使用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; 
}