Какой алгоритм сортировки использует наименьшее количество сравнений?

Представьте себе случай, когда сравнение двух элементов чрезвычайно дорого.

Какой алгоритм сортировки вы бы использовали?

Какой алгоритм сортировки использует наименьшее количество сравнений в среднем случае?

Что делать, если вы можете ожидать, что многие сравниваемые элементы будут идентичными, скажем, в 80% сравнений. Это имеет значение?

Ответы

Ответ 1

Вполне возможно Вставка Сортировка

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

Однако, если сравнение очень дорогое, и если большинство ключей идентичны, возможно, что вход можно считать уже отсортированным или уже почти отсортированным.

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

Ответ 2

Победитель Sleep Sort, который не использует сравнения.

Ответ 3

Посмотрите на ссылку wikipedia Ваш выбор структуры данных также влияет на сортировку.

Ответ 4

Это зависит от того, какие данные у вас есть. Вам нужен стабильный алгоритм или нет?

Если ваши данные равномерно, вы можете использовать сортировку ковша (Θ (n), O (n ^ 2))

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

Конечно, вы можете использовать Sleep sort, но если у вас много данных, он не будет работать.

Если ваши элементы на 80% идентичны, может быть, есть простой способ сказать, что они идентичны (то же самое)?

Ответ 5

Сортировка дистрибутива (с использованием хэш-массива) почти не сравнивает.

m = max number  may appear in the input + 1
hash = array of size m
initialize hash by zeroes

for i = 0 to n - 1
    hash[input[i]] = hash[input[i]] + 1
j = 0
for i = 0 to m - 1
    while hash[i] > 0
        sorted[j] = i
        j = j + 1
        hash[i] = hash[i] - 1