Описания комбинаторных алгоритмов

Скачать 0.87 Mb.

Название	Описания комбинаторных алгоритмов
страница	2/13
Тип	Документы

rykovodstvo.ru > Руководство эксплуатация > Документы

1 2 3 4 5 6 7 8 9 ... 13

Содержание

ЧАСТЬ 1. АЛГОРИТМЫ СОРТИРОВКИ 2

1. Методы вставки. Алгоритм простых вставок 2

1.1. Бинарные вставки 3

1.2. Двухпутевые вставки 4

1.3. Вставки одновременно нескольких элементов 5

1.4. Вставки с убывающим шагом (метод Шелла) 6

1.5. Вставки в связанный список 9

1.6. Вставки в несколько связанных списков 10

2. Обменная сортировка 11

2.1. Метод пузырька 11

2.2. Модификация метода пузырька 12

2.3. Быстрая сортировка 12

2.4. Обменная поразрядная сортировка 16

2.5. Параллельная сортировка Бэтчера 18

3. Сортировка посредством выбора 21

3.1. Использование связанного списка для хранения информации о промежуточных максимумах 22

3.2. Пирамидальная сортировка 23

4. Сортировка посредством слияния 27

4.1. Естественное двухпутевое слияние 27

4.2. Простое двухпутевое слияние 29

4.3. Слияние связанных списков 31

5. Распределяющая сортировка 33

ЧАСТЬ 2. АЛГОРИТМЫ ПОИСКА 37

6. Последовательный поиск 37

6.1. Последовательный поиск по связанному списку 37

6.2. Последовательный поиск с перестановкой элементов 37

6.3. Последовательный поиск в упорядоченном файле 37

6.4. Бинарный поиск в упорядоченном файле 38

6.5. Однородный бинарный поиск 38

6.6. Интерполяционный поиск 39

7. Поиск по бинарным деревьям 39

7.1. Поиск по бинарному дереву 39

7.2. Удаление из бинарного дерева 40

7.3. Построение оптимальных бинарных деревьев поиска 42

7.4. Цифровой поиск по дереву 43

7.5. Цифровой поиск для длинных ключей, хранимых в текстовом массиве (Патриция) 43

ЧАСТЬ 1. АЛГОРИТМЫ СОРТИРОВКИ

1. Методы вставки. Алгоритм простых вставок

Сортировка вставками – простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как Быстрая сортировка), у него есть ряд преимуществ:

- прост в реализации;

- эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;

- эффективен на наборах данных, которые уже частично отсортированы;

- это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);

- может сортировать список по мере его получения;

- не требует временной памяти, даже под стек.

Алгоритм использует прием, которым пользуются игроки в карты при сортировке только что розданной колоды: очередная карта вставляется между уже упорядоченными ранее.

На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.

Файл, подлежащий сортировке, в общем случае состоит из элементов-записей, включающих информационную часть и ключи, по которым производится упорядочение по возрастанию. Поскольку информационная часть почти не влияет на процесс сортировки, будем предполагать, что файлы, используемые в примерах, состоит только из элементов-ключей, а информационная часть записи отсутствует. Здесь k[1], k[2], ... , k[N] - ключи, по которым производится упорядочение файла. X,i,j - рабочие переменные.

for j:=2 to N do begin

i:=j-1;

X:=k[j];

while (X0) begin

k[i+1]:=k[i];

i:=i-1;

end;

k[i+1]:=X;

end

Блок-схема алгоритма будет выглядеть так:

Для примера возьмем файл, состоящий из 8 элементов:

Исх.файл.: 503 87 512 61 908 170 897 275

Алгоритм будет преобразовывать его следующим образом:

j=2 503 87 X= 87

Результат: 87 503

j=3 87 503 512 X=512

j=4 61 87 503 512 X= 61

j=5 61 87 503 512 908 X=908

j=6 61 87 170 503 512 908 X=170

j=7 61 87 170 503 512 897 908 X=897

j=8 61 87 170 275 503 512 897 908 X=275

Время работы алгоритма t примерно оценивается формулой:

t=a*N² + b*N,

где a,b - неизвестные константы, зависящие от программной реализации алгоритма.

Таким образом, время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим - массив, отсортированный в порядке, обратном нужному.

Алгоритм простых вставок порождает несколько модификаций.

1 2 3 4 5 6 7 8 9 ... 13

Похожие:

	Об использовании проблемно-ориентированных языков программирования... В статье рассматривается один из возможных подходов к проблемам проектирования лингвистических алгоритмов и к способам организации...		Отдела боевых алгоритмов и программ В 77 Воспоминания военных программистов отдела боевых алгоритмов и программ рлс до «Дунай-3» системы про а-35. М.: Издательство «Перо»,...
	Кормен Т.,Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание Целями освоения данной дисциплины являются как получение теоретических знаний в области организации структур данных и базовых вычислительных...		Исследование алгоритмов идентификации для систем бездатчикового векторного... Разработка и исследование алгоритмов идентификации и векторного управления в асинхронном электроприводе
	Программа вступительного экзамена для направления подготовки магистров... Рам) и языке высокого уровня. Временная и емкостная сложность алгоритмов для разных представлений. Сложность в среднем и наихудшем....		Разработка формализованного описания процессов сбора, обработки и... Данная работа посвящена разработке формализованного описания Банковских процессов средствами uml
	Руководство по оформлению описания плаката на конференцию Павт (документ ms word)* Описание плаката (с текстом в объеме одной страницы формата А4) содержит информацию о планах и начальных результатах недавно начатого...		Пример описания технических требований системного блока №1 2 2 Пример... Устройство бесперебойного питания для рабочих станций. Типовая конфигурация №1 22
	Пример описания технических требований системного блока №1 2 2 Пример... Устройство бесперебойного питания для рабочих станций. Типовая конфигурация №1 22		Пример описания технических требований системного блока №1 2 2 Пример... Устройство бесперебойного питания для рабочих станций. Типовая конфигурация №1 21
	Пример описания технических требований системного блока №1 2 2 Пример... Устройство бесперебойного питания для рабочих станций. Типовая конфигурация №1 17		Пример описания технических требований системного блока №1 2 2 Пример... Устройство бесперебойного питания для рабочих станций. Типовая конфигурация №1 17
	Конспект урока на тему: «Робот lego mindstorms ev3 исполнитель циклических... Конспект урока на тему: «Робот lego mindstorms ev3 – исполнитель циклических алгоритмов»		Исследование аппроксимационных алгоритмов решения обратных задач технической диагностики
	Разработка и исследование алгоритмов идентификации и векторного управления...		При обучении биологии Составление алгоритмов для формирования и развития умений и мыслительных операций

Руководство, инструкция по применению