Блог

Скажем, у меня есть массив A[5] , состоящий из 5 элементов 5,4,1,2,3 . Теперь я сортирую эти массивы в порядке возрастания. таким образом, результирующий массив теперь будет 1,2,3,4,5 . Я использую qsort() функцию stdlib.h для сортировки этого. Вопрос в том, как я могу получить индексы исходного массива относительно моего нового массива. первоначально мои индексы были 0,1,2,3,4 для соответствующих значений 5,4,1,2,3 , а теперь индексы изменились на 2,3,4,1,0. Как я могу эффективно получить эти индексы в C? Заранее благодарю вас (пожалуйста, напишите код, если это возможно)

Существует также следующий метод при ограниченных условиях.

 #include <stdio.h>

int main(void){
    int data[] ={ 5,4,1,2,3 }; //Without duplication, The number of limited range.
    int size = sizeof(data)/sizeof(*data);
    int keys[size];
    int i;

    printf("data :n");
    for(i=0;i<size;i  ){
        printf("%d ",data[i]);
    }
    for(i=0;i<size;i  ){
        keys[data[i]-1]=i;
    }

    printf("nndatatindexn");
    for(i=0;i<size;i  ){
        printf("%dt%dn", data[keys[i]], keys[i]);
    }
    return 0;
}
/* result sample
data :
5 4 1 2 3

data    index
1       2
2       3
3       4
4       1
5       0
*/
  

Как отсортировать массив по индексу @Kerrek, предлагается следующим образом.

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

int *array;

int cmp(const void *a, const void *b){
    int ia = *(int *)a;
    int ib = *(int *)b;
    return array[ia] < array[ib] ? -1 : array[ia] > array[ib];
}

int main(void){
    int data[] ={ 5,4,1,2,3 };
    int size = sizeof(data)/sizeof(*data);
    int index[size];//use malloc to large size array
    int i;

    for(i=0;i<size;i  ){
        index[i] = i;
    }
    array = data;
    qsort(index, size, sizeof(*index), cmp);
    printf("nndatatindexn");
    for(i=0;i<size;i  ){
        printf("%dt%dn", data[index[i]], index[i]);
    }
    return 0;
}
  

Возьмем 2D-массив. Сохраняйте числа в первом столбце, а затем соответствующие индексы во втором столбце. Вы можете написать свою функцию сравнения как:

 int compare ( const void *pa, const void *pb ) 
{
    const int *a = pa;
    const int *b = pb;
    if(a[0] == b[0])
        return a[1] - b[1];
    else
        return a[0] - b[0];
}  
  

Вызов qsort должен быть:

 qsort(array, n, sizeof array[0], compare);  // n is representing rows  
  

Смотрите Live Demo

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

 _Thread_local uint8_t *array_to_order;
_Thread_local size_t elem_size_to_order;
_Thread_local int (*cmp_for_ordering)(const void *, const void *);

int cmp_array_entry(const size_t *a, const size_t *b)
{
    return cmp_for_ordering(amp;array_to_order[*a * elem_size_to_order], amp;array_to_order[*b * elem_size_to_order]);
}

size_t *make_order_index_array(void *array, size_t *order, size_t elem_count, size_t elem_size, int (*cmp)(const void *, const void *))
{
    // If order is provided by the caller it should have suitable contents, such as when updating an order

    // Initialise the order array if not already provided
    if (order == NULL)
    {
        order = calloc(elem_count, sizeof(size_t));

        // Initialise the order array to the unsorted indices
        for (size_t i=0; i < elem_count; i  )
            order[i] = i;
    }

    // Globals used by the comparison function to order the array
    array_to_order = array;
    elem_size_to_order = elem_size;
    cmp_for_ordering = cmp;

    // Order the order array
    qsort(order, elem_count, sizeof(size_t), cmp_array_entry);

    return order;
}
  

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

 #if defined(_MSC_VER) amp;amp; !defined(_Thread_local)
    #define _Thread_local __declspec(thread)
#endif

#if !(defined(__STDC_VERSION__) amp;amp; (__STDC_VERSION__ >= 201102L)) amp;amp; !defined(_Thread_local)
    #if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__SUNPRO_CC) || defined(__IBMCPP__)
        #define _Thread_local __thread
    #endif
#elif defined(__GNUC__) amp;amp; defined(__GNUC_MINOR__) amp;amp; (((__GNUC__ << 8) | __GNUC_MINOR__) < ((4 << 8) | 9))
    #define _Thread_local __thread
#endif
  

 #include <limits.h>
#include <stdio.h>
#define SIZE 5
int* sortArrayNKeepIndices(int arr[], int arrSize){
    static int indexArr[SIZE];
    int arr2[arrSize];
    for (int i = 0; i < arrSize; i  ) {
        indexArr[i] = 0;
        arr2[i] = arr[i];
    }
    int min = 0, temp = 0;

    for (int i = 0; i < arrSize ; i  )
    {
        min = i;  // record the position of the smallest
        for (int j = i   1; j < arrSize; j  )
        {
            // update min when finding a smaller element
            if (arr[j] < arr[min])
                min = j;
        }
        // put the smallest element at position i
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    } // array sorting ends here
    int ctr = 0;
    while ( ctr < arrSize) {
        min = 0;  // restart from first element
        for (int j = 0; j < arrSize; j  )
        {
            if (arr2[j] == INT_MAX) continue; // ignore already marked as minimum indices
            // update min when finding a smaller element
            if (arr2[j] < arr2[min])
                min = j;
        }
        indexArr[ctr] = min; // updating indexArr with the index of the next minimum
        arr2[min] = INT_MAX; // marking minimum element to be ignored next time
        ctr  ;
    } //keeping track of previous indices of the array elements ends here
    return indexArr;
} // function sortArrayKeepIndices ends here
int main () {
    int arr[SIZE] = {16, 15, 12, 10, 13};
    int* ptr = sortArrayNKeepIndices(arr, SIZE);
    for (int dex = 0; dex < SIZE; dex  ){
        printf("%d (%d, %d)t", arr[dex], * (ptr   dex), dex);}
}
  

// вывод будет 10 (3, 0) 12 (2, 1) 13 (4, 2) 15 (1, 3) 16 (0, 4)
// элемент (старый индекс, новый индекс)