Объектно-ориентированное программирование.

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

Основное понятие объектного программирования – объект – при первом приближении похож на процедуру. Однако процедура выполняет, заложенные в ней действия, когда ее вызывают из основной программы. Объект же может вести себя вполне независимо.

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

Декларативно-ориентированное программирование.

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

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

 

 

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

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

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

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

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

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

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

3. Важной характеристикой предписаний является однозначность их восприятия. Они называются определенностью или детерминированностью.

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

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

Алгоритм постулирует общие требования:

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

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

ü Алгоритм должен быть единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальным.

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

 

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

 

Машина Поста

Пост рассматривает общую проблему, состоящую из множества конкретных проблем, при этом решением общей проблемы является такое решение, которое доставляет ответ для каждой конкретной проблемы. Например, решение уравнения 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