Методические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "




НазваниеМетодические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "
страница5/19
Дата публикации28.09.2013
Размер1.39 Mb.
ТипМетодические указания
vbibl.ru > Информатика > Методические указания
1   2   3   4   5   6   7   8   9   ...   19
^


Метод двухпутевой вставки



Метод двухпутевой вставки является модификацией метода вставки с прямым включением; он позволяет улучшить характеристики сортировки.
Для реализации этого метода необходим дополнительный объем памяти, равный объему, занимаемому таблицей, подлежащей сортировке (назовем его зоной вывода T). На первом шаге сортировки в середину зоны вывода (позиция m=(n div 2)+1) помещается первая запись таблицы R[1]. Остальные позиции Т пока пусты. На последующих шагах сортировки ключ очередной записи R[j] (j=2, 3, …, n) сравнивается с ключом записи T[m] и, в зависимости от результатов сравнения, место для R[j] отыскивается в Т слева или справа от T[m] методом вставки. При этом должны запоминаться номера самого левого (l) и самого правого (r) внесенных в зону вывода элементов. Конечные значения l и r равны 1 и n соответственно.
В алгоритме должны быть учтены также следующие ситуации:

  • ключ записи ^ R[j] меньше ключа записи T[m], но l=1;

  • ключ записи R[j] больше ключа записи T[m], но r=n.


В этих случаях для вставки записи R[j] необходимо осуществлять сдвиг записей подтаблицы вместе с записью T[m] вправо или влево (используется метод вставки с прямым включением).
Рассмотрим пример сортировки с использованием этого метода.
Пусть исходная последовательность ключей таблицы имеет вид:
24, 1, 28, 7, 25, 3, 6, 18, 8 (n=9, m=(n div 2)+ 1=5)


Номер шага

j
^

Зона вывода



Поясне-

ния

1

2

3

4

5

6

7

8

9

1













24













r=5, l=5

2










1

24













1<24, l=4

3










1

24

28










28>24, r=6

4







1

7

24

28










7<24, l=3

5







1

7

24

25

28







25>24, r=7

6




1

3

7

24

25

28







3<24, l=2

7

1

3

6

7

24

25

28







6<24, l=1

8

1

3

6

7

18

24

25

28




18<24, r=8

9

1

3

6

7

8

18

24

25

28

8<18, r=9
1   2   3   4   5   6   7   8   9   ...   19

Похожие:

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconФизика методические указания к лабораторным работам 10, 31
Козлов В. А., Курушин А. Д., Серов Е. А. Физика. Методические указания к лабораторным работам 10, 31 // Под общ ред доц. С. Г. Стоюхина....

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания и задания к лабораторным работам по курсам “
Дискретные структуры“, “Теория алгоритмов и вычислительных процессов“ (для студентов специальностей 050102 “Программное обеспечение...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным наборам предназначены для студентов,...
Металлургическая гидроаппаратура: Методические указания к лабораторным работам / Санкт-Петербургский государственный горный институт...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по дисциплине «Автоматизация...
Сапр простейшей структуры на основе расчета и анализа критериев эффективности с использованием имитационных моделей

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по курсу “
В прологе предусматриваются основные арифметические операции +, -, /, ×, mod, div. Чтобы заставить систему выполнить присваивание...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по дисциплине «Программирование»
Тема: Разработка классов, создание конструкторов и деструкторов. Использование статических членов класса

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconУчебное пособие к лабораторным работам
Автоматизированные информационно-управляющие системы: учебное пособие к лабораторным работам / Л. С. Казаринов, Т. А. Барбасова,...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconКонтрольные задания по курсу «Экономико-математическое моделирование»...
Контрольные задания по курсу «Экономико-математическое моделирование» и методические указания к их выполнению

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconКонтрольные задания по курсу «Экономико-математическое моделирование»...
Контрольные задания по курсу «Экономико-математическое моделирование» и методические указания к их выполнению

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания и контрольные задания к выполнению контрольных...
В методических указаниях приведены программа изучения курса, контрольные вопросы, контрольные задания и методические указания по...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница