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

Answer 1

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