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

Поиск Лекций


Простейшие методы сортировки: метод вставок

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

Пусть имеется n элементов а1 а2, а3, . . ., аn, расположенных в ячейках массива. Сортировка выполняется за (n–1) шаг, причем шаги удобно нумеровать от 2 до n. На каждом i-ом шаге обрабатываемый набор разбивается на 2 части:

· левую часть образуют уже упорядоченные на предыдущих шагах элементы а1, а2, а3, . . ., аi-1

· правую часть образуют еще не обработанные элементы аi, аi+1, аi+2, . . ., аn

На шаге i для элемента аi находится подходящее место в уже отсортированной последовательности. Поиск подходящего места выполняется поэлементными сравнениями и перестановками по необходимости: сравниваем аi с аi-1, если аi < аi-1, то переставляем их, потом сравниваем аi-1 с аi-2 и т. д. Сравнения и, возможно, перестановки продолжаются до тех пор, пока не будет выполнено одно из 2-х следующих условий:

· в отсортированном наборе найден элемент, меньший аi (все остальные не просмотренные элементы будут еще меньше)

· достигнут первый элемент набора а1, что произойдет в том случае, если аi меньше всех элементов в отсортированном наборе и он должен занять первое место в массиве

Пример. Возьмем тот же исходный набор целых чисел: 15-33-42-07-12-19

  а1 а2 а3 а4 а5 а6 Выполняемые операции
шаг 2 сравнение 15 и 33, обмена нет, 15 – пока первый
шаг 3 сравнение 33 и 42, обмена нет, 15 и 33 пока первые
шаг 4 сравнение 07 и 42, меняем их
сравнение 07 и 33, меняем их
сравнение 07 и 15, меняем их; 07-15-33 пока первые
шаг 5 сравнение 12 и 42, меняем их
сравнение 12 и 33, меняем их
сравнение 12 и 15, меняем их
сравнение 12 и 07, обмена нет, пока: 07-12-15-33
шаг 6 сравнение 19 и 42, меняем их
сравнение 19 и 33, меняем их
сравнение 19 и 15, обмена нет, все готово

 

Для данного примера было сделано 12 сравнений и 8 перестановок, что чуть лучше предыдущего метода.

В среднем, число сравнений по данному методу примерно в 2 раза меньше, чем в методе пузырька, оставаясь тем не менее пропорциональным величине n2. Наилучший результат этот метод показывает для уже упорядоченного исходного массива – всего (n-1) сравнение.

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

for i := 2 to n do

Begin

temp := a [i]; j := i – 1;

While (j > 0) and (temp < a [j] ) do

begin a [j+1] := a [j]; j := j – 1; end;

a [j+1] := temp;

end;

 

 

Простейшие методы сортировки: метод выбора

Данный метод из группы простейших имеет лучшие характеристики по числу перестановок, хотя он, как и оба ранее рассмотренных метода, в целом имеет трудоемкость O(n2). Его чуть более лучшие показатели связаны с тем, что в некоторых ситуациях выполняется перестановка не соседних элементов, а отстоящих на некотором расстоянии друг от друга.

Пусть имеется n элементов а1 а2, а3, .

. ., аn, расположенных в ячейках массива. Сортировка выполняется за (n–1) шаг, пронумерованных от 1 до n-1. На каждом i-ом шаге обрабатываемый набор разбивается на 2 части:

· левую часть образуют уже упорядоченные на предыдущих шагах элементы а1, а2, а3, . . ., аi-1

· правую часть образуют еще не обработанные элементы аi, аi+1, аi+2, . . ., аn

Суть метода состоит в том, что в необработанном наборе отыскивается наименьший элемент, который меняется местами с элементом аi. На первом шаге (при i = 1), когда необработанным является весь исходный набор, это сводится к поиску наименьшего элемента в массиве и обмену его с первым элементом. Ясно, что поиск наименьшего элемента выполняется обычным попарным сравнением, но соседние элементы при этом не переставляются, что в целом уменьшает число пересылок.

Пример. Возьмем тот же исходный набор целых чисел: 15-33-42-07-12-19

  а1 а2 а3 а4 а5 а6 Выполняемые операции
шаг 1 сравнение 15 и 33, min = 15
сравнение 15 и 42, min = 15
сравнение 15 и 07, min = 07
сравнение 07 и 12, min = 07
сравнение 07 и 19, min = 07, обмен 15 и 07
шаг 2 сравнение 33 и 42, min = 33
сравнение 33 и 15, min = 15
сравнение 15 и 12, min = 12
сравнение 12 и 19, min = 12, обмен 33 и 12
шаг 3 сравнение 42 и 15, min = 15
сравнение 15 и 33, min = 15
сравнение 15 и 19, min = 15, обмен 42 и 15
шаг 4 сравнение 42 и 33, min = 33
сравнение 33 и 19, min = 19, обмен 42 и 19
шаг 5 сравнение 33 и 42, min = 33, обмена нет, все готово

 

В данном примере сделано 15 сравнений (как и в методе пузырька), но всего 4 перестановки. Эта особенность сохраняется и в целом: по числу сравнений метод выбора близок к методу пузырька, но по числу перестановок существенно превосходит оба рассмотренные выше методы (оценка числа перестановок n*log 2 n)

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

fori := 1 to n–1 do

Begin

k := i; temp := a [i]; {устанавливаем начальный минимальный элемент}

for j := i+1 to n do

if a [j] < temp then

begin{изменяем текущий минимальный элемент}

k := j; temp := a [j];

end;

a [k] := a [i]; a [i] := temp;

end;

Общее заключение по простейшим методам сортировки.

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

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

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

 

Практическое задание

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

· сортировку обменом (метод пузырька)

· сортировку выбором

· сортировку вставками

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

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

После завершения разработки программы необходимо выполнить всеми методами сортировку нескольких массивов с разным числом элементов (10, 100, 1.000, 10.000) и провести сравнительный анализ эффективности рассматриваемых методов.

Главная программа должна реализовать диалог с пользователем для выбора метода сортировки.

 

1.7. Контрольные вопросы по теме

1. В чем состоит задача выбора алгоритмов решения однотипных задач?

2. Какие критерии используются при выборе алгоритмов?

3. Как оценивается трудоемкость алгоритма?

4. Что такое О-нотация и для чего она используется?

5. Какие группы функций можно выделить с помощью О-нотации?

6. Какие рекомендации следует использовать при выборе алгоритмов с помощью О-нотации?

7. Что можно сказать о применимости алгоритмов класса О(2n) и О(n!)?

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

9. Как классифицируются методы сортировки?

10. Что такое внутренняя и внешняя сортировка и в чем состоят особенности этих задач?

11. В чем состоят особенности универсальных и специальных методов внутренней сортировки?

12. Какие основные методы сортировки относятся к универсальным и какую они имеют трудоемкость?

13.

В чем состоит практическое значение изучения простейших методов сортировки?

14. Как классифицируются методы поиска?

15. В чем состоит суть метода сортировки обменом?

16. Какие шаги выполняет алгоритм сортировки обменом?

17. Как программно реализуется сортировка обменом?

18. В чем достоинства и недостатки метода сортировки обменом?

19. Приведите практический пример сортировки массива методом обмена.

20. В чем состоит суть метода сортировки вставками?

21. Какие шаги выполняет алгоритм сортировки вставками?

22. Как программно реализуется сортировка вставками?

23. В чем достоинства и недостатки метода сортировки вставками?

24. Приведите практический пример сортировки массива методом вставок.

25. В чем состоит суть метода сортировки выбором?

26. Какие шаги выполняет алгоритм сортировки выбором?

27. Как программно реализуется сортировка выбором?

28. В чем достоинства и недостатки метода сортировки выбором?

29. Приведите практический пример сортировки массива методом выбора.

 

©2015-2018 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Нарушение авторских прав и Нарушение персональных данных

Она же пирамидальная сортировка.

Является «умной» модификацией-синтезом сортировки выбором и пузырьковой сортировки.

Алгоритм

Основная идея — ищем максимальный элемент в неотсортированной части массива и ставим его в конец этого подмассива.

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

Сортирующее (неубывающее) дерево — дерево у которого любой родитель не меньше чем каждый из его потомков. Если сортирующее дерево невозрастающее, то, соответственно, любой родитель не больше чем каждый из его потомков.

Сложность по времени

У алгоритма нет благоприятных и вырожденных случаев. При любом входящем массиве (даже если он почти отсортирован) сортировка имеет одну и ту же временную сложность — O(n log n).

Дополнительно

Сортировка кучей используется в целом ряде других алгоритмов сортировок.

Это как её непосредственные вариации:

  • Тернарная пирамидальная сортировка
  • Сортировка декартовым деревом
  • Плавная сортировка

Так и гибридные алгоритмы:

Характеристики алгоритма

Название Сортировка кучей (Heap sort, Пирамидальная сортировка, Pyramid sort)
Автор J. W. J. Williams
Год 1964
Класс Сортировки выбором
Устойчивость Нет
Сравнения Да
Сложность по времени Лучшая O (n log n)
Средняя
Худшая
Сложность по памяти Общая O(n)
Дополнительная O(1)

Ссылки

Хабрахабр: J-сортировка

Пирамидальная сортировка в Википедии
Heap sort on Wikipedia
Реализация на различных ЯП

by valemak

Слово сортировка

Слово сортировка английскими буквами(транслитом) — sortirovka

Слово сортировка состоит из 10 букв: а в и к о о р р с т


Значения слова сортировка. Что такое сортировка?

Сортировка

Сортировка — качественная оценка и сортировка лесоматериалов, основанная на допустимости различных пороков древесины в зависимости от ее назначения. При сортировке лесоматериалов различают: — пороки качества: сучки, метик, прорость и другие пороки…

glossary.ru

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

Сортировка Шелла (англ.

Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга.

ru.wikipedia.org

Сортировка данных

СОРТИРОВКА ДАННЫХ [data sorting, ordering] — один из этапов обработки данных, упорядочение элементарных данных в последовательности, определяемой значениями некоторых признаков, называемых ключами сортировки.

Лопатников. — 2003

Сортировка данных [data sorting, ordering] — один из этапов обработки данных, упорядочение элементарных данных в последовательности, определяемой значениями некоторых признаков, называемых ключами сортировки.

slovar-lopatnikov.ru

Сортировка медицинская

Сортировка медицинская I Сортиро́вка медици́нская распределение пораженных и больных при их поступлении на этапы медицинской эвакуации или в лечебные учреждения в зависимости от характера и тяжести поражения (заболевания) на группы нуждающихся в…

Медицинская эциклопедия

СОРТИРОВКА МЕДИЦИНСКАЯ — распределение пораженных и больных в зависимости от характера и тяжести поражения (заболевания) на группы нуждающихся в однородных лечебно-профилактических или эвакуационных мероприятиях с определением очередности и места…

Краткая медицинская энциклопедия. — М., 1989

Сортировка медицинская — распределение поступающих пораженных и больных на группы нуждающихся в однородных лечебно-профилактических и эвакуационных мероприятиях в зависимости от характера и тяжести поражения (заболевания) с определением очередности…

Большой медицинский словарь. — 2000

Гномья сортировка

Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком.

ru.wikipedia.org

Блочная сортировка

Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так…

ru.wikipedia.org

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

Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

ru.wikipedia.org

Сортировка (сельскохозяйств.)

СОРТИРОВКА — с.-х. машина для очистки и сортирования семян разл. культур и нек-рых с.-х. продуктов по к.-л. признакам (парусности, размерам, цвету и др.).

Большой энциклопедический политехнический словарь

Сортировка сельскохозяйственная, машина для разделения на фракции (сортирования) зерна зерновых культур, семян трав, овощных растений, клубней картофеля, лука-севка, плодов (например, томата, яблони) и очищения их от примесей.

БСЭ. — 1969—1978

Медицинская сортировка

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

ru.wikipedia.org

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

Словарь терминов МЧС. — 2010

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

civil_protection.academic.ru

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

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке.

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

ru.wikipedia.org

Русский язык

Сортиро́вка, -и, р. мн. -вок.

Орфографический словарь. — 2004


Примеры употребления слова сортировка

Работает сортировка по имени и фамилии.

Задействуется сортировка почты по дате, теме, отправителю и размеру.

Работает сортировка почты по дате, теме, отправителю и размеру.

Новая сортировка позволит лучше организовать письма в своем электронном ящике, говорится в блоге компании.

Таких, как сбор и сортировка урожая.

В том числе: затарка/растарка контейнеров; подработка, переупаковка, маркировка и сортировка грузов; дополнительное и специальное крепление грузов на судах; обработка нестандартных и опасных грузов, в т.ч.


КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ

Сортуванням називають впорядковування по ключах (тобто за якою-небудь ознакою) елементів деякої структури даних на якій визначено відношення порядку.

У залежності від того, чи знаходяться елементи структур даних у внутрішній (оперативній) пам’яті або у зовнішній пам’яті (на зовнішніх пристроях),розрізняють внутрішнє та зовнішнє сортування.

Нехай існують послідовність a0, a1… an і функція порівняння, яка на будь-яких двох елементах послідовності приймає одне з трьох значень: менше, більше або дорівнює. Задача сортування полягає у перестановці елементів послідовності так, щоб виконувалася умова: ai <= ai+1, для всіх i від 0 до n.

Якщо значення функції порівняння залежить тільки від поля x, то x називають ключем, по якому проводиться сортування. На практиці, в якості x часто виступає число, а поле у зберігає будь-які дані, жодним чином не впливаючи на роботу алгоритму.

Мабуть, жодна інша проблема не породила такої кількості найрізноманітніших рішень, як задача сортування. Чи існує певний "універсальний, найкращий алгоритм"? Маючи приблизні характеристики вхідних даних, можна підібрати метод, який працює оптимальним чином.

Для того, щоб обґрунтовано зробити такий вибір, розглянемо параметри, по яких проводититься оцінка алгоритмів.

1. Час сортування — основний параметр, що характеризує швидкодію алгоритму.

2. Пам’ять — ряд алгоритмів вимагає виділення додаткової пам’яті під тимчасове зберігання даних. При оцінці пам’яті, що використовується, не враховується місце, яке займає початковий масив і незалежні від вхідної послідовності витрати, наприклад, на зберігання коду програми.

3. Стійкість — стійке сортування не міняє взаємного розташування рівних елементів. Така властивість може бути дуже корисною, якщо вони складаються з декількох полів, як на рис. 5, а сортування відбувається по одному з них, наприклад, по x.

4. Природність поведінки — ефективність методу при обробці вже відсортованих, або частково відсортованих даних. Алгоритм поводиться природно, якщо враховує цю характеристику вхідної послідовності і працює краще.

 

Ще однією важливою властивістю алгоритму є його сфера застосування.

Тут основних позицій дві:

· внутрішні сортування працюють з даним в оперативній пам’яті з довільним доступом;

· зовнішні сортування упорядковують інформацію, розташовану на зовнішніх носіях.

Це накладає деякі додаткові обмеження на алгоритм: доступ до носія здійснюється послідовним чином: в кожний момент часу можна зчитати або записати тільки елемент, наступний за слідуючим; o об’єм даних не дозволяє їм розміститися в ОЗП; Крім того, доступ до даних на носію здійснюється набагато повільніше, ніж операції з оперативною пам’яттю.

Даний клас алгоритмів ділиться на два основні підкласи:

· Внутрішнє сортування оперує з масивами, що цілком поміщаються в оперативній пам’яті з довільним доступом до будь-якої комірки. Дані звичайно сортуються на тому ж місці, без додаткових витрат.

· Зовнішнє сортування оперує з пристроями великого об’єму, що запам’ятовують, але з доступом не довільним, а послідовним (сортування файлів), тобто у даний момент ми “бачимо” тільки один елемент, а витрати на перемотування у порівнянні з пам’яттю невиправдано великі . Це приводить до спеціальних методів сортування, які звичайно використовують додатковий дисковий простір.

1. Функція складності алгоритму

 

Для вирішення багатьох проблем існує безліч різних алгоритмів. Який з них вибрати для вирішення конкретного завдання? Це питання дуже ретельно опрацьовується в програмуванні. Ефективність програми є дуже важливою її характеристикою. Ефективність програми має дві складові: пам’ять (або простір) і час. Просторова ефективність вимірюється кількістю пам’яті, потрібної для виконання програми. Комп’ютери володіють обмеженим об’ємом пам’яті. Якщо дві програми реалізують ідентичні функції, то та, яка використовує менший об’єм пам’яті, характеризується більшою просторовою ефективністю. Інколи пам’ять стає домінуючим чинником в оцінці ефективності програм. Проте останніми роками у зв’язку з швидким її здешевленням ця складова ефективності поступово втрачає своє значення. Тимчасова ефективність програми визначається часом, необхідним для її виконання. Кращий спосіб порівняння ефективність алгоритмів полягає в зіставленні їх порядків складності. Цей метод застосовний як до тимчасової, так і просторовій складності. Порядок складності алгоритму виражає його ефективність зазвичай через кількість оброблюваних даних. Наприклад, деякий алгоритм може істотно залежати від розміру оброблюваного масиву. Якщо, скажімо, час обробки подвоюється з подвоєнням розміру масиву, то порядок тимчасової складності алгоритму визначається як розмір масиву. Порядок алгоритму — це функція, домінуюча над точним вираженням тимчасовій складності.

Функція f(n) має порядок 0(g(n)), якщо є константа К і лічильник n0 такі, що f(n)(K*g(n)) для п > n0. Наприклад: відомо, що точний час обробки масиву визначається з рівняння:

1.1. Види функції складності алгоритмів

Для оцінки ефективності алгоритмів використовується функція складності алгоритму, яка позначається прописною буквою О, в круглих дужках записується аргумент. Наприклад, функція складності 0(n^2) читається як функція складності по-рядка п^2. функція складності алгоритму — це функція, що визначає кількість порівнянь, перестановок, а також тимчасові і ресурсні витрати на реалізацію алгоритму.

Функція складності приймає наступний ряд значень (мал. 2.15).

 

 

Чим правіше на осі розташована функція складності, тим менш ефективний алгоритм.

 

· Методи проста вставка, простий і стандартний обмін мають функцію складності О(п^2).

· Метод Хоара і пірамідальне сортування мають функцію складності 0(nlog2n)

· Метод Шелла і турнірне сортування мають функцію складності 0(0,3n(1оg2n)^2).

 

1.2. Cкладність алгоритмів сортування

12Следующая ⇒


Дата добавления: 2013-12-14; Просмотров: 1789; Нарушение авторских прав?;




Читайте также:

Существует традиционное деление алгоритмов на численные и нечисленные. Численные алгоритмы предназначены для математических расчетов: вычисления по формулам, решения уравнений, статистической обработки данных и т.п. В таких алгоритмах основным видом обрабатываемых данных являются числа. Нечиcленные алгоритмы имеют дело с самыми разнообразными видами данных: символьной, графической, мультимедийной информацией. К этой категории относятся многие алгоритмы системного программирования (трансляторы, операционные системы), систем управления базами данных, сетевого программного обеспечения и т.д.

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

Различают алгоритмы внутренней сортировки — во внутренней памяти и алгоритмы внешней сортировки — сортировки файлов. Далее мы будем рассматривать только внутреннюю сортировку.

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

Сортировка производится либо по возрастанию, либо по убыванию значения ключа A[i].key.

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

Алгоритм сортировки «методом пузырька» рассматривался в разделе 3.17. Здесь мы обсудим два алгоритма: сортировку простым включением и быструю сортировку.

Сортировка простым включением. Предположим, что на некотором этапе работы алгоритма левая часть массива с 1-го по (i — 1)-й элемент включительно

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

Процесс начинается с левой части, состоящей из одного элемента А[1], а заканчивается, когда правая часть становится пустой.

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

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

Оценим величину минимальной временной сложности алгоритма. Если массив уже отсортирован, то тело цикла while не будет выполняться ни разу. Выполнение процедуры сведется к работе следующего цикла:

Поскольку тело цикла for исполняется n — 1 раз, то число пересылок элементов массива

Мmin = 2(п — 1),

а число сравнений ключей равно

Сmin = n — 1.

Сложность алгоритма будет максимальной, если исходный массив упорядочен по убыванию. Тогда каждый элемент А[i] будет «прогоняться» к началу массива, т.е. устанавливаться в первую позицию. Цикл while выполнится 1 раз при i = 2, 2 раза при i = 3 и т. д., п — 1 раз при i = п. Таким образом, общее число пересылок записей равно:

Более подходящей для реальной ситуации является средняя оценка сложности. Для ее вычисления надо предположить, что все элементы исходного массива — случайные числа и их значения никак не связаны с их номерами. В таком случае результат очередной проверки условия x. key<A[j].key в цикле While также является случайным.

Разумно допустить, что среднее число выполнений цикла While для каждого конкретного значения i равно i/2, т. е. в среднем каждый раз приходится просматривать половину последовательности до тех пор, пока не найдется подходящее место для очередного элемента

Тогда формула для среднего числа пересылок (средняя оценка сложности) будет следующей:

Как максимальная, так и средняя оценка сложности алгоритма квадратична (является полиномом второй степени) по параметру п — размеру сортируемого массива.

Алгоритм быстрой сортировки. Этот алгоритм был разработан Э. Хоаром. В алгоритме быстрой сортировки используются три идеи:

• разделение сортируемого массива на 2 части, левую и правую;

• взаимное упорядочение двух частей (подмассивов) так, чтобы все элементы левой части не превосходили элементов правой части;

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

Для разделения массива на две части нужно выбрать некоторое «барьерное» значение ключа. Это значение должно удовлетворять единственному условию: лежать в диапазоне значений для данного массива (т.е.

между минимальной и максимальной величиной). За «барьер» можно выбрать значение ключа любого элемента массива, например первого, или последнего, или находящегося в середине.

Далее нужно сделать так, чтобы в левом подмассиве оказались все элементы с ключом, меньшим барьера, а в правом — с большим: Затем, просматривая массив слева направо, необходимо найти позицию первого элемента с ключом, большим барьера, а просматривая справа налево — найти первый элемент с ключом, меньшим барьера. Следует поменять эти значения, затем продолжить встречное движение до следующей пары элементов, предназначенных для обмена. Необходимо повторять эту процедуру, пока индексы левого и правого просмотров не совпадут. Место совпадения станет границей между двумя взаимно упорядоченными подмассивами. Далее алгоритм рекурсивно применяется к каждому из подмассивов (левому и правому). В конечном счете приходим к совокупности из п взаимно упорядоченных одноэлементных массивов, которые делить дальше невозможно. Эта совокупность образует один полностью упорядоченный массив. Сортировка завершена!

Сложность алгоритма быстрой сортировки. Исследование временной сложности алгоритма быстрой сортировки является очень трудоемкой задачей, и поэтому мы здесь приводить его не будем. Рассмотрим лишь окончательный результат этого анализа. Временная сложность T как функция от п — размера массива — по порядку величины выражается следующей формулой:

Т(п) = 0 (n 1n (n)).

Здесь использовано принятое в математике обозначение: O(х) обозначает величину порядка х. Следовательно, временная сложность алгоритма быстрой сортировки есть величина порядка п 1n(n). Эта величина для целых положительных п меньше, чем п2 (вспомним, что алгоритм сортировки простым включением имеет сложность порядка n2).

И чем больше значение п, тем эта разница существеннее. Например:


⇐ Предыдущая28293031323334353637Следующая ⇒


Дата публикования: 2014-12-11; Прочитано: 560 | Нарушение авторского права страницы



studopedia.org — Студопедия.Орг — 2014-2018 год.(0.003 с)…

Добавить комментарий

Закрыть меню