Как вычислить ранг вектора в C?

Question

Как можно (эффективно/быстро) определить ранжирование (элементов) вектора в C (не C++ или использование нестандартных библиотек)? Например, ранг (ing) вектора x=(0.25, 0.54, 0.38, 0.32, 0.49, 0.06, 0.41, 0.21, 0.98, 0.23) должен быть rank(x)=(4, 9, 6, 5, 8, 1, 7, 2, 10, 3).

Как следует из названия, «ранжирование» дает ранг каждого элемента вектора по отношению ко всем другим элементам вектора. Так rank(x[k])=l означает, что k й элемент x является l го наименьшим среди всех элементов в x (например, для k=6 в приведенном выше примере, l равен 1, то есть, 6-й элемент х является наименьшим). Обратите внимание, что такая функция rank() существует в нескольких других языках программирования, но я еще не видел реализацию C. Я ищу чистую реализацию C, которая работает как можно быстрее для векторов целых чисел или действительных чисел.

Answer 1

Один из способов сделать это, чтобы сопоставить данные с индексами, сортировать с помощью qsort и компаратора, который проверяет только значение и игнорирует индекс, а затем присваивает ранги в соответствии с отсортированными индексами.

Вот реализация, которая заключается в временном массиве пар, вместо использования автоматического хранилища. Это безопаснее в тех случаях, когда объем данных достаточно велик, чтобы перехватить стек.

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

struct rank_pair { 
    double val; 
    size_t ind; 
}; 

int cmp_rank_pair(const void* a, const void* b) { 
    struct rank_pair *lhs = (struct rank_pair*)a; 
    struct rank_pair *rhs = (struct rank_pair*)b; 
    return lhs->val < rhs->val ? -1 : (lhs->val > rhs->val ? 1 : 0); 
} 

void rank(double a[], int r[], size_t n) { 
    struct rank_pair *tmp = malloc(n*sizeof(struct rank_pair)); 
    for (int i = 0 ; i != n ; i++) { 
     tmp[i].val = a[i]; 
     tmp[i].ind = i; 
    } 
    qsort(tmp, n, sizeof(struct rank_pair), cmp_rank_pair); 
    for (int i = 0 ; i != n ; i++) { 
     r[tmp[i].ind] = i+1; 
    } 
    free(tmp); 
} 

int main(void) { 
    const size_t N = 10; 
    double a[] = {0.25, 0.54, 0.38, 0.32, 0.49, 0.06, 0.41, 0.21, 0.98, 0.23}; 
    int r[N]; 
    rank(a, r, N); 
    for (int i = 0 ; i != N ; i++) { 
     printf("%d\n", r[i]); 
    } 
    return 0; 
} 

Demo.