Сортировка вставками — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 87: Строка 87:
 
== Источники ==
 
== Источники ==
 
* [http://ru.wikipedia.org/wiki/Сортировка_вставками Википедия - свободная энциклопедия]
 
* [http://ru.wikipedia.org/wiki/Сортировка_вставками Википедия - свободная энциклопедия]
 +
 +
== Дополнительные материалы ==
 +
* [http://rain.ifmo.ru/cat/view.php/vis/sorts/quadratic-2010 Визуализатор квадратичных алгоритмов]

Версия 20:33, 17 мая 2011

Сортировка вставками - квадратичный алгоритм сортировки.

Алгоритм

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

В худшем случае, время работы массива составит [math]\theta(n^2)[/math]

Псевдокод

Вход: массив A, состоящий из элементов A[1], A[2], ..., A[n]

for i = 2, 3, ..., n:  
    key := A[i]
    j := i - 1
    while j > 0 and A[j] > key:
        A[j + 1] := A[j]
        j := j - 1
    A[j + 1] := key

Пример работы

Пример работы алгоритма для массива [5, 2, 4, 3, 1]

До После Описание шага
Первый проход(проталкиваем второй элемент (2))
5 2 4 3 1 2 5 4 3 1 Алгоритм сравнивает второй элемент с первым и меняет их местами.
Второй проход(проталкиваем третий элемент (4))
2 5 4 3 1 2 4 5 3 1 Сравнивает третий со вторым и меняет местами
2 4 5 3 1 2 4 5 3 1 Второй и первый отсортированы, swap не требуется
Третий проход(проталкиваем четвертый элемент (3))
2 4 5 3 1 2 4 3 5 1 Меняет четвертый и третий местами
2 4 3 5 1 2 3 4 5 1 Меняет третий и второй местами
2 3 4 5 1 2 3 4 5 1 Второй и первый отсортированы, swap не требуется
Четвертый проход(проталкиваем пятый элемент (1))
2 3 4 5 1 2 3 4 1 5 Меняет пятый и четвертый местами
2 3 4 1 5 2 3 1 4 5 Меняет четвертый и третий местами
2 3 1 4 5 2 1 3 4 5 Меняет третий и второй местами
2 1 3 4 5 1 2 3 4 5 Меняет второй и первый местами. Массив отсортирован.

См. также


Источники

Дополнительные материалы