Сохранение исходного индекса после сортировки с использованием qsort

Question

Предположим, у меня есть следующий массив:

int A[5]={2,3,5,4,1};

В этом массиве каждый индекс представляет игрока. Например:

A[0]=player 0
A[1]=player 1
.....

Я хочу отсортировать массив в порядке убывания следующим образом:

A[5]={5,4,3,2,1};

а также я хочу отследить предыдущий индекс игроков, чтобы я мог написать отсортированный массив следующим образом:

{player 2, player 4, player 1, player 0,player 4} 

Одним словом, я хочу проследить оригинальный индекс. Я написал программу на C, используя qsort, чтобы расположить элементы в порядке убывания.

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

int A[] = {2,3,5,4,1};

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

int main ()
{
  int n;
  qsort (A, 5, sizeof(int), compare);
  for (n=0; n<5; n++)
  printf ("%d ",A[n]);
  return 0;
}

Можно ли отследить исходный индекс, также используя этот qsort?

Answer 1

Это общее требование. Возможный способ - заменить массив целых и массив структур из двух элементов:

struct PlayerScore {
    int playerId;
    int score;
}

Ваш код может стать:

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

int A[] = {2,3,5,4,1};
#define N sizeof(A)/sizeof(A[0])

struct PlayerScore {
    int playerId;
    int score;
};
int compare (const void * a, const void * b)
{
    return ( (*(struct PlayerScore*)b).score - (*(struct PlayerScore*)a).score );
}

int main ()
{
  int n;
  struct PlayerScore ps[N];
  for(n=0;n<N; n++) {
      ps[n].playerId = n;
      ps[n].score = A[n];
  }
  qsort (ps, 5, sizeof(struct PlayerScore), compare);
  for (n=0; n<N; n++)
      printf ("%d (%d) ",ps[n].score, ps[n].playerId);
  return 0;
}

И вы, наконец, получите:

5 (2) 4 (3) 3 (1) 2 (0) 1 (4)

Answer 2

Ваша проблема не имеет ничего общего с qsort как таковой, а только с дизайном программы.

"В этом массиве каждый индекс представляет игрока" - это проблема. Вы изобрели странную зависимость между индексами массива и содержимым, даже если вы хотите изменить индексы массива.

Вместо массивов int, заполненных загадочными "магическими числами", создайте массив структур со значимыми данными.

Например, это может быть что-то вроде этого:

typedef struct
{
  // whatever makes sense to store here, names, stats etc      
} player_t;

player_t players [] = 
{
  {0, ...},
  {1, ...},
};

Теперь вы можете сортировать эту таблицу по своему усмотрению.

Обратите внимание, что по соображениям производительности, возможно, было бы лучше объявить массив указателей на структуру и затем выполнить qsort этот массив. Гораздо меньше данных для qsort таким образом.

Answer 3

Вам нужно отсортировать пары чисел, например, сохраняя каждый фрагмент информации в структуре:

struct player {
  int data;
  int index;
};

struct player A[] = {{2,0}, {3,1}, {5,2}, {4,3}, {1,4}};

int compare (const void * a, const void * b)
{
   return ( ((struct player*)b)->data - ((struct player*)a)->data );
}

int main ()
{
  int n;
  qsort (A, 5, sizeof(struct player), compare);
  for (n=0; n<5; n++)
  printf ("data=%d, index=%d\n", A[n].data, A[n].index);
  return 0;
}