CODEWITHSUNDEEP
carrayssortingmalloc
john
john

Reputation: 139

How do I sort two arrays without altering the original ones or mallocing new ones?

To make things simple, here's an example of what I want to do:

Say we have two arrays, A and B;

A = [5, 5, 5, 9, 1]

B = [9, 5, 1, 4, 4]

In the program, there are hundreds of these small arrays. I'm trying to sort them based on their maximum values. So in this case, they both have 9's, so go to the next biggest number. Okay, they both have fives, next number. The A array has a 5, and the B array has a 4, so the A array would be sorted first. The problem here is that I don't know how to sort these guys without mallocing a new array to sort these values.

Here's what I got:

int compare(const void *x, const void *y)
{
struct Data *s1, *s2;
s1 = (struct Data *)x;
s2 = (struct Data *)y;

int maxv=-1000;
int maxv2=-1000;
int maxvn=1000;
int maxv2n=1000;


int j=0;
int k=0;

for (k=0; k < 5;k++)
{
max = -1000;
max2= -1000;
    for (j=0; j<5;j++)
    {
        if (s1->margin[j]>max && s1->margin[j]<maxvn)
            maxv=s1->margin[j];
        if (s2->margin[j]>max2 && s2->margin[j]<maxv2n)
            maxv2=s2->margin[j];
    }
if (max2<max)
    return 1;
if (max<max2)
    return -1;

maxvn=maxv;
maxv2n=maxv2;
}
return 0;
}

So, in theory, I want array A to be listed before array B. Unfortunately, array B is being listed before array A because of (i think) the second condition in this argument:

if (s1->margin[j]>max && s1->margin[j]<maxvn)

The other two 5's in the array A are being ignored because of the second argument.

Now, I have no idea how to actually fix this problem unless I just malloc some arrays and then bubble sort them. This though slows my program down. Can anyone here think of a fix that I can implement that would prevent me from using any sort of mallocs and doesn't overlook recurring numbers?

Thanks.

Upvotes: 0

Views: 108

Answers (3)

John Bollinger
John Bollinger

Reputation: 181159

There are at least two possible approaches. The more general is to declare work arrays on the stack, copy the originals into these work arrays, sort them, and then compare them. This avoids the expense and complexity of malloc() and gains you simple(-ish) element comparisons. It still uses auxilliary space. Example:

int compare(const void *x, const void *y)
{
    struct Data *s1 = (struct Data *) x;
    struct Data *s2 = (struct Data *) y;
    int temp1[5];  /* or replace `int` with the correct type */
    int temp2[5];  /* or replace `int` with the correct type */
    int i;

    memcpy(temp1, s1->margin, sizeof(temp1));
    memcpy(temp2, s2->margin, sizeof(temp2));

    /* ... sort temp1 and temp2 however you want ... */

    /* compare */
    for (i = 0; i < 5; i += 1) {
        if (temp1[i] < temp2[i]) return -1;
        if (temp1[i] > temp2[i]) return  1;
    }

    return 0;
}

Alternatively, if the array elements have small enough bounds then you can compute a key value for each and compare them. This particular one works if the array elements are all certain to be between 0 and 20, inclusive:

int compare(const void *x, const void *y)
{
    struct Data *s1 = (struct Data *) x;
    struct Data *s2 = (struct Data *) y;
    uint64_t key1 = 0;
    uint64_t key2 = 0;
    int i;

    for (i = 0; i < 5; i += 1) {
        key1 += 1 << (s1->margin[i] * 3);
        key2 += 1 << (s2->margin[i] * 3);
    }

    if (key1 < key2) return -1;
    if (key1 > key2) return  1;
    return 0;
}

That treats the keys as arrays of 3-bit elements, and accumulates in each element the number of times that element's index appears in the corresponding original array. The resulting 64-bit values can be compared via ordinary integer comparison operators.

If the elements of your original array are bounded between 0 and 9 then 32-bit keys would be sufficient for this second approach.

Updated to add:

Note, too, that if you have a large number of these arrays to sort then it would be greatly to your advantage to minimize the cost of your comparisons. The computed-key approach has the advantage that you could compute a key for each array just once, store it somewhere, and then have very fast comparisons for the rest of the sort. Any type of temp array or multi-loop approach within the individual comparisons will be very rough on your performance (and even re-computing the keys each time, though not terrible, is also not great).

Upvotes: 3

Sasha Pachev
Sasha Pachev

Reputation: 5336

First, sort all of the small arrays (either with qsort(), or if they are very small, your own bubble or insertion sort might be faster) to make the comparison easier. This will make your compare function smaller. Then simplify your compare() function (now it only needs to make one simultaneous pass through both arrays), and use qsort() on the array of arrays passing it your new compare() function.

Upvotes: -1

JJF
JJF

Reputation: 2777

You could allocate one additional element in each array and store in that element the largest value contained in the array. Then whenever the array is updated the code that does the update could keep the max value slot if needed. You'd always have the array's highest value in say slot 0 (or slot 5 for instance if the arrays always contained 5 elements).

It's the classic speed vs size trade off in performance. One additional element's RAM footprint per array plus time to keep max element updates vs. complexity of sorting arrays or scanning through them serially.

Upvotes: 0

Related Questions