Есть ли хорошая библиотека для сортировки большого массива чисел на C?

Question

Если у меня есть большой массив целых чисел или поплавок, что такое хороший алгоритм/ реализация для сортировки (в C)?

Уже немного поздно редактировать игру...но я ищу правильность и скорость.

Answer 1

Для сортировки массивов чисел рассмотрим алгоритм поразрядной сортировки.При правильном проектировании эти виды сортировки должны обеспечить лучшую производительность, чем GLIBC qsort().

Библиотека usort содержит реализации для всех основных числовых типов C.

http://bitbucket.org/ais/usort/wiki/Home

Преимущество в скорости поразрядной сортировки по сравнению с qsort GLIBC составляет примерно 2,5 раза для чисел с плавающей запятой двойной точности при N = 1000000 на моем 64-битном ноутбуке Intel.Однако по мере роста N преимущество должно стать еще больше, поскольку поразрядная сортировка — это алгоритм с линейным временем, требующий постоянного количества проходов по данным.

Для очень малого N один и тот же код отправляется на интросортировку или сортировку вставками.

Answer 2

qsort() из стандартной библиотеки — это хорошо.

Функции сравнения в этих случаях будут тривиальны:

int cmp_int(const void *a, const void *b)
{
    const int *ia = a;
    const int *ib = b;

    if (*ia < *ib)
        return -1;

    if (*ia > *ib)
        return 1;

    return 0;
}

int cmp_float(const void *a, const void *b)
{
    const float *fa = a;
    const float *fb = b;

    if (*fa < *fb)
        return -1;

    if (*fa > *fb)
        return 1;

    return 0;
}

(РЕДАКТИРОВАТЬ:Их версия, основанная на вычитании b из a, опирается на поведение знакового переполнения, поэтому это не очень хорошая идея.)

Answer 3

Никогда не будет плохой идеей использовать qсортировка...если только вы не разбираетесь в цифрах.

Вы пометили поразрядную сортировку.Сколько памяти вы готовы вложить?Находятся ли числа в определенном диапазоне?Есть ли у них свойства, которые делают возможной поразрядную сортировку?

Если вы не хотите использовать много памяти, qsort — отличный вариант.

Answer 4

Учитывая огромный объем оперативной памяти, которую мы получаем в настоящее время, возможна следующая сортировка наборов:отметьте бит в огромном массиве битов ОЗУ для каждого имеющегося у вас числа, а затем считайте их обратно, просканировав ОЗУ.На этапах маркировки и сканирования можно применить множество аппаратных оптимизаций.