Вопрос 10.1. Как реализуется сортировка вставками и какова временная сложность этого метода сортировки

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

Если сортируемый файл целиком помещается в память (или целиком помещается в массив, то для него мы используем внутренние методы сортировки. Сортировка данных с ленты или диска называется внешней сортировкой.

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

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

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

В лучшем случае: 2(n-1), В среднем случае: , В худшем случае:

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

void insert_sort(int *array, int n)

{

int i, j, temp;

for (i = 1; i < n; i++) {

temp = array[i];

for (j = i-1; j >= 0 && temp < array[j]; j--)

array[j+1] = array[j];

array[j+1] = temp;

}

}