Sort an array in the relative order of elements of another array in c

Question

I wish to sort a second array as per the first array. e.g.

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

I want first to be unchanged and second to be sorted in the same relative order as the first. i.e. the lowest value is at index 0, the second lowest value is at index 3, third lowest value is at index 4 etc etc

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

I have already tried some code for the following

#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);
}

The actual output is

9 10 3 2 7

I am open to a different data structure, but arrB should only be sorted one time.

I have seen some solutions for this in C++, Javascipt and other languages. But there is not a solution in C.

Edit - These arrays would be quite large in the final program. I am looking for a single sorting operation. i.e. single call to qsort

Answer 1

You need to create the meta-data that matches the desired ordering (i.e an array of indexes). Then apply that meta-data to the second array.

#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");
}

Demo

Answer 2

Here is my approach, it uses qsort twice and arrC contains the result.

#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);
}