Многопользовательская сортировка в C

Question

Я хочу отсортировать несколько массивов одним из этих массивов с помощью quicksort. Для тестирования я использую следующие данные:

x y  z 
j 106.0 106 
s 115.0 115 
h 104.0 104 
g 103.0 103 
l 108.0 108 

---

Я уже построил функцию QuickSort для одного массива, который принимает uint32_t data_type значения, определяющего тип данных массива для сортировки. В этом частном случае сортировочной все массивы можно сделать с помощью:

char x[5] = { 'j', 's', 'h', 'g', 'l' }; 
double y[5] = { 106.0, 115.0, 104.0, 103.0, 108.0 }; 
uint64_t z[5] = { 106, 115, 104, 103, 108 }; 
QuickSort(5, x, CHAR_NR); 
QuickSort(5, y, DOUBLE_NR); 
QuickSort(5, z, UINT64_NR); 

QuickSort выглядит следующим образом:

void QuickSort(uint64_t arrlen, void *arr, uint32_t data_type) 

Он использует переключатель на data_type и вызывает функцию так:

static inline void quicksort_c(uint64_t arrlen, char *arr) 
{ 
    if (arrlen < UINT64_C(2)) { return; } 
    char p = arr[arrlen/UINT64_C(2)]; 
    char t; 
    uint64_t i, j; 
    for (i = UINT64_C(0), j = (arrlen - UINT64_C(1));; i++, j--) { 
     while (arr[i] < p) { i++; } 
     while (p < arr[j]) { j--; } 
     if (i >= j) { break; } 

     t = arr[i]; 
     arr[i] = arr[j]; 
     arr[j] = t; 
    } 
    quicksort_c(i, arr); 
    quicksort_c(arrlen - i, arr + i); 
    return; 
} 

---

Теперь я хочу, чтобы одна функция могла сортировать все массивы для случаев, когда они не иметь порядок после сортировки по одному из массивов. Я придерживаюсь аналогичного подхода, используя переключатель на data_type массива сортировки и конкретные функции для разных типов. Вместо того, чтобы непосредственно поменяв два значения это Кальесы функции, которая перебирает все значения массивов и свопов:

char x[5] = { 'j', 's', 'h', 'g', 'l' }; 
double y[5] = { 106.0, 115.0, 104.0, 103.0, 108.0 }; 
uint64_t z[5] = { 106, 115, 104, 103, 108 }; 

uint32_t data_types[3] = { CHAR_NR, DOUBLE_NR, UINT64_NR }; 
void *arrs[3] = { x, y, z}; 
QuickSort_Multi(3, arrs, 5, data_types, 0, status); 

... 

static inline void quicksort_multi_c(uint64_t arrslen, void **arrs, 
    uint64_t arrlen, char *arr, uint32_t *data_types) 
{ 
    if (arrlen < UINT64_C(2)) { return; } 
    char p = arr[arrlen/UINT64_C(2)]; 
    //char t; 
    uint64_t i, j; 
    for (i = UINT64_C(0), j = (arrlen - UINT64_C(1));; i++, j--) { 
     while (arr[i] < p) { i++; } 
     while (p < arr[j]) { j--; } 
     if (i >= j) { break; } 
     quicksort_multi_swap(arrslen, arrs, data_types, i, j); 
    } 
    quicksort_multi_c(arrslen, arrs, i, arr, data_types); 
    quicksort_multi_c(arrslen, arrs, arrlen - i, arr + i, data_types); 
    return; 
} 

static inline void quicksort_multi_swap(uint64_t arrslen, void **arrs, 
    uint32_t *data_types, uint64_t i, uint64_t j) 
{ 
    char  buffer_c; 
    uint64_t buffer_u64; 
    double  buffer_double; 
    char  *buffer_c_arr; 
    uint64_t *buffer_u64_arr; 
    double  *buffer_double_arr; 

    uint64_t u64a; 
    void *arr; 
    for (u64a = UINT64_C(0); u64a < arrslen; u64a++) { 
     arr = arrs[u64a]; 
     switch (data_types[u64a]) { 
      case CHAR_NR: 
       buffer_c_arr = arr; 
       buffer_c = buffer_c_arr[i]; 
       buffer_c_arr[i] = buffer_c_arr[j]; 
       buffer_c_arr[j] = buffer_c; 
       break; 
      case UINT64_NR: 
       buffer_u64_arr = arr; 
       buffer_u64 = buffer_u64_arr[i]; 
       buffer_u64_arr[i] = buffer_u64_arr[j]; 
       buffer_u64_arr[j] = buffer_u64; 
       break; 
      case DOUBLE_NR: 
       buffer_double_arr = arr; 
       buffer_double = buffer_double_arr[i]; 
       buffer_double_arr[i] = buffer_double_arr[j]; 
       buffer_double_arr[j] = buffer_double; 
       break; 
      default: break; 
     } 
    } 
} 

---

Обратите внимание, я не изменил сам алгоритм быстрой сортировки. Я просто изменил функцию свопинга. Странно с приведенными выше массивами образцов я не получаю никаких предупреждений компилятора, но при выполнении примера создается segmentation fault. С другой стороны, он работает с char x[5] = { 'a', 'b', 'h', 'g', 'l' };.

Любые идеи, как решить эту проблему?

Answer 1

Вы можете сделать так:

struct elem { 
    char  x; 
    double y; 
    uint64_t z; 
}; 

struct elem array[] = { 
    { 'j', 106.0, 106 }, 
    { 's', 115.0, 115 }, 
    { 'h', 104.0, 104 }, 
    { 'g', 103.0, 103 }, 
    { 'l', 108.0, 108 } 
}; 

int cmp(const void *a, const void *b) 
{ 
... 
} 

qsort(array, (sizeof array)/(sizeof *array), (sizeof *array), cmp); 

qsort из <stdlib.h>

EDIT

Или так:

struct arrays { 
    char const *xs; 
    double const *ys; 
    uint64_t const *zs; 
}; 

char x[5] = { ... }; 
double y[5] = { ... }; 
uint64_t z[5] = { ... }; 
unsigned i[5] = { 0, 1, 2, 3, 4 }; 
struct arrays arrs = { x, y, z }; 
... 
/* NOTE: This isn't portable */ 
int cmp(void *arrays, const void *a, const void *b) 
{ 
    ... 
} 
... 
qsort_r(i, 5, sizeof *i, &arrs, cmp); 

edit2

Другой вариант:

struct elem { 
    char  x; 
    double y; 
    uint64_t z; 
}; 

struct elem elems[] = { 
    { 'j', 106.0, 106 }, 
    { 's', 115.0, 115 }, 
    { 'h', 104.0, 104 }, 
    { 'g', 103.0, 103 }, 
    { 'l', 108.0, 108 } 
}; 
struct elem *array[] = { 
    elems + 0, elems + 1, elems + 2, elems + 3, elems + 4 
}; 

int cmp(const void *a, const void *b) 
{ 
    struct elem const **ap = a, **bp = b; 
... 
} 

qsort(array, (sizeof array)/(sizeof *array), (sizeof *array), cmp);