CODEWITHSUNDEEP
carrayssortingqsort
ComputerLocus
ComputerLocus

Reputation: 3618

Keeping two arrays in the same ordering when sorting

I have an integer array that I need to sort containing unix times. I was going to use qsort to sort it which is fairly trivial. However I also have an array of "strings" that needs to remain in the same order as the integer array.

So position 2 in the integer array would correspond with an element in position two of the other array.

Is there anyway using qsort to maintain such a relationship?

Upvotes: 0

Views: 124

Answers (2)

rcgldr
rcgldr

Reputation: 28826

A more generic solution that actually sorts 2 (or more) arrays, according to one of the arrays, by sorting an array of pointers to the key array, then reordering all of the arrays to sort them (it also restores the array of pointers back to their initial state). The compare function only needs to know the type that the pointers point to. The reorder in place takes O(n) (linear) time as every move places a value in it's final sorted location. In this example, a[] is an array of integers, b[] is an array of pointers to strings (char *).

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 *pa = malloc(...);   /* array of pointers */
    int ta;    /* temp value for a */
    char *tb;  /* temp value for b */
    /* ... */

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

Upvotes: 1

Iharob Al Asimi
Iharob Al Asimi

Reputation: 53006

Do it like this

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

struct Data
{
    long int time;
    const char *string;
};

int
datacmp(const void *const x, const void *const y)
{
    return ((struct Data *) x)->time - ((struct Data *) y)->time;
}

int
main(void)
{
    struct Data array[] = {
        {1234, "1234 Text"},
        {1034, "1034 Text"},
        {1041, "1041 Text"}
    };
    size_t count;

    count = sizeof(array) / sizeof(array[0]);
    for (size_t i = 0 ; i < count ; ++i)
    {
        fprintf(stderr, "Entry %zu:\n\ttime  : %ld\n\tstring: %s\n\n", 
            i, array[i].time, array[i].string);
    }

    fprintf(stderr, "\n");
    qsort(array, count, sizeof(array[0]), datacmp);
    fprintf(stderr, "---- Sorted array:\n");

    for (size_t i = 0 ; i < count ; ++i)
    {
        fprintf(stderr, "Entry %zu:\n\ttime  : %ld\n\tstring: %s\n\n", 
            i, array[i].time, array[i].string);
    }

    return 0;
}

Upvotes: 1

Related Questions