Сортировать массив в относительном порядке элементов другого массива в c

Question

Я хочу отсортировать второй массив в соответствии с первым массивом.например,

first = {1,8,7,2,4}
second = {9,7,2,10,3}

Я хочу, чтобы сначала не было изменений, а затем отсортировано в том же порядке, что и первый.то есть самое низкое значение в индексе 0, второе самое низкое значение в индексе 3, третье самое низкое значение в индексе 4 и т. д. и т. д.

second = {2,10,9,3,7}

Я уже пробовал некоторый код для следующего

#include <stdio.h>

typedef struct
{
    int num;
    int pos;
}ArrType;

ArrType arrA[5] = {{1,0},{8,1},{7,2},{2,3},{4,4}};
ArrType arrB[5] = {{9,0},{7,1},{2,2},{10,3},{3,4}};;

int cmparr(const void *a, const void *b)
{
    ArrType *tmpa, *tmpb;
    tmpa = (ArrType*) a;
    tmpb = (ArrType*) b;

    return(arrA[tmpa->pos].num - arrA[tmpb->pos].num);
}
int main(void)
{
    int i;
    qsort(arrB,5, sizeof(ArrType), cmparr);

    for (i=0; i<5; i++)
    {
        printf ("%d ",arrB[i].num);
    }
    return (0);
}

Фактический вывод:

9 10 3 2 7

Я открыт для другой структуры данных, но arrB должен быть отсортирован только один раз.

Я видел некоторые решения для этого в C ++, Javascipt и других языках.Но в C. не существует решения.

Edit - эти массивы в конечной программе будут довольно большими.Я ищу одну операцию сортировки.т.е. один звонок на qsort

Answer 1

Вам необходимо создать метаданные, которые соответствуют желаемому порядку (т. Е. Массив индексов). Затем примените эти метаданные ко второму массиву.

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

int first[] = {1,8,7,2,4};
int second[] = {9,7,2,10,3};

int compare(const void * a, const void * b);
int binary_search(int array[], int min, int max, int target);
void print_array(int * array, int c);

int main()
{
  int idx;
  int c = sizeof(first)/sizeof(int);
  int * sorted = NULL;
  int * indexes = NULL;
  int * result = NULL;

  if (NULL == (sorted = malloc(sizeof(first)))) {
      return -1;
  }
  memcpy(sorted, first, sizeof(first));

  if (NULL == (indexes = malloc(sizeof(first)))) {
      free(sorted);
      return -1;
  }
  memset(indexes, -1, sizeof(first));

  if (NULL == (result = malloc(sizeof(second)))) {
      free(sorted);
      free(indexes);
      return -1;
  }
  memset(result, -1, sizeof(second));

  // 1st: Sort the reference array
  qsort (sorted, c, sizeof(int), compare);

  // 2nd: Record the position of each sorted element in the original array (this is your meta-data)
  for (idx=0; idx<c; idx++) {
      indexes[idx] = binary_search(sorted, 0, c, first[idx]);
  }

  // 3rd sort the target array
  memcpy(sorted, second, sizeof(second));
  qsort (sorted, c, sizeof(int), compare);

  // 4th apply the stored positions to the sorted target array
  for (idx = 0; idx < c; idx++) {
      result[idx] = sorted[indexes[idx]];
  }
  print_array(result, c);

  free(result);
  free(indexes);
  free(sorted);
  return 0;
}

int compare(const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int binary_search(int array[], int min, int max, int target)
{
    int mid;
    while (min <= max)
    {
        mid = min + (max - min)/2;
        if (target > array[mid])
            min = mid + 1;
        else if (target < array[mid])
            max = mid - 1;
        else
            return mid;
    }
    return -1;
}

void print_array(int * array, int c)
{
    for(int i = 0; i < c; i++) {
        printf("%d ", array[i]);
    } 
    printf("\n");
}

Демо

Answer 2

Вот мой подход, он использует qsort дважды, а arrC содержит результат.

#include <stdio.h>

typedef struct
{   
    int num;
    int pos;
}ArrType;

ArrType arrA[5] = {{1,0},{8,1},{7,2},{2,3},{4,4}};
int arrB[5] = {9,7,2,10,3};;
int arrC[5];
int cmpInt(const void *a, const void *b)
{   
        return(*a - *b);
}
int cmp(const void *a, const void *b)
{   
    ArrType *tmpa, *tmpb;
    tmpa = (ArrType*) a;
    tmpb = (ArrType*) b; 
        return(tmpa->num - tmpb->num);
}
int main(void)
{
    int i;
    qsort(arrA,5, sizeof(ArrType), cmp);
    qsort(arrB,5, sizeof(ArrType), cmpInt);
    for (i=0; i<5; i++)
    {   
        arrC[arrA[i].pos] = arrB[i];
    }   
    return (0);
}

Answer 3

Поскольку в C нет лямбда-сравнения (которое можно использовать для сортировки массива индексов в соответствии с first []), приведенный ниже код сортирует массив указателей ap [] на элементы first [] с использованием qsort().Использование указателей устраняет необходимость передавать имя массива в качестве параметра для функции сравнения, что, в свою очередь, позволяет функции сравнения работать с qsort ().Выражение (ap [i] -first) преобразует указатель в индекс.Следующая секунда [] сортируется, также используя qsort ().Затем ap [] используется как набор рангов для переупорядочения секунды [] по месту и по времени O (n).

Для объяснения переупорядочения по рангу по сравнению с переупорядочением по индексу:

    dst[rank[i]] = src[i];              /* reorder by rank */
    dst[i] = src[index[i]];             /* reorder by index */

Пример кода:

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

/* compare for ptr to integer */
int cmppi(const void *p0, const void *p1){
    return (*(int *)p0 - *(int *)p1);
}

/* compare for ptr to ptr to integer */
int cmpppi(const void *p0, const void *p1){
    return (**(int **)p0 - **(int **)p1);
}

int main()
{
int first[] =  {1, 8, 7, 2, 4};
int second[] = {9, 7, 2,10, 3};
int **ap;                               /* array of pointers */
int *tmpp;
int tmpi;
size_t i, j;

    /* allocate and generate array of pointers to first[] */
    ap = (int **)malloc(sizeof(first)/sizeof(first[0])*sizeof(int *));
    for(i = 0; i < sizeof(first)/sizeof(first[0]); i++)
        ap[i] = &first[i];
    /* sort ap  */
    qsort(ap, sizeof(first)/sizeof(first[0]), sizeof(int *), cmpppi);
    /* sort second */
    qsort(second, sizeof(second)/sizeof(second[0]), sizeof(int), cmppi);
    /* reorder ap and second in place using ap as rank (O(n) time) */
    for (i = 0; i < sizeof(second) / sizeof(second[0]); i++){
        while(i != (j = ap[i] - first)){
            tmpp = ap[i];               /* swap(ap[i], ap[j]) */
            ap[i] = ap[j];
            ap[j] = tmpp;
            tmpi = second[i];           /* swap(second[i], second[j] */
            second[i] = second[j];
            second[j] = tmpi;
        }
    }   
    /* display second[] */
    for (i = 0; i < sizeof(second) / sizeof(second[0]); i++)
        printf("%3d", second[i]);
    printf("\n");
    free(ap);
    return 0;
}