Найти индексы k наименьших значений в С

Question

Я внедряю K Nearest Neighbor в C, и я дошел до точки, где я вычислил матрицу расстояний каждой точки в моем наборе размера m, который должен быть помечен, до каждой точки в моем уже помеченномнабор размером n.Формат этой матрицы:

[[dist_0,0 ... dist_0,n-1]
 .
 .
 . 
 [dist_m-1,0 ... dist_m-1,n-1]]

Далее мне нужно найти k наименьших расстояний в каждой строке, чтобы я мог использовать индексы столбцов для доступа к меткам этих точек, а затем вычислить метку для точкииндекс строки относится к.Последняя часть тривиальна, но вычисление индексов k наименьших расстояний поставило меня в тупик.У Python есть простые способы сделать что-то подобное, но сама природа C заставила меня немного расстроиться.Я был бы признателен за некоторые советы (без каламбура) о том, что делать и какие полезные функции С могли бы помочь.

Answer 1

Не зная k и полагая, что он может быть переменным, самый простой способ сделать это будет:

1. Организовать каждый элемент в структуре, содержащей исходный индекс столбца.
2. Отсортируйте каждую строку матрицы в порядке возрастания и возьмите первые k элементов этой строки.

---

struct item {
    unsigned value;
    size_t index;
};

int compare_items(void *a, void *b) {
    struct item *item_a = a;
    struct item *item_b = b;

    if (item_a->value < item_b->value)
        return -1;
    if (item_a->value > item_b->value)
        return 1;
    return 0;
}

// Your matrix:
struct item matrix[N][M];

/* Populate the matrix... make sure that each index is set,
 * e.g. matrix[0][0] has index = 0.
 */

size_t i, j;

for (i = 0; i < M; i++) {
    qsort(matrix[i], N, sizeof(struct item), compare_items);

    /* Now the i-th row is sorted and you can take a look
     * at the first k elements of the row.
     */
    for (j = 0; j < k; j++) {
        // Do something with matrix[i][j].index ...
    }
}