Методы сортировок и их реализации. Беляева И.В - 23 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

Сортировка
методом
вставок
Представьте
себе
колоду
карт,
из
которой
каждый
раз
вынимается
и
вставляется
на
указанное
место
одна
карта.
Такой
способ
упорядочения
называется
сортировкой
методом
вставок
(insertion sort).
В
данном
случае
массив
делится
на
две
части:
упорядоченную
и
неупорядоченную,
как
показано
на
рис.
6.
Вначале
весь
массив
неупорядочен.
На
каждом
шаге
метода
вставок
из
неупорядоченной
части
извлекается
первый
элемент,
который
затем
вставляется
в
нужное
место
упорядоченной
части.
Первый
шаг
тривиален:
переместить
элемент
theArray{O}
из
неупорядоченной
части
в
упорядоченную.
Для
этого
даже
не
нужно
переставлять
элементы
массива.
Следовательно,
этот
шаг
можно
пропустить,
считая,
что
элемент
theArray[O}
уже
принадлежит
упорядоченной
части,
анеупорядоченной
частью
массива
является
отрезок
theArray[l
...
n-l}.
Тот
факт,
что
элементы
в
упорядоченной
части
расположены
в
порядке
возрастания,
является
инвариантом
алгоритма.
Поскольку
на
каждом
шаге
размер
упорядоченной
части
увеличивается
на
единицу,
а
размер
неупорядоченной
части,
соответственно,
на
единицу
уменьшается,
в
момент
окончания
алгоритма
весь
массив
окажется
упорядоченным.
Упорядоченная
часть
Неупорядоченная
часть
~_----~----_'"
r_---
л--_
[I]
...
=
...
[I]
о
п-l
После
i
итераций
РИСУНОК
6.
Сортировка
методом
вставок
разбивает
массив
на
две
части
На
рис.
7
показаны
результаты
сортировки
массива,
состоящего
из
пяти
целых
чисел,
методом
вставок.
В
исходном
положении
упорядоченная
часть
массива
состоит
из
единственного
элемента
theArray[O},
равного
29,
а
к
неупорядоченной
части
относятся
все
остальные
элементы
массива.
Извлечем
из
неупорядоченной
части
массива
ее
первый
элемент
-
число
1
О
-
и
вставим
в
соответствующее
место
упорядоченной
части.
Для
этого
понадобится
сдвинуть
элементы
массива,
чтобы
освободить
место
для
вставляемого
числа.
Снова
извлечем
из
вновь
образованной
неупорядоченной
части
массива
ее
первый
элемент
-
число
14 -
и
вставим
в
соответствующее
место
упорядоченной
части
и
т.д.
22

Страницы