Опять же, взять в сравнение эту самую сортировку вставками и, например, HeapSort. От автора Данная статья рассматривает один из алгоритмов сортировки массивов. Реализация сортировки очень проста, всего 3 строчки. Эффективность Сортировка вставками наиболее эффективна когда массив уже частично отсортирован и когда элементов массива не много. Если же элементов меньше 10 то данный алгоритм является лучшим.

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

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

Реализация Прежде чем приступить к реализации определимся с форматом входных данных — для примера это будет массив целочисленных (int) значений. Анализ производительности Сортировка вставками имеет сложность n2, количество сравнений вычисляется по формуле n*(n-1)/2.

Простые сортировки

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

Фактически, задачей алгоритма сортировки является нахождение такой перестановки, применение которой к входной перестановке ее отсортирует. Причем для каждой из возможных входных перестановок существует 1 единственная перестановка, переводящая входной массив в отсортированный.

Когда ты можешь написать статью об алгоритме он у тебя невольно остаётся в памяти) Я не считаю этот алгоритм вершиной сложности, наоборот решил начать с простого. Сколь бы хорошим и эффективным ни был выбранный вами алгоритм, но если в качестве подзадачи он использует «плохую» сортировку, то вся работа по его оптимизации оказывается бесполезной.

Их важная особенность состоит в том, что эти алгоритмы не требуют дополнительной памяти: вся работа по упорядочению производится внутри одного и того же массива. К простым внутренним сортировкам относят методы, сложность которых пропорциональна квадрату размерности входных данных. Иными словами, при сортировке массива, состоящего из N компонент, такие алгоритмы будут выполнять С*N2 действий, где С — некоторая константа.

Общую же эффективность алгоритма обычно оценивают «в среднем»: как среднее арифметическое от сложности алгоритма «в лучшем случае» и «в худшем случае», то есть (Eff_best + Eff_worst)/2. Самый простой способ сортировки2В названиях алгоритмов мы будем следовать Кнуту., который приходит в голову, — это упорядочение данных по мере их поступления.

Понятно, что для этой сортировки наилучшим будет случай, когда на вход подается уже упорядоченная последовательность данных. В худшем же случае — когда входная последовательность упорядочена «наоборот» — сравнений будет уже (N+1)*N/2, а пересылок (N-1)*(N+3).

Алгоритм сортировки постепенно «уточняет» необходимую перестановку так, чтобы в итоге осталась одна единственная, сортирующая именно эту входную последовательность. Эти элементы поступают на вход алгоритма сортировки в виде одной из N! различных перестановок этих элементов. Для алгоритмов сортировок, основанных на сравнении элементов, доказано, что не может существовать алгоритма со сложностью лучшей, чем n*log(n).