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

Question

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

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

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

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

Answer 1

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

Из этого ACM Paper:

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

Из вики статьи Insertion sort:

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

SO Вопрос: Is there ever a good reason to use Insertion Sort?

Answer 2

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

Answer 3

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

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

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

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

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

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

Answer 4

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