c++ - How can I quicksort a two dimension array by a specific cell?

Question

I have got a 2d array and I would like to quicksort it with the given qsort() function in C++:

unsigned work[N][3];

I would like to sort the "work" array by the third index... so if work[i] goes before work[j] if work[i][2]>work[j][2].

I know I would need to use a function to compare it, but I have no inkling how to do that.

edit: If I would do the following, would that help:

unsigned work[3][N];
qsort(work[2], N, sizeof(unsigned), compare);

And compare would be the following:

int compare(const void* a, const void* b)
{
    return(*(unsigned*)a-*(unsigned*)b);
}

?

Answer 1

Well, the short answer would be to not use std::qsort at all, but std::sort. But unfortunately the latter won't work, since unsigned int[3] is not assignable. So here's the easiest std::qsort solution.

First we define a custom comparator function:

// return -1 if a before b, 1 if after, 0 if equal
int compare(const void *a, const void *b)
{
    const unsigned int *arg1 = reinterpret_cast<const unsigned int*>(a);
    const unsigned int *arg2 = reinterpret_cast<const unsigned int*>(b);
    if(arg1[2] > arg2[2])
        return -1;
    if(arg1[2] < arg2[2])
        return 1;
    return 0;
}

Which we then use to sort the array. Keep in mind that work is an array of arrays, and thus work[0] is an array of 3 unsigned ints, there's no pointer indirection involved in any way. So it's perfectly suited for being sorted by std::qsort:

std::qsort(work, sizeof(work)/sizeof(work[0]), sizeof(work[0]), compare);

By the way, the third element is indexed with 2, since we usually start to count at 0 in C++ (and many other programming languages).

EDIT: Though, the best solution would indeed be to drop this array of arrays and use something more suited to C++, like a std::vector of std::array<unsigned int,3>s (or any other datastructure that fits a bit more to the actual context):

typedef std::array<unsigned int,3> uint3;
std::vector<uint3> work(N);

Which can then be sorted with a simple:

std::sort(std::begin(work), std::end(work), 
          [](const uint3 &a, const uint3 &b) { return a[2] > b[2]; });

Or, if you don't have C++11 (though in this case you won't have std::array either and need to start thinking about a resonable datastructure apart from a mere 3-array):

struct compare
{
    bool operator()(const uint3 &a, const uint3 &b) const
    {
        return a[2] > b[2];
    }
};

std::sort(work.begin(), work.end(), compare());

As a bonus to much clearer code, you also most probably get a slight performance boost of std::sort over std::qsort.

Answer 2

Yes, you can qsort() this. qsort() works by taking a required linear block of "stuff", partitioning it into uniform sized chunks where you specify the size (in bytes), and feeding you the base address of each block partition for comparison.

First, determine the size you need. It should be obvious the "things" you're sorting are array rows three elements wide. Second, write a comparator that can accept the base address of two such things as pointers, in our case, a simple pointer will work, as it nicely peels off the outer array dimension. Finally, the actually comparison will be three elements deep (p[2] to be precise) off each pointer p we're given:

So lets flesh the code:

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

static const size_t ROWSIZE = 3;

static void print_array(int rows, int ar[rows][ROWSIZE])
{
    int i,j;
    for (i=0;i<rows;++i)
    {
        for (j=0; j<ROWSIZE; printf("%d ", ar[i][j++]));
        printf("\n");
    }
    printf("\n");
}

// compare function
static int compare_row(const void* left, const void* right)
{
    const int *ileft = left, *iright = right;
    return ileft[ROWSIZE-1] - iright[ROWSIZE-1];
}

int main()
{
    int ar[10][ROWSIZE] = {0}, i;

    // fill with random junk from 10 to 99
    srand((unsigned)time(0));

    for (i=0;i<ROWSIZE * sizeof(ar)/sizeof(ar[0]); ++i)
        ar[i/ROWSIZE][i%ROWSIZE] = 10 + (rand() % 90);

    // print prior to sort.
    print_array(sizeof(ar)/sizeof(ar[0]), ar);

    // send to qsort
    qsort(ar, sizeof(ar)/sizeof(ar[0]), sizeof(ar[0]), compare_row);

    // print again after sort.
    print_array(sizeof(ar)/sizeof(ar[0]), ar);

    return EXIT_SUCCESS;
}

Sample Output

50 14 23 
69 81 93 
30 72 18 
26 49 29 
51 87 58 
18 74 40 
26 61 26 
43 80 27 
27 61 34 
13 66 89 

30 72 18 
50 14 23 
26 61 26 
43 80 27 
26 49 29 
27 61 34 
18 74 40 
51 87 58 
13 66 89 
69 81 93