Quicksort parallel arrays with respect to both arrays at the same time

Question

I have two parallel arrays, a double a[] and an int b[], that I am trying to sort using quicksort.
I want to sort the first array a[] in descending order and at the same time swap the values of b[].
Simultaneously, for elements of a[] with the same value, the elements of b[] must be sorted in ascending order.
I have adjusted the following code, but I can't figure out how to achieve the last part.

void qsort1(double a[], int b[], int lo, int hi) {
 int h, l, p, t1;
 double t;

 if (lo < hi) {
   l = lo;
   h = hi;
   p = a[hi];

   do {
     while ((l < h) && (a[l] <= p)) 
        l = l+1;
     while ((h > l) && (a[h] >= p))
        h = h-1;
     if (l < h) {
        t = a[l];
        a[l] = a[h];
        a[h] = t;
        t1 = b[l];
        b[l] = b[h];
        b[h] = t1;
      }
   } while (l < h);

   a[hi] = a[l];
   a[l] = p;

   qsort1( a, b, lo, l-1 );
   qsort1( a, b, l+1, hi );
 }
}

For example:

Arrays at the beginning:

a[1] = 10 b[1] = 1
a[2] = 15 b[2] = 2
a[3] = 20 b[3] = 3
a[4] = 15 b[4] = 4

Arrays in the end:

a[1] = 20 b[1] = 3
a[2] = 15 b[2] = 2
a[3] = 15 b[3] = 4
a[4] = 10 b[4] = 1

Answer 1

I would avoid two independent arrays. Instead I would make a struct that contained one double and one integer and make an array of that struct. The benefit is two things:

1) The array can be sorted by standar qsort

2) The requirement about sorting on the double first and sort on the integer in case of equal double values, can easily be implemented by the compare function.

It can look something like this:

typedef struct
{
  double a;
  int b;
} SomeDataType;

int compar(const void * a, const void * b)
{
  SomeDataType* pa = (SomeDataType*)a;
  SomeDataType* pb = (SomeDataType*)b;
  if (pa->a > pb->a) return -1;
  if (pa->a < pb->a) return 1;
  if (pa->b > pb->b) return 1;
  if (pa->b < pb->b) return -1;
  return 0;
}

void pd(SomeDataType* p, int n)
{
  for(int i=0; i<n; ++i)
  {
    printf("%f - %d\n", p[i].a, p[i].b);
  }
}
int main()
{
  SomeDataType arr[] = {{10.0, 1}, {15.0, 2}, {20.0, 3}, {15.0, 4}};
  pd(arr, 4);
  qsort(arr, 4, sizeof(SomeDataType), compar);
  printf("-------------------------\n");
  pd(arr, 4);
  return 0;
}

Output:

10.000000 - 1
15.000000 - 2
20.000000 - 3
15.000000 - 4
-------------------------
20.000000 - 3
15.000000 - 2
15.000000 - 4
10.000000 - 1

If it's important to have two individual arrays in the program, I would still use qsort and an array of structs. I would do the sorting in 3 steps.

1) Copy data from the individual arrays to an array of structs

2) Sort the array of structs using qsort

3) Copy the sorted data in the array of structs back to the individual arrays

That could look like:

typedef struct
{
  double a;
  int b;
} SomeDataType;

int compar(const void * a, const void * b)
{
  SomeDataType* pa = (SomeDataType*)a;
  SomeDataType* pb = (SomeDataType*)b;
  if (pa->a > pb->a) return -1;
  if (pa->a < pb->a) return 1;
  if (pa->b > pb->b) return 1;
  if (pa->b < pb->b) return -1;
  return 0;
}

void qsort1(double a[], int b[], int lo, int hi)
{
 if (lo < hi)
 {
   int num_elements = hi - lo + 1;
   SomeDataType* p = malloc(num_elements * sizeof *p);

   // Copy from individual arrays to array of structs
   for(int i=0; i<num_elements; ++i)
   {
     p[i].a = a[lo+i];
     p[i].b = b[lo+i];
   }

   // Sort array of structs
   qsort(p, num_elements, sizeof *p, compar);

   // Copy from array of structs  back to individual arrays
   for(int i=0; i<num_elements; ++i)
   {
     a[lo+i] = p[i].a;
     b[lo+i] = p[i].b;
   }

   free(p);
 }
}

void pa(double a[], int b[], int n)
{
   for(int i=0; i<n; ++i)
   {
     printf("a[%d] = %f b[%d] = %d\n", i, a[i], i, b[i]);
   }
}

int main()
{
  double a[] = {10.0, 15.0, 20.0, 15.0};
  int b[] = {1, 2, 3, 4};
  pa(a, b, 4);
  qsort1(a, b, 0, 3);
  printf("-------------------------\n");
  pa(a, b, 4);

  return 0;
}

Output:

a[0] = 10.000000 b[0] = 1
a[1] = 15.000000 b[1] = 2
a[2] = 20.000000 b[2] = 3
a[3] = 15.000000 b[3] = 4
-------------------------
a[0] = 20.000000 b[0] = 3
a[1] = 15.000000 b[1] = 2
a[2] = 15.000000 b[2] = 4
a[3] = 10.000000 b[3] = 1