Qsorting a multidimensional array

Question

I am currently working on an algorithm, that requires my multidimensional array (currently 3-dimensional) to be sorted by value of sum of first and second item. Specifically:

(condition for item i and j to be swapped)

if ((Array[i][1]+Array[i][2]) > (Array[j][1]+Array[j][2])) return 1;

I have decided, for test purposes, to use select sort. However, my algorithm is required to do all its magic in under 5 seconds. Select sort needs for itself around 10 seconds to sort such array, if it has around 200 000 items.

I have decided to use a better algorithm, since I'm pretty confident in rest of my program. I am aware that unix systems contain a built-in quicksort function, qsort (available through man qsort in terminal). However, I do not know how to implement it.

My idea was to create another array, one dimensional (1D), with same length, containing indexes of items in main array. Through that, I might be able to sort only the secondary 1D array, where first item will have index of item in main array with smallest sum, second will have the second smallest, and so on.

However, how can I do it? Qsort function needs to be provided with comparing function, to decide whether to swap, or not. If I did make my own comparing function (like the one I stated in begin of my question), how can I address with something like (Array[SeconArray[i]][0]), when main Array is only specified in main of the function, and therefore cannot be accessed through another function in same file?

I'll be glad for any tips or tricks how to solve this. I'm also not keen on using qsort. If you think that another sorting algorithm can do better, please, let me know.

Thanks a lot

Why not transform your 3D vector to a n*2 vector? smallVector[n][0] is the index in the 3D vector as you've explained and smallVector[n][1] is the key you need to sort by. — Lord Zsolt
– Lord Zsolt, Commented Nov 14, 2013 at 8:40
I'm not clear on your exact requirements Can you post a formal declaration of your 3D array, a small sample of row data (say a 3x3x3 sample, and an exact expectation of output (i.e. the logic of your comparator ideology and what you expect your cube to look when finished? (and just so I'm clear, Array[0][], the real "first" item row, is not used in computation?) — WhozCraig
– WhozCraig, Commented Nov 14, 2013 at 8:47
I can. The point of this program is to fill empty tanks with water, provided you know measures of each tank. I'm saving base area of each tank in first item, height of tank in second, and altitude in third. I need to sort these by altitude, in which each tank ends, which is height+altitude, therefore Array[i][1]+Array[i][2]. P.S.: indexing starts at 0, so first item has index 0, second 1 etc. — Michal Kučera
– Michal Kučera, Commented Nov 14, 2013 at 8:50
Ok. so far I only see 2D. I trust if this is truly 3D I'll see it in your updated post. qsort should be able to do this for you (at least i think so based on what i'm seeing in your description). The trick is getting the item width correct so the item addresses land on the right spots in your array when data is being shuffled about by qsort. — WhozCraig
– WhozCraig, Commented Nov 14, 2013 at 8:51
You were right. I failed to realize, that this really actually is only 2D array. — Michal Kučera
– Michal Kučera, Commented Nov 15, 2013 at 16:45

WhozCraig · Accepted Answer · 2013-11-14 09:27:39Z

I've only a limited amount of time to post this, but hopefully the idea is clear. This is one way qsort can be setup to do what you're looking for. This is a 2D array Nx3 that I've populated with random values from [0.0,500). The idea can be extended to a 3D and beyond array.

The trick is to get the row width correct (or in the case of 3D the slab, 4D the cube, etc...)

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

int cmp_row(const void* arg1, const void* arg2)
{
    const double *ar1 = arg1;
    const double *ar2 = arg2;

    double diff = (ar1[1] + ar1[2] - ar2[1] - ar2[2]);
    return (diff < 0.0) ? -1 : (0.0 < diff);
}

int main(int argc, char *argv[])
{
    static const int N = 50;
    double (*ar)[3] = NULL;
    int i=0;

    // see prng
    srand((unsigned)time(NULL));

    // allocat space for Nx3 2D array.
    ar = calloc(N, sizeof(*ar));

    // since I've no test data, random fill with values
    //  from [0..500)
    for (i=0;i<N;++i)
    {
        ar[i][1] = ((double)rand()/(double)RAND_MAX)*500.0;
        ar[i][2] = ((double)rand()/(double)RAND_MAX)*500.0;
    }

    // sort by elements 1+2
    qsort(ar, N, sizeof(*ar), cmp_row);

    for (i=0;i<N;++i)
    {
        printf("%3d : %7.3f + %7.3f  = %7.3f\n",
               i+1, ar[i][1], ar[i][2], ar[i][1]+ar[i][2]);
    }

    // release allocation
    free(ar);

    return 0;
}

Note: This gets a little more complex when dealing with what I called the syntax-only 2D+ arrays. Those would me the "arrays" that are actually vectors of pointers. int **ar etc. The premise is nearly the same, however, and only the comparator would have to change. If I've the time I'll add such a beast as an additional sample if input warrants it.

Final Note: This does not protect from potential overflow or underflow of the floating point values. a considerably more complex boolean-logic-only comparator can do that, but unless your data is uber-sensitive to such extremes, its hardly worth it for this example.

Output (obviously your's will vary)

I've included the summation of ar[i][1] + ar[i][2] as evidence of the sorting order doing what I believe you want. I hope this helps.

  1 :  47.986 +   1.471  =  49.457
  2 : 114.418 +  26.848  = 141.267
  3 : 148.183 +  12.145  = 160.328
  4 :  46.925 + 161.231  = 208.155
  5 : 102.405 + 116.097  = 218.502
  6 :  58.676 + 172.490  = 231.167
  7 : 144.797 +  99.977  = 244.774
  8 :   8.914 + 314.920  = 323.833
  9 :  68.885 + 255.924  = 324.809
 10 : 107.825 + 220.631  = 328.457
 11 : 287.056 +  44.610  = 331.665
 12 : 217.505 + 114.799  = 332.304
 13 : 240.620 + 104.506  = 345.127
 14 : 242.288 + 133.509  = 375.797
 15 : 381.538 +   4.073  = 385.611
 16 :   4.991 + 383.519  = 388.510
 17 : 257.611 + 163.872  = 421.483
 18 :  43.278 + 380.951  = 424.230
 19 : 300.775 + 129.879  = 430.654
 20 : 134.814 + 314.688  = 449.502
 21 : 103.281 + 346.874  = 450.155
 22 : 197.761 + 263.668  = 461.429
 23 : 303.872 + 173.430  = 477.302
 24 : 466.265 +  11.400  = 477.665
 25 : 108.817 + 391.995  = 500.812
 26 : 467.992 +  40.985  = 508.977
 27 : 353.493 + 160.398  = 513.891
 28 : 406.446 + 130.214  = 536.659
 29 : 244.678 + 303.989  = 548.667
 30 : 303.282 + 260.434  = 563.716
 31 : 254.139 + 317.150  = 571.290
 32 : 368.311 + 203.118  = 571.429
 33 : 372.654 + 201.597  = 574.251
 34 : 143.985 + 454.796  = 598.781
 35 : 254.561 + 402.038  = 656.598
 36 : 309.922 + 363.872  = 673.795
 37 : 196.554 + 478.447  = 675.000
 38 : 493.585 + 185.749  = 679.334
 39 : 438.196 + 257.858  = 696.054
 40 : 347.198 + 360.908  = 708.107
 41 : 262.210 + 456.034  = 718.244
 42 : 389.174 + 339.315  = 728.489
 43 : 300.199 + 446.422  = 746.621
 44 : 344.346 + 427.167  = 771.513
 45 : 317.604 + 470.313  = 787.917
 46 : 312.785 + 475.855  = 788.640
 47 : 334.682 + 492.928  = 827.609
 48 : 399.056 + 430.449  = 829.505
 49 : 460.128 + 373.025  = 833.154
 50 : 419.137 + 440.745  = 859.882

Collectives™ on Stack Overflow

Qsorting a multidimensional array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related