Какой алгоритм сортировки самый быстрый для небольшого числа целых чисел?

Question

Мне интересно, какой самый быстрый алгоритм будет для этого.У меня есть 8 целых чисел от 0 до 3000, и мне нужно их отсортировать.Хотя целых чисел всего 8, эта операция будет выполняться миллионы раз.

Answer 1

Вот реализация нечетно-четной сети сортировки слиянием в C99 (извините за «неправильный» язык):

#define CMP_SWAP(i, j) if (a[i] > a[j])              \
    { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }

void sort8_network(int *a)
{
    CMP_SWAP(0, 1); CMP_SWAP(2, 3); CMP_SWAP(4, 5); CMP_SWAP(6, 7);
    CMP_SWAP(0, 2); CMP_SWAP(1, 3); CMP_SWAP(4, 6); CMP_SWAP(5, 7);
    CMP_SWAP(1, 2); CMP_SWAP(5, 6); CMP_SWAP(0, 4); CMP_SWAP(1, 5);
    CMP_SWAP(2, 6); CMP_SWAP(3, 7); CMP_SWAP(2, 4); CMP_SWAP(3, 5);
    CMP_SWAP(1, 2); CMP_SWAP(3, 4); CMP_SWAP(5, 6);
}

Я рассчитал это на своей машине против сортировки вставкой

void sort8_insertion(int *a)
{
    for (int i = 1; i < 8; i++)
    {
        int tmp = a[i];
        int j = i;
        for (; j && tmp < a[j - 1]; --j)
            a[j] = a[j - 1];
        a[j] = tmp;
    }
}

Примерно для 10 миллионов сортировок (ровно в 250 раз больше всех 40320 возможных перестановок) сеть сортировки заняла 0,39 секунды, а сортировка вставки - 0,88 секунды.Мне кажется, оба достаточно быстры.(Цифры включают около 0,04 секунды для генерации перестановок.)

Answer 2

Быстрее всего было бы просто написать множество if операторов, чтобы сравнить их, чтобы определить их точный порядок. Это снимет накладные расходы, которые есть у любого алгоритма сортировки.

Answer 3

Самый быстрый способ - это сортировочная сеть , реализованная аппаратно. За исключением этого, самый быстрый способ определяется только измерением. Я бы попробовал

• std::sort
• сортировка по типу ям с ведром с повторным использованием ведер,
• куча if операторов и
• сортировка вставок

в таком порядке, потому что это самый простой в сложном порядке (попробуйте правильно выполнить сортировку при вставке в первый раз ...), пока не найдете что-то, что можно обслуживать, как только константа восемь получит значение девять.

Кроме того, сортировка по пузырькам, выбор заслуживают внимания и сортировка по оболочке заслуживают уведомления. Я никогда не реализовывал их, потому что у них плохая репутация, но вы можете попробовать их.

Answer 4

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

(В зависимости от многих факторов, точка отсечения, при которой быстрая сортировка становится лучше, чем сортировка вставкой, обычно находится между 5 и 10элементы).

Answer 5

лет спустя) до 32 входов, см. Сортировка сетевого генератора . Для 8 входов это дает 19 обменов, как ответ Свена Марнача:

o--^--^--------^--------------------------o
   |  |        |
o--v--|--^--^--|--^--^--------------------o
      |  |  |  |  |  |
o--^--v--|--v--|--|--|--^--------^--------o
   |     |     |  |  |  |        |
o--v-----v-----|--|--|--|--^--^--|--^--^--o
               |  |  |  |  |  |  |  |  |
o--^--^--------v--|--v--|--|--|--v--|--v--o
   |  |           |     |  |  |     |
o--v--|--^--^-----v-----|--|--|-----v-----o
      |  |  |           |  |  |
o--^--v--|--v-----------v--|--v-----------o
   |     |                 |
o--v-----v-----------------v--------------o


There are 19 comparators in this network,
grouped into 7 parallel operations.

[[0,1],[2,3],[4,5],[6,7]]
[[0,2],[1,3],[4,6],[5,7]]
[[1,2],[5,6],[0,4],[3,7]]
[[1,5],[2,6]]
[[1,4],[3,6]]
[[2,4],[3,5]]
[[3,4]]

Answer 6

Я запустил библиотеку алгоритмов сортировки для всех перестановок {0, 429, 857, 1286, 1714, 2143, 2571, 3000}.

Самые быстрые были:

name                                time   stable in-place
AddressSort                         0.537   No      No
CenteredLinearInsertionSort         0.621   Yes     No
CenteredBinaryInsertionSort         0.634   Yes     No
BinaryInsertionSort                 0.639   Yes     Yes
...
QuickSort                           0.650   No      Yes
...
BubbleSort                          0.802   Yes     Yes

Подробнее об AddressSort см. http://portal.acm.org/citation.cfm?id=320834

Answer 7

Следующая цитата из Bentley и др. , Разработка функции сортировки может быть интересна здесь:

Различные улучшения сортировки вставками, включая бинарный поиск, развертывание цикла и обработку n = 2 в качестве особого случая, не помогли. Самый простой код был самым быстрым.

(Акцент мой.)

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

Answer 8

Для целых чисел, вы можете попробовать radix-sort. Это O (N).

Answer 9

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

В общем случае std :: sort () будет быстрее, чем все, что вы можете написать, если вы не настоящий гуру сортировки.

Answer 10

Для очень небольшого количества целых, сортировка пузырьков может быть очень быстрой.Пузырьковая сортировка с числовыми сравнениями может быть записана с очень низкими издержками, а при малых n реальная разница между O (n log n) и O (n ^ 2) стирается.