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

Question

У меня есть список строк, которые были отсортированы по определенной функции сравнения.

Теперь я должен пересортировать этот список, используя другую функцию сравнения.

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

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

Answer 1

Вставка сортировки хорошо работает с небольшими или почти отсортированными списками.

Из этой бумаги ACM :

Тесты по случайно сгенерированным спискам различные комбинации длины списка и небольшие коэффициенты сортировки указывают что Straight Insertion Sort лучше для небольших или почти отсортированных списков и что Quickersort лучше в противном случае.

Из статьи вики Сортировка вставок :

Если входной массив уже отсортирован, сортировка вставки выполняет всего лишь n-1 сравнения, таким образом, делая вставку сортировать более эффективно, когда дано отсортировано или "почти отсортированные" массивы.

SO Вопрос: Есть ли когда-нибудь веская причина использовать сортировку вставками?

Answer 2

Для почти отсортированных списков варианты сортировки Comb превосходят быструю сортировку. Я не проверял, как сортировка гребешков сравнивается с сортировкой вставок.

Answer 3

Как я понял, ваш список данных уже отсортирован (скажем, по порядку кодировки ascii / country), но без некоторых словарных правил, применяемых для конкретной страны. Например Германия и их умлауты

см. Germanic_umlaut в Википедии

Вы не вставляете новые элементы, вы просто хотите применить их к более строгому правилу сортировки.

как вы можете прочитать, например, здесь

http://www.softpanorama.org/Algorithms/Sorting/bubblesort.shtml

пузырьковая сортировка хорошо работает с уже отсортированными списками с несколькими перестановками. Звучит так, будто пузырьковая сортировка - хороший алгоритм для начала. Также обратите внимание, что пузырьковая сортировка является «стабильным» алгоритмом сортировки. Это может быть важно для вашего сценария.

Answer 4

Есть доступ к обеим операциям поиска? Если да, вы можете создать некоторое хеш-дерево во время первого процесса сортировки и использовать его для других операций сортировки