heap.tech
лаборатория велосипедов
×

Insertion sorting algorithm. Сортировка вставкой.

18 марта 2016
В двух предыдущих статьях я рассказывал что такое алгоритмы и привел примеры реализации двух алгоритмов сортировки: сортировка пузырьком с сортировка выбором (перебором). Это простые алгоритмы, но вместе с тем они работают достаточно быстро, хотя алгоритм сортировки выбором в любом случае имеет одно и тоже количество сравнений и перестановок.

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

Поехали!



Предыдущие статьи
1. Bubble sorting algorithm. Пузырьковая сортировка
2. Selection sorting algorithm. Сортировка выбором.


Пусть массив A состоит из 4 ячеек [7,1,6,3]. Отсортируем массив А по возрастанию с использованием алгоритма вставки.
Сортировка массива начинается со второй ячейки (значение равно 1). Запоминаем её (цифра один). Запускаем вложенный цикл и проверяем значения в предыдущих ячейках, так как у нас первая итерация - нужно проверить всего одну ячейку - самую первую. Так как 1 < 7 - необходимо сделать записать вторую ячейку, на место первой. Внутренний цикл на этом заканчивается. Теперь остается записать ранее записанную ячейку (со значением 1) на место второй ячейки (значение которой равно 7).

Реализация

function insertionSort(arr) { var len = arr.length, el, j; for (var i = 1; i < len; i++) { el = arr[i]; j = i; while (j > 0 && arr[j - 1] > el) { arr[j] = arr[j - 1]; j--; } arr[j] = el; } return arr; }


Верхний цикл перебирает массив начиная с первого элемента и до конца массива. Второй цикл перебирает массив начиная с текущей позиции из верхнего цикла и до 0, а также arr[j - 1] > el. Это значит, что цикл будет выполняться до момента, пока значение предыдущего элемента массива больше, чем значение текущей ячейки из верхнего цикла. Это логично, ведь какая-то часть уже может быть отсортирована, поэтому нет смысла проверять каждый раз весь массив целиком.

Да, а где традиционный порядок сортировки ?

function insertionSort(arr, orderByDesc) { var len = arr.length, el, j; var comprasion = function (indexer, a, b) { if (indexer > 0) { if (orderByDesc) return a < b; else return a > b; } return false; }; for (var i = 1; i < len; i++) { el = arr[i]; j = i; while (comprasion(j, arr[j - 1], el)) { arr[j] = arr[j - 1]; j--; } arr[j] = el; } return arr; }


Вызывать так:

var shakedArray = [7,6,4,2,1,9,7,3,5,9,2], orderedArray = insertionSort(shakedArray, true);


Плюсы

Алгоритм устойчивый - то есть не меняет порядок отсортированных чисел.
Алгоритм простой, его легко запомнить

Минусы

Википедия пишет о большой вычислительной сложности. В частности вот это j > 0 && arr[j - 1] > el и вот это arr[j] = arr[j - 1].

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

Оставлять комментарии могут только зарегистрированные пользователи

пока никто не оставлял комментариев