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

The actual output is not as expected. Something is wrong in the cmparr function or in the data structures used. — Ranon
– Ranon, Commented Jun 21, 2019 at 6:12
@Socowi - I have specified the expected output second = {2,10,9,3,7} — Ranon
– Ranon, Commented Jun 21, 2019 at 6:14
@Socowi i believe it is more like: you check the order of first so lowest is at position 0 next is at position 3 etc. Then you apply this order to second so you search the lowest value and place it at position 0 then you search the next value and place it at position 3 etc. — Yastanub
– Yastanub, Commented Jun 21, 2019 at 6:42
@Ranon You're not going to find a solution with a single sorting operation. Since you implicitly need to be able to answer the question "what element is the largest element in an array?" you either need to sort both of them or search them - a much more expensive operation on an unsorted array. — Tibrogargan
– Tibrogargan, Commented Jun 21, 2019 at 7:18

Tibrogargan · Accepted Answer · 2019-06-21 07:22:05Z

2

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

edited Jun 21, 2019 at 7:22

answered Jun 21, 2019 at 6:50

Tibrogargan

4,6323 gold badges21 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ranon Over a year ago

There are 3 sorting operations in this solution. As the size of the array would be large, i am looking for a single sort operation.

Tibrogargan Over a year ago

Where is the 3rd? Not that it matters, 2 is greater than 1.

Sandy · Accepted Answer · 2019-06-23 13:31:36Z

1

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

edited Jun 23, 2019 at 13:31

answered Jun 21, 2019 at 6:55

Sandy

9036 silver badges18 bronze badges

2 Comments

Ranon Over a year ago

There are 2 sorting operations here. Can it be done with only a single sorting operation?

Sandy Over a year ago

@Ranon We need to find the mapping of sorted vs given order, it will require one sorting procedure. Other sorting procedure is for getting second array sorted so that using the mapping is a linear operation. This is a NlogN solution, if we manage to do it in a single sorting operation it will still be NlogN.

rcgldr · Accepted Answer · 2019-06-21 10:35:51Z

Since C doesn't have a lambda compare (which could be used to sort an array of indexes according to first[]), the code below sorts an array of pointers ap[] to the elements of first[] using qsort(). Using pointers eliminates the need to pass an array name as a parameter for the compare function, which in turn allows the compare function to work with qsort(). The expression (ap[i]-first) converts a pointer into an index. Next second[] is sorted, also using qsort(). Then ap[] is used as a set of ranks to reorder second[] in place and in O(n) time.

To explain reorder by rank versus reorder by index:

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

Example code:

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

Collectives™ on Stack Overflow

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

3 Answers 3

2 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related