CODEWITHSUNDEEP
carrayssortingpointers
Elyviere
Elyviere

Reputation: 73

C - Sort two arrays the same way

So I have two arrays (pointers actually), lets call them a and b. I want to first sort a, then save the exact swaps I did to get that sorted array and apply them to my vector b. Here's a short example of what I mean:

int *a, *b;
//appropriate mallocs
a[0] = 2; a[1] = 3; a[2] = 1;
b[0] = 4; b[1] = 2; b[2] = 3;
//sort a in decreasing order --> a==[3, 2, 1]
//sort b based on sorting of a --> b==[2, 4, 3]

How I could achieve this without writing my own sort function?

Upvotes: 4

Views: 6256

Answers (4)

rcgldr
rcgldr

Reputation: 28921

This example does what the original question asked for, it sorts two (or more) arrays the same way, without having to combine the array elements into a common structure.

It uses an array of pointers, so the compare function does not need to know which array it is sorting, only the type of the elements being sorted. It could be modified to sort multiple arrays according to one of the arrays.

It creates an array of pointers to a[], uses qsort() to sort the array of pointers according to a[], then uses the sorted pointers to reorder both a[] and b[] in place (with the side effect that the sorted pointers are restored to their initial state).

The reordering time complexity is O(n) as each store places an element in its sorted position.

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

int compare(const void *pp0, const void *pp1)
{
    int i0 = **(int **)pp0;
    int i1 = **(int **)pp1;
    if(i0 > i1)return -1;
    if(i0 < i1)return  1;
    return 0;
}

int main()
{
    int a[3] = {2, 3, 1};
    int b[3] = {4, 3, 2};
    int *pa[3];
    size_t i, j, k;
    int ta, tb;

    /* create array of pointers to a[] */
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        pa[i] = &a[i];

    /* sort array of pointers */
    qsort(pa, sizeof(a)/sizeof(a[0]), sizeof(pa[0]), compare);

    /* reorder a[] and b[] according to the array of pointers */
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++){
        if(i != pa[i]-a){
            ta = a[i];
            tb = b[i];
            k = i;
            while(i != (j = pa[k]-a)){
                a[k] = a[j];
                b[k] = b[j];
                pa[k] = &a[k];
                k = j;
            }
            a[k] = ta;
            b[k] = tb;
            pa[k] = &a[k];
        }
    }

    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        printf("%2d ", a[i]);
    printf("\n");

    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        printf("%2d ", b[i]);
    printf("\n");

    return 0;
}

Upvotes: 10

milevyo
milevyo

Reputation: 2184

// i am going to submit the idea not the code.

    int *a,*b;
    int *ord; // an array that holds indexes (sorting orders)

//...

    a[ord[0]] = 2; a[ord[1]] = 3; a[ord[2]] = 1;
    b[ord[0]] = 4; b[ord[1]] = 2; b[ord[2]] = 3;

//...
//now you have just to sort the indexes array ord

Upvotes: 0

mksteve
mksteve

Reputation: 13085

This is not solvable as requested, the sort functions don't expose the swaps they perform.

However, it seems that the result could be achieved with a struct.

struct combined {
   int a_;
   int b_;
};

Where the qsort function tests the a_ element, but also sorts the b_ data. Again, this requires a comparison function

 int compare( const void * l, const void * r )
 {
     struct combined * _l= (struct combined *)l;
     struct combined * _r= (struct combined *)r;
     if( _l->a_ > _r->a_ ) return -1; // reverse sort
     if( _l->a_ < _r->a_ ) return 1;
     return 0;
 }

finally 

 struct combined array[] = { {2,4}, {3,2}, {1,3} };
 qsort( array, 3, sizeof( struct combined), compare );

 array => { {3,2}, {2,4}, {1,3} };

Upvotes: 1

unwind
unwind

Reputation: 400029

The better solution is to group the data into an array of structures, then sort that based on the desired key (i.e. the a values):

struct my_data {
  int a;
  int b;
};

struct my_data data[100];

static int data_cmp(const void *a, const void *b)
{
  const struct my_data *da = a, *db = b;

  return da->a < db->a ? -1 : da->a > db->a;
}

qsort(data, sizeof data / sizeof *data, sizeof *data, data_cmp);

This uses qsort() to sort, which is typically highly desirable.

Upvotes: 6

Related Questions