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

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


c arrays struct counting-sort radix-sort
person niu    schedule 08.05.2015    source источник
comment
Во-первых: реализовать более простую сортировку, такую ​​как пузырьковая сортировка, используя структуры, содержащие тип int. Как только вы поймете, как это сделать, вы можете перейти к сортировке по основанию. Не пытайтесь сделать все за один шаг.   -  person JS1    schedule 08.05.2015
comment
Если ваши структуры содержат элементы, отличные от uint32_t, которые вы хотите использовать в качестве ключа сортировки, то о стандартной сортировке подсчетом не может быть и речи, поскольку она основана на неразличимости целых чисел, имеющих одинаковое значение. Если диапазон значений велик, как вы говорите, то, вероятно, сортировка подсчетом в любом случае является плохой идеей, потому что она масштабируется как O(R+N) во времени и памяти, где R — диапазон сортируемые значения.   -  person John Bollinger    schedule 08.05.2015

Ответы (2)


arrow_upward
0
arrow_downward

Если вы используете 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 );

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

person Mark Lakata    schedule 08.05.2015
comment
Спасибо за Ваш ответ! Я реализовал qsort с функцией сравнения. Но как реализовать сортировку по основанию для сортировки массива указателей? - person niu; 18.06.2015
comment
При сортировке по основанию вы создаете N ячеек, выполняете цикл по массиву и помещаете каждый элемент в одну из ячеек (в зависимости от цифры, по которой вы сортируете), а затем снова объединяете ячейки. Повторите это для каждой цифры, пока не закончите. В вашем случае вместо помещения целого числа в корзину вы помещаете указатель в корзину. - person Mark Lakata; 18.06.2015

arrow_upward
0
arrow_downward

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

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

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

person rcgldr    schedule 09.05.2015