3

I'm not C expert and I've read through the forum, but I still need some advice regarding a sorting problem on C.

I have 4 dynamic arrays of doubles in C. All of them are the same size, and lets say n. What I want to do is to sort all of them using one of the arrays as first order and a second array as my second order. So if the arrays are *x, *y, *w and *z. I want to sort them according to the values of *x, then *y.

I must do this efficiently because the arrays are quite large.

Any help will be much appreciated.

Improve this question
11
  • stackoverflow.com/questions/1787996/… Commented Nov 28, 2013 at 17:43
  • The question is how to sort array? Or you know how to sort one array? Commented Nov 28, 2013 at 17:44
  • 2
    Here: qsort. Try something, and if you have a problem then, then we'll talk. About sorting large arrays, see: stackoverflow.com/questions/5588041/… Commented Nov 28, 2013 at 17:44
  • 1
    @user20679 you don't actually ask specific question. This is not appreciated here. For your case: take any decent open source quick sort implementation (or some other algorithm). Then find a part where they swap elements. So in that place instead of swapping of original array, swap elements of other arrays with according index. Commented Nov 28, 2013 at 18:28
  • 1
    @Andrey: The question is perfectly clear; each of x[i], y[i], w[i], and z[i] represent a record, and he wants to sort each record by x and y. This would be dead easy if he had a struct to represent the four quantities, but he doesn't. Commented Nov 28, 2013 at 18:37

3 Answers 3

Reset to default
2

The easy way to do this would be to map your four separate arrays onto a single array of a struct type like

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];
}

and then create a comparison function to pass to 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;
}

Now you can use the qsort library function to sort that array of struct:

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

Once that array is sorted, you can map the results back onto your four original arrays.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

OP said : I'm aware that this is not the best approach to handle the data but a cant change it.
@Artur I'm sure it can temporarily be changed.
Would look nicer is comparing func had conditions looking this way: if ( l->x < r->x ) return -1; if ( l->x > r->x ) return 1; if ( l->y < r->y ) return -1; if ( l->y > r->y ) return 1; return 0;
1

Clearly, sorting this using standard qsort() is not going to work; there isn't a mechanism for passing four arrays.

Equally clearly, if the data were structured as an array of structures, then using qsort() would be feasible.

Question 1: Is it feasible to create an array of structures, load it, sort it, and then unload back into the original arrays?

Question 2: Another option is to sort an array of integers:

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

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

The comparator function would have to be able to access the x and y arrays as file scope variables:

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;
}

You'd then be able to access the arrays using x[indexes[i]] etc to access the ith element in sorted order.

Is that acceptable?

If that is not convenient either, then you will end up writing your own sort; it isn't horribly painful, but will require some care.

I spent some time adapting an existing sort test framework to this scenario. The full code is quite large because it includes a lot of testing support code. The core function (compare, swap, partition and quicksort) are here (122 lines, including comment and blank lines):

/* 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;
}

The test framework (quite ridiculously elaborate if it weren't that I already had a variant of it on hand) is 369 lines including blank lines and comment lines — and all the code above:

#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;
}
Improve this answer

Comments

1

If you can't use qsort with 

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

Use qsort with

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

Create an array of size n, fill x with x values, i with index. Call qsort. At the end, i will store the permutation order. Swap the three other arrays according to the permutation order. Then do the same with little arrays ("with same x") in the y direction.

If this ugly trick is not possible, then I don't see any other solution than reinventing the wheel.

(edit : I have just seen Andrew said something very close to this answer...sorry!) Bye,

Francis

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.