Используя основную сортировку / счетную сортировку для массива структур в C?

Question

У меня есть массив структур, который содержит тип uint32_t. Зная максимальные и минимальные значения массива, я хочу реализовать сортировку подсчета или сортировку по основанию для сортировки массива на основе uint32_t. Диапазон значений может быть очень большим. Я понятия не имею, как отсортировать массив структур вместо целых чисел. Или есть ли лучшие алгоритмы для такой сортировки? Спасибо!

Answer 1

Выполните сортировку по основному счетчику по одному байту 32-разрядного целого числа за раз (обратите внимание, что это должен быть младший байт первым, самый старший байт последним). Для сортировки массива потребуется 4 прохода сортировки. Вам понадобится второй массив для перемещения в / из каждого прохода сортировки по основанию.

Вы сэкономите немного времени, используя матрицу индексов 4 (каждое 32-разрядное целое число имеет 4 байта) x 256 (каждый байт имеет 256 возможных значений) (изначально это счетчики, но преобразованные в индексы), заполняя матрицу всего за один проход массива.

Таким образом, это в общей сложности 5 проходов чтения и 4 прохода записи массива структур с использованием счетной / радикальной сортировки на основе 4 байтов 32-битных целочисленных значений.

Answer 2

Если вы используете qsort, вам нужно предоставить функцию сравнения, например:

struct Foo
{ 
   uint32_t index;
   other stuff;
}


int compareMyType (const void * a_, const void * b_)
{
  const Foo* a = a_;
  const Foo* b = b_;

  if ( a->index <  b->index ) return -1;
  if ( a->index == b->index ) return 0;
  if ( a->index >  b->index ) return 1;
}

Foo foos[100];
qsort(foos,100,compareMyType );

Радикальная сортировка может быть быстрее для целых чисел, но если вы действительно обеспокоены эффективностью, вы бы не сортировали массив структур, а массив указателей на структуры, поскольку при копировании данных будут существенные накладные расходы.