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

Question

Вдохновлен этим вопросом

Выбор того, какой алгоритм использовать для сортировки коллекции, можно сделать лучше, если мы заранее знаем, насколько хорошо отсортирована коллекция. Есть ли способ, которым мы можем измерить (или сохранить измерение) того, насколько хорошо отсортирована коллекция? Можем ли мы сделать это таким образом, чтобы затраты на поддержание или измерение того, насколько хорошо что-то отсортировано, не перевешивают преимущества выбора лучшего алгоритма сортировки?

Answer 1

Увеличение @Doug:

Удаление никогда не может сделать список меньше отсортированным, поэтому вам не нужно отслеживать его.

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

Возможно, это слишком много штрафа (то есть два сравнения на одну вставку). Вы могли бы сделать только одно сравнение для более размытого результата? Или мне нравится идея просто считать вставки.

Answer 2

Есть интроспективная сортировка, которая делает именно это, вроде ...

http://ralphunden.net/content/tutorials/a-guide-to-introsort/

Answer 3

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

Если изменения меньше, то данные являются низкочастотными, что указывает на неслучайное распределение.

Вы также можете измерить общую тенденцию с помощью фильтра - это средняя тенденция, измеряемая вниз или вверх - если вниз, вы можете рассмотреть возможность перевернуть весь массив или использовать сортировку, подходящую для «обращенных» данных.

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

-Adam

Answer 4

Одно подходящее решение:

Сохранить количество операций (вставок / удалений), выполненных с момента последней сортировки. Чем выше это число, тем больше вероятность несортировки коллекции.

Answer 5

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

Также есть пороговое значение для малого N. Если N мало (например, 10), сортировка вставкой хороша, даже если список не отсортирован. Java делает эту оптимизацию для маленького N в том, что иначе является сортировкой слиянием.

Answer 6

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

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

Answer 7

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

Рассчитать эту вероятность относительно просто:

int sorted = 0;
for (int i = 0; i < list_length; i++) {
    if (list[i+1] >= list[i]) {
       sorted++;
    }
}
sortedness = sorted/(list_length-1);

Надеюсь, это поможет!

Answer 8

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

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

Наконец, в 99,99% случаев зачем? Просто используйте быструю сортировку. Если ваш набор данных достаточно мал, чтобы постоянная часть сортировки Big O на быстрой сортировке перекрывала экономию времени по сравнению с пузырьковой сортировкой, сортировка будет настолько быстрой, что вам даже не придется тратить время на вопрос.

Вы действительно говорите мне, что ваш вопрос - это 0,01% вопросов, требующих решения?