Профилирующие алгоритмы сортировки по частично отсортированным данным

Question

Мы знаем, что некоторые сортировки, такие как сортировка вставками, хороши для массивов, которые «в основном отсортированы» и не так хороши для случайных данных.

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

Answer 1

Число инверсий - это обычная мера степени сортировки массива.

Пара элементов (pi,pj) в перестановке p называется инверсией в перестановке, если i<j и pi >pj.Например, в перестановке (3,1,2,5,4) содержит 3 инверсии (3,1), (3,2) и (5,4).

Сортированный массив получил 0 инверсий, а обратный отсортированный массив получил n * (n-1) /2.

Answer 2

Вы можете сгенерировать «частично отсортированный» набор данных, прерывая современный Fisher-Yates shuffle , запущенный на уже упорядоченном наборе данных.

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

Answer 3

Также обратите внимание на создание двоичной кучи, а затем использование представления массива в качестве отправной точки.Бинарная куча, реализованная в массиве, не отсортирована , но упорядочена.Я думаю, что это будет считаться "частично отсортировано".