Optimize function to order a two-dimensional array by the value of its position 0 in C

Question

double generation[genomes_per_generation][amount_of_variables];
double ranked_generation[genomes_per_generation][1 + amount_of_variables];
double tmp[1 + amount_of_variables];
int i, j, k;
for (i = 0; i < gens_per_generation; i++) {
    for (j = i + 1; j < gens_per_generation; j++) {
        if (ranked_generation[j][0] > ranked_generation[i][0]) {
            for (k = 0; k < 1 + amount_of_variables; k++) {
                tmp[k] = ranked_generation[i][k];
                ranked_generation[i][k] = ranked_generation[j][k];
                ranked_generation[j][k] = tmp[k];
            }
        }
    }
}

My intention is to move the rows of the array depending on the initial value as shown in my current code, the problem with this is that although it works, it is slow. I tried to use qsort() but it only gave me segmentation faults.

If anyone comes up with any tricks with pointers, memory align or whatever, please let me know.

Answer 1

Your current algorithm looks like a selection sort which runs in O(n²) time (where n is the genomes_per_generation here). Your overall algorithm runs in O(m n²) (where m is amount_of_variables). Using qsort is indeed a goo strategy since it should use a n log n sorting algorithm (typically an introsort).

This following code should work (untested):

int compareFun(const void* block_a, const void* block_b)
{
    double first_a = *(const double*)block_a;
    double first_b = *(const double*)block_b;

    // Optimizing compilers like Clang generate a fast branch-less code here
    if(first_a < first_b)
        return -1;
    if(first_a > first_b)
        return 1;
    return 0;
}

// In your computing function:
size_t itemSize = (1 + amount_of_variables) * sizeof(double); // In bytes!
qsort(ranked_generation, genomes_per_generation, itemSize, compareFun);

The idea is that qsort works on blocks of n bytes and you should not forget to multiply the size of a block by sizeof(double). The comparison function only compare the first item of each block like in the initial code. Note that the above code assumes ranked_generation is filled with correct values (the original code does not fill it and does not use generation either).