Комментарии 1
Есть более точный анализ сортировки вставками основанный на инверсиях. Инверсия в перестановке — это такая пара элементов, что больший из них стоит раньше. Единственная перестановка с нулевым количеством инверсий — это тождественная, она же является единственной отсортированной. Утверждается, что если сортировка вставками делает своп, то число инверсий уменьшается ровно на единицу. Отсюда количество свопов — это количество инверсий. Количество сравнений — это количества свопов плюс не больше, чем n холостых проверок, после которых срабатывает break.
Среднее число инверсий в перестановке — n(n-1)/4. Это легко увидеть, если разбить перестановки на пары: перестановка и её перевернутый вариант (элементы идут в обратном порядке); каждая пара элементов образует инверсию либо в исходной перестановке, либо в её перевертыше, поэтому на две перестановки имеем n(n-1)/2 инверсий. Указанный анализ годится также и для произвольного массива, у которого все элементы различны
Что еще примечательно, если мы можем менять местами только соседние элементы, то сортировка вставками является оптимальной по количеству свопов, так как своп соседних элементов меняет количество инверсий ровно на единицу, поэтому невозможно в таких условиях сделать свопов меньше, чем количество инверсий. К слову, сортировка пузырьком также обладает этим свойством, но при этом делает много ненужных сравнений.
Еще интересным моментом является то, что можно за nlogn (а может и быстрее, если есть знатоки RMQ подскажите пожалуйста) посчитать количество инверсий и, если оно окажется достаточно мало, то использовать сортировку вставками, а если велико — что-нибудь другое
Среднее число инверсий в перестановке — n(n-1)/4. Это легко увидеть, если разбить перестановки на пары: перестановка и её перевернутый вариант (элементы идут в обратном порядке); каждая пара элементов образует инверсию либо в исходной перестановке, либо в её перевертыше, поэтому на две перестановки имеем n(n-1)/2 инверсий. Указанный анализ годится также и для произвольного массива, у которого все элементы различны
Что еще примечательно, если мы можем менять местами только соседние элементы, то сортировка вставками является оптимальной по количеству свопов, так как своп соседних элементов меняет количество инверсий ровно на единицу, поэтому невозможно в таких условиях сделать свопов меньше, чем количество инверсий. К слову, сортировка пузырьком также обладает этим свойством, но при этом делает много ненужных сравнений.
Еще интересным моментом является то, что можно за nlogn (а может и быстрее, если есть знатоки RMQ подскажите пожалуйста) посчитать количество инверсий и, если оно окажется достаточно мало, то использовать сортировку вставками, а если велико — что-нибудь другое
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сортировка вставками