Quickly sorting an array of objects based on their known resemblance to each other using C

Question

I have a randomly ordered C array of integer numbers.

Each of these numbers represents a color, and has its relationship to every other number in the array defined elsewhere (they are non-linear, and are based on both the brightness of the color and the hue).

I need a quick, efficient algorithm to sort these numbers based on their resemblance to each other. The sorting is either so that the the numbers in the array cluster based on resemblance, or the opposite, i.e. in such a way that numbers that resemble each other are as far from each other as possible.

What's the best way to do this?

Answer 1

PMG is right in his comment. Based on what you've said, there's no reason to not use a quicksort with a customer comparison function. See the link that PMG posted in his comment for more information, and make sure your comparison function (which is int (*compar)(const void *, const void *)) do the magic for you.

Answer 2

One way would be to begin by picking an object, then search the remaining objects using your metric function to find the closest one/most distant one. Repeat this for each object you add to the output list. The algorithm is O(n^2) which isn't too bad.

Answer 3

You could try convert your colour from HSL colour space (I presume you use it, since you mentioned hue and lightness) to CIELAB. In CIELAB colour space you can quite easily calculate resemblence of colours, as human eye perceive it. With that distance calculated, you could sort your colours.

Answer 4

First, I'm assuming that you are going to use the qsort or similar function to do your sorting, and need a comparison function to pass to that. These comparison functions behave like memcnp and strcmp -- returning an integer to signify less than, equal to, or greater than.

One way to do this is by treating the entire color value as one big number as far as the comparison goes:

int bright_hue_compare(const void * a, const void * b) {
    int rc = bright_compare(a, b);
    if (!rc) {
        rc = hue_compare(a, b);
    }
    return rc;
}

This would group colors first by their brightness (assuming that you write a brightness compare function) and second by their hue. You may want to swap the order of these, and internally they can be more complicated.

Sorting such that similar colors are further from each other is more complicated, since you really need to compare it to several values possible neighbor values at a time to space them out further. I doubt that you could get this reliably with quicksort (the stdlib qsort function may not be quicksort, but assuming that it is), though:

int bright_hue_inverse_compare(const void * a, const void * b) {
    int rc = bright_hue_compare(a, b);
    if (rc) {
       return 0;
    }
    return random(); // so that they are the same so randomize greater/lesser
}

Might be good enough for you, but yields far from optimal results.

Really you would probably have to write your own sorting function for this, and it will probably be have a very high run time because each color needs to be compared against many of its neighbors. The more optimal you want this distribution the more this starts to look like an AI problem where each color wants to move as far away from like colors as it can.

Oh, something that I just thought of that might yield good results would be if averaged all of the hues and all of the brightnesses and then divided the array in half and tried to make each sub-array's averages be as close as you could to the averages of the entire array as you could by swapping some colors between the arrays to balance things out. Then you divide these arrays in half and repeat. I don't think you will (and probably can't) get optimal results with this, but I think it's may be pretty good. Finding what to swap would be the biggest problem here.