Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Топ:
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного...
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Интересное:
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Дисциплины:
2017-10-11 | 219 |
5.00
из
|
Заказать работу |
|
|
Рассмотрим один из простейших алгоритмов сортировки сравнениями: так называемую пузырьковую сортировку.
Алгоритм «Пузырьковая сортировка»
1. Повторять:
А. Для всех элементов списка, кроме последнего, повторять:
1. Если текущий элемент больше следующего, то поменять их местами.
2. Конец цикла при условии, что ни одной замены не произошло.
Проиллюстрируем работу алгоритма на примере последовательности из 5-ти чисел: 5, 3, 1, 4, 2. Работа алгоритма пузырьковой сортировки проиллюстрирована на следующем рисунке.
► | 5┐ | ► | 3┐ | ► | |||||||||||||||||||||||||||
3┘ | ► | 5┐ | 1┘ | ► | ► | 3┐ | |||||||||||||||||||||||||
1┘ | ► | 5┐ | ► | 4┐ | 2┘ | ► | |||||||||||||||||||||||||
4┘ | ► | 5┐ | 2┘ | ► | ► | ||||||||||||||||||||||||||
2┘ |
Видно, что на каждом шаге внешнего цикла самый большой элемент перемещается в конец списка. При этом не обязательно просматривать весь список каждый раз, так как на каждом шаге последний элемент оказывается на своем месте. В связи с этим на каждом шаге можно просматривать на один элемент меньше, и алгоритм можно модифицировать.
|
Алгоритм «Пузырьковая сортировка»
1. Присвоить переменной k количество элементов списка.
2. Повторять:
А. Уменьшить k на 1.
Б. Для первых k элементов списка повторять:
1. Если текущий элемент больше следующего, то поменять их местами.
3. Конец цикла, при условии, что ни одной замены не произошло.
Сколько времени будет выполняться такая сортировка? За элементарную операцию примем операцию сравнения двух элементов и подсчитаем, сколько таких операций необходимо произвести, если дан список из n элементов. На каждом шаге будет просматриваться на один элемент меньше. В худшем случае (когда исходный массив отсортирован по убыванию) каждый раз будет производиться хотя бы один обмен элементов, пока не останется только один элемент, и сортировку не закончится. На первом шаге будет сделано n -1 сравнение, на втором n -2 сравнения, и т.д. до одного сравнения. Итого, имеем арифметическую прогрессию от 1 до n -1 с n -1 элементом. Сумма этой прогрессии:
.
При больших значениях n эта функция ведет себя как n2. В таком случае говорят, что вычислительная сложность алгоритма равна O (n2). Эта оценка вычислительной сложности алгоритма называется асимптотической. Такая оценка обычно является достаточно плохой. Возникают вопросы: можно ли написать алгоритм, который будет работать быстрее и какой самый быстрый алгоритм вообще можно написать? Ответ – можно, и это . Невозможно написать более быстрый алгоритм сортировки сравнениями. Для лексикографической сортировки наиболее быстрый алгоритм имеет вычислительную сложность .
При сортировке для обмена элементов списка можно использовать дополнительную переменную.
Пример (см. пример из параграфа 6.4)
VAR
Temp:Student;
k,i:Integer;
Stop:Boolean;
...
{ Сортировка массива S со списком студентов по
фамилии. Пусть длина списка задана переменной n }
k:=n;
REPEAT
Dec(k);
Stop:=True;
FOR i:=1 TO k DO
IF S[i].Name>W[i+1].Name THEN
BEGIN
Temp:=S[i];
S[i]:=S[i+1];
S[i+1]:=Temp;
Stop:=False;
END;
UNTIL Stop;
Лекция 8
|
|
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!