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

Ответ 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 секунды для генерации перестановок.)

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

• std::sort,
• сортировка свиней (ведро) с повторным использованием ведер,
• набор операторов if и
• вставка сортировка

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

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

Ответ 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]]

Ответ 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

Ответ 7

Следующая цитата из Bentley et al., Engineering может быть интересной здесь:

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

(Подчеркните мой.)

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

Ответ 8

Хорошим источником для сравнения сортировки algos является http://www.sorting-algorithms.com/. Обратите внимание, что даже исходный статус заказа влияет на результаты. Но в любом случае для 8 целых чисел даже простая сортировка пузырьков должна выполнять эту работу.

Ответ 9

Для положительных целых чисел самый быстрый тип известен как aacus sort-it O (n)

http://en.wikipedia.org/wiki/Abacus_sort

Если у вас только очень мало элементов, то маловероятно, что вы заметите какую-либо разницу в производительности от выбора какого-либо конкретного алгоритма.

Ответ 10

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

Ответ 11

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

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

Ответ 12

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