Какие алгоритмы сортировки дают приближенную/приближенную сортировку раньше?

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

Под "хорошим приближением" я имею в виду такие метрики, как Kendall tau и Spearman footrule для определения того, как "далеко" упорядоченный список от другого (в данном случае точного сорта)

Конкретное приложение, которое я имею в виду, - это то, где люди делают субъективное парное сравнение и, возможно, не смогут выполнять все n log n сравнений, требуемых, скажем, с помощью heapsort или bests case quicksort.

Какие алгоритмы лучше других при получении списка в ближайшем/приближенном виде раньше?

Ответ 1

Вы можете проверить алгоритм сортировки оболочки.

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

Вот еще информация http://en.wikipedia.org/wiki/Shell_sort

Ответ 2

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

Ответ 3

как насчет сортировки слева направо и заканчивая немного преждевременным (каламбур не предназначен)?

это будет время выполнения Nb, где b - количество бит, которое вы решили изучить. чем больше бит вы исследуете, тем более упорядоченным будет

несортированный:
5 0101
8 1000
4 0100
13 1101
1 0001

после 1 бит (N):
5 0101
1 0001
4 0100
13 1101
8 1000

после 2 бит (2N)
1 0001
5 0101
4 0100
8 1000
13 1101

и т.д.

Ответ 4

Мое полностью ненаучное и визуальное исследование сортирует на этой странице, указывает, что "Comb Sort" выглядит хорошо. Кажется, что с каждым проходом он приближается к лучшему приближению.

Ответ 5

Я разработал алгоритм сортировки NlgN, который я назвал "сортировкой турниров" некоторое время назад, который находит выходные данные по порядку (т.е. начинается с поиска первого элемента, затем находит второй элемент и т.д.). Я не уверен, что это совершенно практично, поскольку накладные расходы на хранение превышают затраты на сортировку quicksort, merge sort и т.д., Но в бенчмаркинге с 1,000,000 случайными элементами сравнение фактически наступило ниже стандартной реализации быстрой сортировки библиотек (хотя я не уверен, как это будет против новых).

Для моего алгоритма "оценка" каждого элемента - это количество предметов, которые, как известно, лучше. Первоначально каждый предмет имеет счет 0. Когда два предмета сравниваются, лучший предмет добавляет к его счету счет другого предмета, плюс один. Чтобы запустить алгоритм, объявите все элементы "подходящими", и пока осталось больше одного подходящего элемента, сравните два подходящих элемента с самым низким счетом и сделайте проигравшего "неприемлемым". Как только все, кроме одного элемента были объявлены неприемлемыми, выведите один оставшийся элемент и затем объявите права на все элементы, которые этот элемент "избил".

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

Ответ 6

Сортировка пузырьков я считаю. Преимущество состоит в том, что вы можете постепенно улучшать порядок с помощью дополнительных разверток данных.