Быстрая сортировка параллельных массивов по отношению к обоим массивам одновременно

Question

У меня есть два параллельных массива, double a [] и int b [], которые я пытаюсь отсортировать с помощью быстрой сортировки.
Я хочу отсортировать первый массив a [] в порядке убывания и в то же время поменять местами значения b [].
Одновременно для элементов a [] с одинаковым значением элементы b [] должны быть отсортированы в порядке возрастания.
Я изменил следующий код, но не могу понять, как выполнить последнюю часть.

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

Например:

Массивы в начале:

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

Массивы в конце:

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

Я бы избежал двух независимых массивов.Вместо этого я сделал бы структуру, которая содержала бы одно двойное и одно целое число, и сделал бы массив этой структуры.Преимущество состоит в двух вещах:

1) Массив можно отсортировать по стандартному qsort

2) Требование о сортировке по двойному первому и сортировке по целому в случае равных двойных значений,может быть легко реализован функцией сравнения.

Это может выглядеть примерно так:

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

Вывод:

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

Если важно иметь два отдельных массивав программе я бы все равно использовал qsort и массив структур.Я бы сделал сортировку в 3 шага.

1) Скопируйте данные из отдельных массивов в массив структур

2) Сортируйте массив структур, используя qsort

3) Скопируйте отсортированные данные в массиве структур обратно в отдельные массивы

Это может выглядеть следующим образом:

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

Вывод:

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