Специальные главы по информатике.

Специальные главы по информатике.

Алгоритмы и структуры данных

Оглавление

Стили программирования. 3

Формализация понятия алгоритма. Машина Поста и Тьюринга. 9

Методы анализа алгоритмов. Эффективность алгоритмов. 18

Алгоритмы сортировки. 23

Внутренняя сортировка. 23

Пузырьковая сортировка. 24

Сортировка вставками. 25

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

Сортировка Шелла. 27

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

Сортировка слиянием.. 33

Внешняя сортировка. 36

Внешняя многофазная сортировка слиянием.. 36

Структуры данных. 40

Массив как базовая структура. 41

Простейшие структуры данных. 44

Стек. 44

Стековый калькулятор и обратная польская запись формулы.. 46

Очередь. 49

Ссылочные реализации структур данных. 52

Списки. 54

Деревья и графы.. 59

Множества. 62

Бинарное дерево поиска. 64

Красно-черные деревья, AVG-деревья. 65

Хеширование. 68

Пирамиды и пирамидальная сортировка. 71

Алгоритмы поиска. 75

Метод двоичного поиска. 76

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

Динамическое программирование. 78

«Жадные алгоритмы». 79

Поиск с возвратом. 79

Поиск лексической информации. 80

Литература. 80

 

 

Стили программирования

В настоящее время создание алгоритмов – написание программ для ЭВМ – вид человеческой деятельности. Подходы к разработке алгоритмов в ходе эволюции компьютеров существенно изменялись.

На первом этапе в эпоху ЭВМ 1-го и 2-го поколения требования к алгоритмам были весьма жесткими:

· Использовать наименьшее возможное число ячеек оперативной памяти;

· Минимальное число операций.

Программы были ориентированы на работу непосредственно процессора и составлялись из соответствующих команд:

· Операции присваивания;

· Простейшие арифметические операции;

· Операции сравнения чисел;

· Операторы условного и безусловного перехода;

· Операторы вызова подпрограмм.

Такой подход создания алгоритмов, ориентированных на непосредственное выполнение компьютером операций, принято называть операционным (язык низкого уровня Assembler). Программы составленные подобным образом весьма экономичны. К недостаткам данного подхода можно отнести запутанность структуры программы из-за злоупотребления командами условного и безусловного перехода, трудности при отладке программ и их модификации. Все это приводило к огромной трудоемкости программирования и высокой цене.

Процедурно – ориентированное программирование сейчас продолжает развиваться и в сторону параллельного программирования. Логика решения множества задач допускает одновременное выполнение нескольких операций, приводящей к увеличению эффективности. Развитие многопроцессорных компьютеров делает возможным создание параллельных алгоритмов.

 

С появлением массовых ЭВМ 3-го поколения подтолкнуло к разработке новых методологий программирования. Появившийся в начале 1970-х новый подход к разработке алгоритмов получил название структурного.

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

В основе технологических принципов структурного программирования лежит утверждение о том, что логическая структура программы может быть выражена комбинацией трех базовых структур: следования, ветвления и цикла (это содержание теоремы Бема-Якопини).

1. Следование илилинейная – сама важная из структур. Она означает, что действия могут быть выполнены друг за другом.

Линейная структура может быть как из отдельных команд, так и из множеств операторов.

 

 

2. Ветвление. – этоструктура, обеспечивающая выбор между двумя альтернативами. Происходит проверка условия, а затем происходит выбор пути дальнейшего действия.

 

 

3. Циклы или повторения предусматривают повторное выполнение некоторого набора команд программы. Циклы связаны с проверкой логических условий. Пока условие сохраняет свое значение происходит выполнение цикла, а при его изменении происходит передача выполнения по программе дальше.

 

Цикл с «предусловием».

 

Цикл с «постусловием».

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

Модульность. – прием структурного подхода к разработке алгоритма. Модуль – это последовательность логически связанных операций, оформленная как отдельная часть программы, не зависящая от других частей. Использование модулей имеет ряд преимуществ:

· Возможность создания программы несколькими программистами;

· Простота проектирования и последующих модификаций программ;

· Упрощение отладки и поиска ошибок;

· Возможность использовать готовых библиотек наиболее употребительных модулей.

Комбинируя эти модули- подпрограммы, удается формировать итоговый алгоритм уже не из простых операторов, а из законченных блоков – модулей, имеющих определенную смысловую нагрузку и обращаться к ним по названиям.

Важным достижением структурного подхода к разработке алгоритмов является нисходящее проектирование программ, основанное на идее уровней абстракции, которые становятся уровнями модулей в разрабатываемой программе. На этапе проектирования строится схема иерархии, изображающие эти уровни. Схема иерархии позволяет разработчику сначала определить, что надо сделать в программе. А лишь затем, как это надо делать. При нисходящем проектировании исходная, подлежащая решению задача разбивается на ряд подзадач, подчиненных по своему содержанию главной задаче. Такое разбиение называется детализацией или декомпозицией.

На следующем этапе происходит дальнейшая детализация до уровня небольших подзадач. Которые требуют для решения небольших модулей в 3-5 строчки.

Структурное программирование, наиболее отчетливо выраженное в языке Паскаль (PASCAL), возникло в ходе развития процедурно-ориентированного подхода, заложенного в исторически первом из языков программирования – Фортране (FORNRAN). В языках данной группы программист описывает действия для реализации необходимого процесса, используя понятия команд (операторов) и данных.

Структурирование программы – это разбивка на отдельные подпрограммы. В каждом модуле может находиться произвольное количество подпрограмм.

Подпрограммы – общее название для процедур и функций - представляют собой инструмент языка, позволяющий писать хорошо структурированные программы. В структурированных программах обычно легко прослеживается основной алгоритм, их проще понять и легче отлаживать, они менее чувствительны к ошибкам программирования. Все эти свойства являются следствием важной особенности подпрограмм, каждая из которых представляет собой самостоятельный фрагмент программы, связанный с основной лишь с помощью нескольких параметров.

Практически во всех языках программирования имеются средства структурирования. Соответственно такие языки называют процедурно-ориентированные. Pascal относится к таким языкам.

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

 

Машина Поста

Пост рассматривает общую проблему, состоящую из множества конкретных проблем, при этом решением общей проблемы является такое решение, которое доставляет ответ для каждой конкретной проблемы. Например, решение уравнения 5 х + 4 = 0 – это одна из конкретных проблем, а решение уравнения а х + b = 0 – это общая проблема, тем самым алгоритм должен быть универсальным. Т.е. должен быть соотнесен с общей проблемой.

Абстрактная машина Поста представляет собой бесконечную информационную ленту, разделенную на позиции – клетки. В каждой клетке стоять метка или отсутствовать таковая. Вдоль ленты движется каретка. Она может передвигаться шагами вправо или влево, проверять наличие метки в клетке, наносить метку в пустую клетку или стирать имеющуюся метку. Исполнитель обладает определенной системой возможных команд, которые однозначно им понимаются, на работу с данными – определенной расстановкой меток в позициях информационной ленты.

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

Машина Поста определяет расстановка меток в позициях информационной ленты. В результате действия машины Поста нужно:

ü переместить каретку влево или вправо;

ü определить, клетка пустая или помеченная;

ü стереть метку в текущей клетке;

ü поставить метку в пустую текущую клетку;

ü остановить машину.

Язык машины Поста:

1. N. - номер текущей команды;

2. M. - номер следующей команды;

3. N. → M. - переместить каретку вправо на одну ячейку;

4. N. ← M. - переместить каретку влево на одну ячейку;

5. N. ● M.- поставить метку в текущую ячейку;

6. N. ● M. стереть метку в текущей ячейке;

7. - определить, клетка пустая или помеченная;

8. N.! остановка машины.

Задачи для самопроверки.

В задачах считается, что N расположенных подряд меток обозначают число N. Напишите и самостоятельно исполните программу машины Поста.

 

1. Вычитание двух чисел, записанных на ленте и разделенных друг от друга пустой клеткой. Начальное положение каретки под этой разделяющей пустой клеткой. Уменьшаемое – не меньше вычитаемого.

2. Сложение двух чисел, записанных на ленте и разделенных друг от друга пустой клеткой. Начальное положение каретки под этой разделяющей пустой клеткой.

3. Вычитание двух чисел, записанных на ленте и разделенных друг от друга произвольным количеством пустых клеток. Начальное положение каретки под последней не пустой клеткой первого числа. Уменьшаемое – не меньше вычитаемого.

4. Сложение двух чисел, записанных на ленте и разделенных друг от друга произвольным количеством пустых клеток. Начальное положение каретки под последней не пустой клеткой первого числа.

5. Деление одного числа, записанного метками, на 2. Начальное положение каретки под последней не пустой клеткой числа. Указание: справа от пустой клетки поставить метку, а слева стирать по две метки до тех пор, пока слева остаются метки.

6. Умножение числа на 2, записанного на ленте метками. Начальное положение каретки под первой непустой клеткой числа. Указание: через одну пустую клетку поставить две метки, а из исходного числа стереть одну и т.д.

7. Умножение двух чисел, отмеченных метками на ленте и разделенных пустой клеткой. Начальное положение каретки под разделяющей пустой клеткой.

8. Деление числа на 2. Проверяемое число должно делиться на 2 без остатка. Стирайте каждую вторую метку, а оставшиеся метки уплотнить. Начальное положение каретки под первой непустой клеткой числа.

9. Дан массив меток. Каретка обозначает первую пустую секцию перед началом массива. Раздвиньте массив так, чтобы после каждой метки была пустая секция.

10. Разделить число на 5. Начальное положение каретки под первой непустой клеткой числа.

 

Машина Тьюринга

Машину Тьюринга (МТ) также используют для изучения свойств алгоритмов. Она содержит счетную ленту, разделенную на ячейки, но ограниченную слева (для анализа аварийных ситуаций и выполнения предписаний об остановке); читающую и пишущую головку; лентопротяжный механизм и исполнительное операционное устройство. Это устройство может находиться в одном из дискретных состояний q0, q1,…., qs, принадлежащих некоторой конечной совокупности – алфавиту внутренних состояний. При этом q0 определяется как начальное состояние.

Каждая ячейка ленты в каждый момент времени занята буквой из множества рабочего алфавита А =(а0, а1,…,аt). Отсутствие буквы также является буквой – «пробелом» и обозначается за а0. Соответственно головка в каждый момент времени находится над некоторой ячейкой ленты, являющейся текущей, и может читать буквы, стирать или печатать их. Лентопротяжный механизм перемещает ленту, и головка оказывается над соседней ячейкой.

Машина Тьюринга начинает работу работать из некоторой начальной конфигурации, включающей в себя начальное состояние и положение считывающее – записывающей головки над определенной ячейкой ленты.

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

Различные алгоритмы осуществляются на различных машинах Тьюринга, отличающихся наборами команд, внутренним и внешним алфавитами. Можно построить универсальную машину Тьюринга, способную выполнять любой алгоритм любой машины Тьюринга. Это достигается путем кодирования конфигурации и программы любой данной машины Тьюринга в символах внешнего алфавита универсальной машины. Само кодирование должно выполняться следующим образом:

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

2. строки кодовых записей должны однозначно разбиваться на отдельные кодовые группы;

3. должна иметься возможность распознать кодовые группы, соответствующие командам. Различать кодовые группы, соответствующие символам внешнего алфавита и внутренним состояниям.

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

Алгоритмы Маркова

Для формализации понятия алгоритма российский математик А.А.Марков предложил использовать ассоциативные исчисления.

Основными его понятиями являются алфавит, как конечный набор символов – букв, конечная линейная последовательность букв – слово и допустимая система подстановка. Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок.

Слова Р1 и Р2 в некотором ассоциативном исчислении будут смежными, если одно из них может быть преобразовано в другое однократным применением допустимой подстановки. Последовательность рядом стоящих смежных слов образуют дедуктивную цепочку, ведущую от начального Р слова к конечному М, посредством промежуточных:

Р, Р1, Р2, Р3,……, М. Соответственно слова Р и М будут эквивалентными при наличии данной цепочкой.

Любой процесс вывода формул, математические выкладки и преобразования также являются дедуктивными цепочками в некотором ассоциативном исчислении. Построение ассоциативных исчислений является универсальным методом детерминированной переработкой информации и позволяет формализовать понятие алгоритма.

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

Алфавит А	Система подстановок В
А={а,b,с}	cb-cc
cca-ab
ab-bca

Предписание о применении подстановок: в произвольном слове Р надо сделать возможные подстановки, заменив левую часть подстановок на правую; повторить процесс с вновь полученным словом.

babaac®bbcaaac ® остановка т.к. нет подстановки.

bcacabc® bcacbcac ® bcacccac ®bcacabc ® бесконечный процесс т.к. пришли к исходному слову.

Предложенный А.А.Марковым способ уточнения понятия алгоритма основан на понятии нормального алгоритма. Его определяют так. Пусть задан алфавит А и система подстановок В. Для произвольного слова Р подстановки из В подбираются в том же порядке, в каком они следуют в В. Если подходящей подстановки нет, то процесс останавливается. В противном случае берется первая из подходящих подстановок и производится замена ее правой частью первого вхождения ее левой части в Р. Затем все действия повторяются для получившегося слова Р1. Если применяется последняя подстановка из системы В, процесс останавливается. Такой набор предписаний вместе с алфавитом и набором подстановок В определяют нормальный алгоритм и определены ситуации остановок алгоритма.

Нормальный алгоритм Маркова можно рассматривать как универсальную форму задания любого алгоритма. Универсальность нормальных алгоритмов декларируется принципом нормализации: для любого алгоритма в произвольном конечном алфавите А можно построить эквивалентный ему нормальный алгоритм над алфавитом А.

Возможны соответственно различные способы композиции нормальных алгоритмов:

1. Суперпозиция алгоритмов. При суперпозиции двух алгоритмов А и В выходное слово первого алгоритма рассматривается как входное слово второго алгоритма В.

2. Объединение алгоритмов. Объединением алгоритмов А и В в одном и том же алфавите называется алгоритм С в том же алфавите, преобразующим любое слово р, содержащееся в области определения алгоритмов А и В, в записанные рядом слова А(р) и В(р).

3. Разветвление алгоритмов. Разветвлением алгоритмов представляет собой композицию D трех алгоритмов А, В, и С, причем область определения алгоритма D является пересечением областей определения всех трех алгоритмов А, В и С, а для любого слова р из этого пересечения D(p) = A(p), если C(p) = e, D(p)= B(p), если C(p) = e, где е – пустая строка.

4. Итерация алгоритмов. Итерация (повторение) представляет собой такую композицию С двух алгоритмов А и В, что для любого входного слова р соответствующее слово С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое словом В.

Алгоритма Маркова также нашли применения в качестве основы специализированного языка программирования, применяемого как язык символьных преобразований при разработке систем искусственного интеллекта.

 

Методы анализа алгоритмов. Эффективность алгоритмов.

Алгоритм – это набор команд для выполнения определенной задачи. Для написания компьютерных алгоритмов используется формализованный стиль (однозначность понимания команд, понятность и т.д.). Алгоритмы были формализованы еще тысячи лет назад. Евклид описал алгоритмы для деления углов пополам, проверки равенства треугольников и решения других геометрических задач. Он начал с небольшого словаря аксиом («параллельные прямые не пересекаются») и создал на их основе алгоритмы для решения более сложных задач. Такие формализованные алгоритмы хорошо подходят для решения математических задач, где нужно доказать истинность каких – либо положений и т.д., при этом скорость алгоритма не имеет значения. При решении же реальных задач (сортировку миллиона записей) эффективность алгоритма становится критерием оценки алгоритма.

При оценке эффективности алгоритма необходимо учитывать много характеристик. Из особенностей компьютерных программ алгоритм оценивается как с точки зрения скорости, так и с точки зрения используемой памяти. Таким образом, находится компромисс между этими показателями.

Критерий памяти поднимался в разные периоды развития компьютеров от принципиального значения на ранних этапах развития. Например, вещественное число в интервале от –10 до +10 с одним десятичным знаком после запятой при записи виде вещественного числа займет от 4 до 8 байтов. Однако, если предварительно умножить это число на 10 и записать его как целое в интервале -100 до +100, то для его хранения потребуется 1 байт. Необходимость экономить память и привела к проблеме 2000 года. Когда значения дат, а именно год в целях экономии усекали до двух цифр 99 вместо 1999.

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

При анализе алгоритма определяется количество «времени», необходимое для его выполнения. Это не реальное число секунд, а приблизительное число операций, выполняемых алгоритмом. Таким образом, будем называть «временем» вычислительную сложность алгоритма.

При анализе алгоритма выбор входных данных может существенно повлиять на его выполнение. Будем ли мы искать нужное значение в отсортированном списке или в неупорядоченном. Поэтому необходимо оценивать эффективность алгоритма на всех возможных наборах данных, которые обеспечивают как самое быстрое и медленное (наихудшее) выполнение алгоритма.

Наилучший случай для алгоритма – такой набор данных, на котором алгоритм выполняется за минимальное время. Целевое значение при поиске располагается в первой проверяемой ячейке. Время выполнения будет наименьшим и мало информативным.

Анализ наихудшего случая чрезвычайно важен, так как позволяет оценить максимально время работы алгоритма. В этом случае необходимо найти такие входные данные, на которых алгоритм будет выполнять больше всего работы. При поиске – эта та ситуация, когда целевой элемент находится в последней проверяемой ячейки или вообще отсутствует в списке.

Точное знание количества операций, выполненных алгоритмом, не играет существенной роли в анализе алгоритмов. Более важным оказывается скорость роста этого числа при возрастании объема входных данных. Разные функции при увеличении значения аргумента ведут себя по-разному. Но их можно объединить в классы.

Нас интересует общий характер поведения алгоритмов, а не подробности этого поведения. Поэтому при анализе алгоритмов нас интересует класс скорости роста, к которому относится алгоритм.

При оценки эффективности пользуются классом функций О(f). Алгоритм имеет сложность О(f(N)) (О большое F от N), если с увеличением размерности исходных данных N время выполнения алгоритма возрастает с той же скоростью, что и функция f(N).

Например, сортируем N положительных чисел.

For i = 1 to N

MaxValue = 0 ‘ Нахождение максимального элемента

For j = 1 to N

If Value(j) > MaxValue Then

MaxValue = Value(j)

Maxj = j

EndIf

Next j

Print MaxValue ‘ печать найденного элемента

Value(Maxj) = 0 ‘ обнуление найденного элемента для исключения его из дальнейшего поиска

Next i

В этом алгоритме два цикла –один вложен в другой. Во время каждой из N – итераций внешнего цикла внутренний цикл выполняется N раз. Общее количество итераций N*N или N² . Это определяет сложность алгоритма О(N²) (пропорциональна N²). Сложность этого алгоритма растет с той же скоростью, что и N².

Правила позволяющие оценить сложность алгоритма:

ü Необходимо использовать только ту часть уравнения рабочего цикла, которая возрастает быстрее. Например. Рабочий цикл представлен формулой N³ + N. В этом случае его сложность будет О(N³). При больших значениях N первая часть доминирует и вся функция сравнима с N³.

ü Постоянные множители можно не учитывать. Алгоритм с рабочим циклом 3* N² рассматривается как О(N²).

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

Сложность рекурсивных процедур зависит от количества итераций. Если процедура содержит рекурсионный вызов, то сложность алгоритма O(N). Если же процедура содержит несколько рекурсионных вызовов, то это многократная рекурсия и оценить ее сложность труднее. Если у нас есть в процедуре два рекурсионных вызова

Sub Recursio(N)

If N<= 0 then end

Recursio(N – 1) ‘рекурсионный вызов

Recursio(N – 1) ‘рекурсионный вызов

End sub

 

Если количество итераций при входном значении N равно T(N), то Т(0) = 1 – программа закончит свою работу на первом шаге. Для больших N процедура запускается дважды, количество итераций равно 1+2*T(N-1). При рассмотрении значений, можно заметить, что если T(N)=2^N+1-1, то рабочий цикл процедуры будет равен О(2^N).

Для рекурсивных процедур важна объемная сложность. Объем занятой памяти может увеличиться при увеличении последовательных рекурсионных вызовов. Такой поверхностный анализ необходимо проводить

 

Подводя итог. Сможет ли алгоритм работать быстрее, зависит от того, как его используют. Если запускаете редко с малыми объемами данных, то и производительность О(N²) вполне приемлема. Если же алгоритм выполняется в интерактивном режиме с большими объемами данных недостаточно и О(N).

Обычно алгоритмы со сложностью N*log(N) работают с очень хорошей скоростью. Вычислительная сложность алгоритмов, порядок которых определяется C^N и N! Очень велика, поэтому эти алгоритмы пригодны для задач с очень малым объемом перерабатываемой информацией.

Иногда лучшим способом для определения наиболее эффективного алгоритма является тестирование.

 

Задания для самопроверки

1. Напишите на псевдокоде алгоритм, подсчитывающий количество прописных букв в текстовом файле. Сколько сравнения требуется этому алгоритму?

2. Напишите алгоритм, не использующий сложных условий, который по трем введенным целым числам определяет, различны ли они все между собой. Сколько сравнений в среднем делает алгоритм при различных наборах входных данных?

3. Напишите алгоритм для поиска второго по величине элемента в списке из N значений. Сколько сравнений делает алгоритм в наихудшем случае?

 

 

Алгоритмы сортировки

 

Сортировкой, или упорядочиванием списка объектов называется расположение этих объектов по возрастанию или убыванию согласно определенному линейному отношению порядка, такому как отношение «≤» для чисел.

Средства языка программирования позволяют сортировать не только числа, но и строки. При этом они выстраиваются в лексикографическом порядке, в соответствии с алфавитом. Одна строка считается больше другой, если при их просмотре слева направо и отсечении у них по одному символу оказывается, что код ASCII символа первой строки больше кода ASCII символа второй строки.

Различают внешнюю и внутреннюю сортировку. При внутренней сортировке все сортируемые данные помещаются в оперативную память компьютера, где можно получить доступ к данным в любом порядке, т.е. используется модель памяти с произвольным доступом. Внешняя сортировка применяется тогда, когда объем упорядочиваемых данных слишком большой, чтобы все данные можно было поместить в оперативную память. При внешней сортировке приходится решать вопросы, связанные с перемещением больших блоков данных от устройства внешнего хранения данных к оперативной памяти и обратно.

Внутренняя сортировка

Существует несколько алгоритмов сортировки. Они отличаются друг от друга сложностью и быстротой работы или эффективностью, т.е. зависимостью времени работы алгоритма от длины сортируемого массива. Как правило, чем более эффективно работает алгоритм, тем он сложнее.

Простые схемы сортировки

Среди простых способов можно отметить «наивную» сортировку. При этом способе производятся все возможные перестановки элементов массива. Для каждого варианта перестановки проверяется, удовлетворяет ли он условию упорядоченности. Все перестановки элементов массива можно создать при помощи рекурсионного процесса. Очевидно, что алгоритм работает очень медленно.

Пузырьковая сортировка

Самым простым методом сортировки является так называемый метод «пузырька»/ «камушка». Основную идею этого метода можно представить следующим образом. Массив, элементы которого будем упорядочивать, расположим вертикально. Элементы с наименьшими значениями более «легкие» и «всплывают» вверх наподобие пузырька. При первом проходе вдоль массива, начиная проход сверху, берется первый элемент массива и поочередно сравнивается со значениями последующих элементов. При встрече с более «легким» они меняются местами, и тот становится «эталоном», с которым происходит дальнейшее сравнение. В результате наименьший элемент массива оказывается на самом верху массива. Во время второго прохода вдоль массива находят второй по значению элемент и располагают его под элементом, найденным во время предыдущего прохода. При i-том проходе не проверяются элементы выше i –той, т.к. они имеют значения, меньшие, чем у оставшихся элементов массива.

BubbleSort1 (list,N)

For i=1 To N-1

For j=i+1 To N

If LIST(i) > LIST(j) Then

Call Swap(LIST(i),LIST(j))

End If

Next j

Next i

END

‘х и у меняются своими значениями

Private Sub Swap (x,y)

z=x

x=y

y=z

End

 

Другой вариант метода "пузырька" основан на сравнении соседних элементов. При каждом проходе ближе к своему месту продвигаются сразу несколько элементов, хотя гарантированно занимает окончательное положение лишь один. Этот способ позволяет прекратить дальнейшее сравнение. если перестановок на предыдущем шаге не было.

BubbleSort2 (list,N)

numberOfPairs=N ' число перестановок

swappedElemens= true ' флаг отслеживающий наличия перестановок

While swappedElements do

numberOfPairs= numberOfPairs-1

swappedElemens= false

for i=1 to numberOfPairs do

if list[i] > list[i+1] then

Swap(list[i], list[i+1])

swappedElemens= true

endIf

end For

end While

end

Эффективность алгоритма О(N²)

Пузырьковый метод наиболее прост, но и менее эффективен, чем другие методы. Он подойдет в тех случаях, когда упорядочивается уже почти упорядоченный массив – массив с локальным нарушением порядка.

 

Сортировка вставками.

Дана последовательность чисел A₁, A₂, A₃........... A_n. Требуется переставить числа в порядке возрастания. Пусть A₁, A₂, A₃,.......A_i-1 – упорядоченная последовательность, т.е. A₁ ≤ A₂ ≤ A₃,......... ≤. A_i-1 Оставшаяся часть последовательности A_i, A_i+1, A_i+2,....... A_n.. На i-том этапе мы вставляем A_i-1 в нужную позицию среди упорядоченных элементов последовательности. После этой вставки первые i элементов будут уже упорядочены.

For i =2 to n ‘Последовательность из 1-го элементом упорядочена

‘ переместить Ai на позицию j ≤ i такую, что

A_k < A_i ‘ для j ≤ k < i последовательность возрастающая и

Либо A_j-1 < A_i, либо j=1

Процесс производится до тех пор, пока все элементы от i до n не будут перебраны.

InsertionSort(list,N)

for i=2 to N do

newElement=list[i]

location=i-1

while (location >=1) and (list[location]>newElement) do

//сдвигаем все элементы, большие очередного

list[location+1]= list[location]

location= location-1

endWhile

list[location]=newElement

end for

end

 

Эффективность алгоритма О(N²)

Этот алгоритм можно реализовать также через рекурсию. Во время рекурсивного спуска никаких действий не совершается. Очередной рекурсионный вызов осуществляется с укорочением массива на один элемент (отсекаем каждый раз последний элемент). Условием окончания рекурсии – укороченный массив будет содержать всего один элемент. Начинается процесс рекурсионного подъема, во время которого отсортировываем укороченный массив. В отсортированный массив вставляем отделенный элемент: просматривается весь массив, чтобы найти место вставки, а затем все элементы массива, стоящие после этого места, перемещаются на одну позицию вправо. Вставляемый элемент занимает свое свободное место.

 

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

Сортировка посредством выбора также достаточно проста. Ищем номер максимального элемента массива. На его место помещается последний элемент массива и соответственно максимальный на последнее место. Затем просматривается уже укороченный массив без последнего элемента, т.к.на последнем месте стоит уже элемент, имеющий максимальное значение, и ищется максимальный элемент среди оставшейся части. Производится обмен и т.д. Процесс завершается, когда длина последнего остатка не станет равной единицы.

Можно для реализации данного алгоритма использовать рекурсию.

Сортировка посредством выбора без использования рекурсии и будем искать для разнообразия элемент с минимальным значением среди A_i, A_i+1, A_i+2,....... A_n. Соответственно записи после i-го этапа последовательность A₁, A₂, A₃,.......A_i будет упорядочена.

Chose(List,N)

For i = 1 To N-1

indexOfMin = i

min = List[i]

For j = i+1 To N

If List[j] < min Then

min = List[j]

indexOfMin = j

End If

Call Swap(List [i), List [indexOfMin])

Next j

Next i

End

Сортировка Шелла

Эту сортировку придумал Дональд Л.Шелл. В ней весь список рассматривается как совокупность перемешанных подсписков. На первом шаге эти подсписки представляют собой просто пары элементов. На втором шаге в каждой группе по четыре элемента. При повторении процесса число элементов в каждом подсписке увеличивается, а число подсписков уменьшается. Сортировка в подсписках на каждом шаге выполняется путем однократного применения сортировки вставками.

Алгоритм сортировки Шелла

ShellSort(list, N)

//list сортируемый список элементов N число элементов в списке

passes = [log_2 N] // целая часть

while (passes >= 1) do

increment = 2^passes-1 // 2 ^passes-1

for start = 1 to increment do

InsertionSort(list, N, start, increment)

end for

passes = passes - 1

end while

end

Переменная increment содержит величину шага между номерами элементов подсписка. (На рисунке шаг принимает значения 8, 4, 2 и 1.) В алгоритме мы начинаем с шага, на 1 меньшего наибольшей степени двойки, меньшей, чем длина списка. Поэтому для списка из 1000 элементов первое значения шага равно 511. Значение шага также равно числу подсписков. Элементы первого подсписка имеют номера 1 и 1 + increment; первым элементов последнего подсписка служит элемент с но