Введение в информационные системы. Брюхомицкий Ю.А. - 114 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

114
Метод вставок. В этом методе упорядоченная последовательность соз-
дается на свободном участке памяти, который выделяется под длину отсортиро-
ванного массива записей. Так как исходная и упорядоченная последовательно-
сти
располагаются в разных участках памяти, для их обозначения используем
различные символы. Элементы исходной последовательности обозначим A(i), а
элементы упорядоченной последовательность – В(j).
Первый элемент А(1)
исходной последовательности А занимает первую
позицию в свободном участке памяти, т.е. становится первым элементом В(1)
последовательности В. Элемент А(2) сравнивается с В(1). Если А(2) < B(1), то
элемент В(1) передвигается на одну позицию, а элемент А(2) занимает его
прежнее место. Теперь в свободном участке памяти размещены два элемента
В(1) и В
(2), образующих последовательность, упорядоченную по возрастанию
значений ключа.
В каждом i-м проходе элемент А(i) сравнивается поочередно со всеми
элементами последовательности В, начиная с В(1). При обнаружении В(j),
большего А(i), элементы B(j), B(j+1), B(j+2), . . ., B(i–1) передвигаются на одну
позицию, освобождая место для элемента A
(i), который занимает j-ю позицию.
На рис. 8.3 приведен пример сортировки методом вставок. В рамки взя-
ты элементы последовательности А(i), включаемые в последовательность В в
текущем проходе.
10 8 9 6 1 7 3 5 4 2
Проход 1 10
Проход 2
8
10
Проход 3 8
9
10
Проход 4
6
8 9 10
Проход 5
1
6 8 9 10
Проход 6 1 6
7
8 9 10
Проход 7 1
3
6 7 8 9 10
Проход 8 1 3
5
6 7 8 9 10
Проход 9 1 3
4
5 6 7 8 9 10
В
Проход 10 1
2
3 4 5 6 7 8 9 10
Рис. 8.3. Пример сортировки методом вставок
Последовательность из N элементов будет отсортирована этим методом
за N проходов. В первом проходе сравнений не требуется, так как первый эле-
мент просто размещается в первой ячейке памяти. В дальнейшем в течение ка-
ждого i-го прохода будет выполнено в худшем случае i–1 сравнение. Худшим
является случай, когда исходная последовательность уже отсортирована в нуж-
ном порядке.

Страницы