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




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

Метод вставки с бинарным включением



Метод вставки с прямым включением можно улучшить, если отыскивать место для вставляемой записи в упорядоченной подтаблице с помощью метода бинарного (дихотомического, двоичного, логарифмического) поиска. Эта модификация метода вставки названа вставкой с бинарным включением.
Рассмотрим j й шаг сортировки (j=2, 3, ..., n). Если K[j]>=K[j-1], то упорядоченность не нарушилась и следует перейти к R[j+1]–ой записи. Если же K[j]<K[j-1], то R[j] запоминается в рабочей переменной (Rab=R[j]) и для нее ищется место в упорядоченной части таблицы – в подтаблице. Обозначим нижнюю границу индекса этой подтаблицы через ng, верхнюю - через vg (первоначально ng=1. vg=j-1).
Согласно бинарному поиску ключ K[j] рассматриваемой записи R[j] должен сначала сравниться с ключом K[i] записи R[i], находящейся в середине упорядоченной подтаблицы (i=(ng+vg) div 2). Если K[j]>K[i], то отбрасывается (то есть больше не рассматривается) левая часть подтаблицы- записи с меньшими ключами (ng=i+1). Если K[j]<K[i], то отбрасывается правая часть подтаблицы - записи с большими ключами (vg=i-1). В оставшейся части подтаблицы поиск продолжается. Процесс деления частей подтаблицы пополам продолжается до тех пор, пока не возникнет одна из следующих ситуаций:
1) K[j]=K[i], следовательно, (i+1)-я позиция является местом для рассматриваемой записи. Сдвинем записи R[i+1], R[i+2], …, R[j-1] на одну позицию вправо и освободим тем самым место для вставки (R[i+1]=Rab).
2) K[j]<>K[i] и ng>vg – ключи не совпали, а длина последней подтаблицы равна 1. В этом случае местом для вставки является позиция ng, поэтому записи R[ng], R[ng+1], … , R[j-1] должны быть сдвинуты на одну позицию вправо (R[ng]=Rab).

Алгоритм бинарного поиска подробно описан в разделе "Дихотомический поиск по совпадению".
Рассмотрим на примере j-й шаг сортировки (определяется место записи с ключом, равным 9; j=7, K[j]=9):

Среднее число сравнений для данного метода составляет n log2(n).
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
Главная страница