Сортировка вставками — различия между версиями
Borisov (обсуждение | вклад) (→Источники) |
Borisov (обсуждение | вклад) (→Алгоритм) |
||
| Строка 4: | Строка 4: | ||
<wikitex>На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. | <wikitex>На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. | ||
| − | Алгоритм работает за $O(n + k)$, где k — число обменов элементов входного массива. В среднем и в худшем случае — за $O(n^2)$.</wikitex> | + | Алгоритм работает за $O(n + k)$, где k — число обменов элементов входного массива. В среднем и в худшем случае — за $O(n^2)$. Более точные оценки работы алгоритма приведены ниже. |
| + | </wikitex> | ||
==Псевдокод== | ==Псевдокод== | ||
Версия 16:49, 20 мая 2012
Сортировка вставками — квадратичный алгоритм сортировки.
Содержание
Алгоритм
<wikitex>На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
Алгоритм работает за $O(n + k)$, где k — число обменов элементов входного массива. В среднем и в худшем случае — за $O(n^2)$. Более точные оценки работы алгоритма приведены ниже. </wikitex>
Псевдокод
<wikitex>
for (int i = 1; i $\leqslant$ n - 1; i++)
j $\leftarrow$ i - 1
while (j $\geqslant$ 0 && a[j] > a[j + 1])
a[j] $\leftrightarrow$ a[j + 1]
j $\leftarrow$ j - 1
</wikitex>
Пример работы
Пример работы алгоритма для массива [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 | Меняет второй и первый местами. Массив отсортирован. |
См. также
- Сортировка пузырьком
- Сортировка выбором
- Сортировка кучей
- Сортировка слиянием
- Быстрая сортировка
- Сортировка подсчетом
Источники
- Википедия - свободная энциклопедия
- Н. Вирт «Алгоритмы и структуры данных», часть 2.2.1 "Сортировка с помощью прямого включения"
