Сортировка вставкой.

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

Реализация алгоритма на языке Java:

При рассмотрении данного алгоритма также учитывается особое свойство сортируемого массива — инвариант цикла. Здесь элементы 0…j — 1 полностью отсортированы, а остальные j + 1…n элементов не отсортированы. Во внешнем цикле мы получаем элемент из неотсортированной части(на начало выполнения алгоритма она включает в себя один единственный элемент) и присваиваем его переменной key. Далее мы получаем позицию самого правого элемента из отсортированной части. Нам надо определить место для вставки нового элемента. Для этого мы последовательно, справа-налево до первого элемента сравниваем его значение со значениями других отсортированных элементов. Если значение key > a[i], то значение a[i] сдвигается вправо, освобождая место для нового элемента. В конце концов элемент будет добавлен в отсортированную часть и мы тоже самое проделаем для следующего элемента. Сортировка будет выполняться до тех пор, пока все элементы массива не окажутся в отсортированной части. Для наглядности нашел такую картинку:

insertionsort

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

Реализация алгоритма на языке С:

Вычислительная сложность данного алгоритма составляет O(n^2). Но данный метод все же работает быстрее пузырьковой сортировки и немного быстрее сортировкой методы выбором, а также часто применяется на последних этапах других методов сортировки, например, быстрой сортировки.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *