Разработайте эффективный алгоритм для сортировки 5 различных ключей менее чем за 8 сравнений

Question

Разработка эффективного алгоритма для сортировки 5 различных - очень больших - ключей менее чем 8 сравнений в худшем случае Вы не можете использовать основную сортировку.

Answer 1

Пример последовательности операций с использованием сортировки слиянием (приведенная ниже функция merge объединит два отсортированных подсписка в один отсортированный комбинированный список):

elements[1..2] <- merge(elements[1..1], elements[2..2]) # 1 comparison
elements[3..4] <- merge(elements[3..3], elements[4..4]) # 1 comparison
elements[3..5] <- merge(elements[3..4], elements[5..5]) # 1-2 comparisons
elements[1..5] <- merge(elements[1..2], elements[3..5]) # 2-4 comparisons

Answer 2

Невозможно иметь менее 9 сравнений для сортировки 5 элементов, когда ввод неизвестен. Нижняя граница была доказана для сортировки сетей до 10. См. https://en.wikipedia.org/wiki/Sorting_network.

Правильность сортировки сетей может быть проверена по принципу Ноль-один, как упомянуто в «Искусстве компьютерного программирования», том 3, Кнута. То есть, если сеть сортировки может правильно сортировать все перестановки 0 и 1, то это правильная сеть сортировки. Ни один из алгоритмов, упомянутых в этом посте, не прошел тест Zero-one.

Кроме того, нижняя граница говорит о том, что сортировки на основе сравнения не могут иметь меньше, чем ceil (log (n!)) Компараторов для правильной сортировки, однако это не означает, что это достижимо.