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

Question

У меня много музыки c, и я хочу присвоить им рейтинг от наименее любимого до любимого (это займет много дней). Я хотел бы сравнить два файла musi c одновременно (двухстороннее сравнение). Я видел несколько вопросов об алгоритмах с наименьшим количеством сравнений. Но подвох в том, что (так как это долгий процесс), я хочу добавить новые муси c в коллекцию, и в этом случае я не хочу начинать заново сортировать все (таким образом создавая намного больше шагов сравнения).

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

Меня не интересует наименьшее количество сравнений только для нескольких элементов. Скажем, минимум 1000 наименований.

Бонус, если алгоритм поддерживает N-стороннее сравнение (где N> 2) в случае, если я хочу вместо этого сравнивать картинки.

РЕДАКТИРОВАТЬ: сравнение двух песен - это ручной процесс, слушая их (таким образом, медленно), алгоритм сортировки необходим, чтобы ранжировать их в наименьшем количестве сравнений

Answer 1

Кажется, в вашей задаче есть два этапа. Первый этап - сортировка всех песен, которые у вас уже есть, а второй - вставка новых песен, одна за другой, в уже отсортированный порядок.

---

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

На этот вопрос нет идеального ответа; Ни один из известных алгоритмов сортировки не использует доказуемо минимальное количество сравнений для всех входных данных. Теория информации дает n log₂ n - 1.443 n + O (log n ) в качестве теоретической нижней границы для среднего числа сравнений , но эта граница не была достигнута.

Известные в настоящее время алгоритмы сортировки, которые наиболее близки к вышеуказанной границе, представляют собой сортировка с вставкой слиянием (также известная как алгоритм Форда-Джонсона), и вариации этого. Сортировка с вставкой слиянием выполняет в среднем приблизительно n log₂ n - 1,415 n сравнений, что очень близко к теоретической границе. Для 1024 предметов вы, вероятно, будете делать что-то вроде ~ 8 790 сравнений, где теоретическая граница равна ~ 8 760.

Согласно этому другому ответу переполнения стека по состоянию на декабрь 2018 года, нет алгоритмы, улучшающие сортировку с вставкой слиянием, «свободно документированы» , что, как я понимаю, означает, что эти улучшенные алгоритмы представлены только в научных статьях c. Для сортировки с вставкой слиянием доступно больше общедоступной c информации, и вариантов для ее улучшения не так много, поэтому я бы предложил использовать этот алгоритм, а не изучать академическую c литературу; если ваш n не намного больше, от него мало что получится.

---

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

Вы не можете сделать это с помощью сравнений ⌈log₂ ( n + 1) ⌉ на вставку, поскольку существует n + 1 позиций, новый элемент может принадлежать в текущем порядке, и каждое сравнение дает один бит информации.

Алгоритм двоичного поиска работает, чтобы найти правильную позицию в отсортированном массиве; или вы можете использовать сбалансированное двоичное дерево поиска структура данных. В любом случае, каждая вставка будет достигнута с использованием оптимального количества сравнений. Преимущество использования бинарного дерева поиска состоит в том, что вставка занимает всего O (log n ); вставка в отсортированный массив требует O (log n ) сравнений, но O ( n ) время для перемещения других элементов массива.

Answer 2

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

По существу, если вы знаете о распределении ваших данных вы можете сортировать быстрее, чем O (n log n) . Например, если вы сортируете n чисел и знаете, что они являются целыми числами между 1 и N , вы можете использовать счетную сортировку отсортировать их в O (n + N) . Вы можете итеративно добавлять элементы для O (1).

Применение этого к вашей проблеме ранжирования musi c более сложное (песни не являются целыми числами), но вы можете сделать вариацию bucket sort , где вы сначала складываете свои музыкальные файлы c, скажем, в 10% "ярусов": верхние 0-10%, 10-20%, 20-30%, ..., 90-100% ( то есть дно). Затем вы можете либо рекурсивно применить сортировку по сегментам (top 0-1%, 1-2%, et c.), Либо применить стандартные алгоритмы сортировки. В конце концов, вам нужно будет сделать стандартную сортировку сравнения. Этот подход, по сравнению только с использованием сортировки сравнения, уменьшит количество сравнений в log (n) / log (n / B) , где B - это число ковши. Для 100 сегментов и 10000 песен это сокращение в 2 раза.

Альтернативный, сохраняющий сравнение подход заключается в выполнении сортировки вставками (как для начальной сортировки, так и для последующих вставок) с модифицированным двоичным поиском . : вместо того, чтобы устанавливать начальные границы двоичного поиска на 0 и n , установите их в значения, основанные на вашей собственной интуиции того, где вы уверены, что это закончится, как 0 и n / 10 , если он определенно входит в ваши лучшие 10%. Чем более детально вы можете сделать это, тем меньше будет сравнений.

Предупреждение: как с сортировкой сегментов, так и с модифицированным двоичным поиском. Если вы не правы, вам потребуется выполнить дополнительные сравнения, чтобы исправить вашу ошибку.

И последнее слово: этот вопрос предполагает, что существует - это правильный рейтинг и , что его можно достичь с помощью сравнений. Если у вас есть круговые предпочтения, такие как a> b, b> c и c> a , a la rock-paper-scissors, тогда ранжирование не может быть построено. Алгоритмы все еще будут завершены, но полученный список будет непоследовательным.

Answer 3

Предполагая, что в вашей библиотеке musi c нет порядка, сортировка по слиянию является лучшим алгоритмом сортировки. Однако добавить элементы во время сортировки слиянием не так-то просто.

Я думаю, что ваша лучшая ставка - это дерево поиска с ограниченной глубиной, такое как дерево 2-3 или красно-черное дерево. Лично я бы предложил 2-3 дерева, так как красный черный является его вариантом с меньшей сложностью для каждого узла, но с худшей границей минимальной глубины.

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

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

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