Идея метода. Массив разделяется на две части: отсортированную и не отсортированную. Элементы из не отсортированной части поочередно выбираются и вставляются в
отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов.
В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент, а в качестве не отсортированной части - все остальные элементы.
Пусть теперь k-1 элементов массива упорядочены. Необходимо подобрать среди них место для k-го элемента. Это можно сделать, например, сравнивая его поочередно с предыдущими, найти его место, затем "сдвинуть" вправо все элементы, начиная с найденного номера, уже упорядоченного массива на 1 позицию.
Основные блоки алгоритма: Считаем, что первые k-1 элементов массива уже упорядочены
последовательный просмотр элементов, начиная с первого по (k-1)-й, до тех пор, пока не встретится элемент, больший k-го; запоминание номере этого элемента - m;
запоминание значения k-го элемента во вспомогательной переменной;
"сдвиг" элементов с m-го по (k-1)-й вправо, причем сначала (k-1)-й элемент помещается на место k-го, затем (k-2)-й на место (k-1)-го и т. д.;
помещение k-го элемента на "освободившееся" m-ое место.
|
Начальное состояние массива |
12 18 15 14 10 22 15 |
|
Шаг 1 |
12 18 15 14 10 22 15 |
|
Шаг 2 |
12 18 15 14 10 22 15 |
|
Шаг 3 |
12 15 18 14 10 22 15 |
|
Шаг 4 |
12 14 15 18 10 22 15 |
|
Шаг 5 |
10 12 14 15 18 22 15 |
|
Шаг 6 |
10 12 14 15 15 18 22 |
Чтобы вставить элемент в отсортированный массив, важен номер (индекс) его нового места.
Для запоминания вставляемого элемента потребуется одна вспомогательная переменная.
Чтобы освободить место для вставки элемента, нужно сдвинуть элементы массива вправо на одну позицию.
Вычислительная эффективность сортировки вставками
Сортировка вставками требует фиксированного числа проходов. На n-1 проходах вставляются элементы от A[1] до A[n-1]. На i-ом проходе вставки производятся в подсписок A[0]–A[i] и требуют в среднем i/2 сравнений. Общее число сравнений равно
|
1/2 + 2/2 + 3/2 + ... + (n-2)/2 + (n-1)/2 = n(n-1)/4 |
В отличие от других методов, сортировка вставками не использует обмены. Сложность алгоритма измеряется числом сравнений и равна O(n2). Наилучший случай – когда исходный список уже отсортирован. Тогда на i-ом проходе вставка производится в точке A[i], а общее число сравнений равно n-1, т.е. сложность составляет O(n). Наихудший случай возникает, когда список отсортирован по убыванию. Тогда каждая вставка происходит в точке A[0] и требует i сравнений. Общее число сравнений равно n(n-1)/2, т.е. сложность составляет O(n2).
В принципе, алгоритм сортировки вставками можно значительно ускорить. Для этого следует не сдвигать элементы по одному, как это продемонстрировано в приведенном выше примере, а находить нужный элемент с помощью бинарного поиска, описанного в предыдущем номере (то есть, в цикле разбивая список на две равные части, пока в списке не останется один-два элемента), а для сдвижки использовать функции копирования памяти. Такой подход дает довольно высокую производительность на небольших массивах. Основным узким местом в данном случае является само копирование памяти. Пока объем копируемых данных (около половины размера массива) соизмерим с размером кэша процессора 1 уровня, производительность этого метода довольно высока. Но из-за множественных непроизводительных повторов копирования, этот способ менее предпочтителен, чем метод «быстрой» сортировки, описанный в следующем разделе. Этот же метод можно рекомендовать в случае относительно статичного массива, в который изредка производится вставка одного-двух элементов.
