Теория алгоритмов. Алгоритмы сортировки массивов. (Лекция 2) презентация

Содержание


Презентации» Информатика» Теория алгоритмов. Алгоритмы сортировки массивов. (Лекция 2)
Теория алгоритмов
 Лекция № 2
 Алгоритмы сортировки массивовАлгоритм сортировки
 Сортировка - это процесс упорядочения некоторого множества элементов, наКритерии оценки алгоримов
 Время — основной параметр, характеризующий быстродействие алгоритма. ДляКлассификация алгоритмов сортировки
 Устойчивость (stability) — устойчивая сортировка не меняет взаимногоКлассификация по области применения 
 Внутренняя сортировка оперирует с массивами, целикомТакже алгоритмы классифицируются по:
 потребности в дополнительной памяти или её отсутствии;Алгоритмы устойчивой сортировки
 Сортировка обменная (пузырьком) (англ. Bubble sort ) — сложностьАлгоритмы неустойчивой сортировки
 Сортировка выбором (Selection sort) — Сложность алгоритма: O(n2);Прочие алгоритмы сортировки
 Сортировка перестановкой — O(n·n!) — худшее время. ДляСортировка обменом (пузырьковая сортировка)
 Идея метода: шаг сортировки состоит в проходеПримерПримерОптимизация алгоритма
 Запоминаем, производился ли на данном проходе какой-либо обмен. ЕслиСортировка выбором
 Идея метода состоит в том, чтобы создавать отсортированную последовательностьПримерСортировка вставками
 Идея алгоритма: Предположим последовательность a[0]...a[i] упорядочена. При этом поПримерСортировка Шелла
 Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, идея которого состоитБыстрая сортировка
 Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанныйБыстрая сортировкаСортировка подсчетом
 Этот алгоритм подходит для сортировки целых чисел из неЦифровая сортировка
 Цифровая сортировка — один из алгоритмов сортировки, использующих внутреннююАлгоритмы поиска
 Одно из наиболее часто встречающихся в программировании действий это-Линейный поиск
 Данный алгоритм является простейшим алгоритмом поиска и в отличие,Двоичный поиск
 Двоичный поиск (также известен, как метод деления пополам иДвоичный поиск в упорядоченном массивеБиблиотека STLАлгоритмы STL
 STL - алгоритмы представляют набор готовых функций, которые могутФункции для сортировки членов коллекции
 sort, stable_sort, partial_sort, partial_sort_copy, nth_element, binary_search,



Слайды и текст этой презентации
Слайд 1
Описание слайда:
Теория алгоритмов Лекция № 2 Алгоритмы сортировки массивов


Слайд 2
Описание слайда:
Алгоритм сортировки Сортировка - это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >, <, і , Ј . Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же элементы, но в порядке возрастания (или убывания) значений.

Слайд 3
Описание слайда:
Критерии оценки алгоримов Время — основной параметр, характеризующий быстродействие алгоритма. Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n²). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в O(n log n) сравнениях в среднем; Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.

Слайд 4
Описание слайда:
Классификация алгоритмов сортировки Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов. Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше. Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n log n) , но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Слайд 5
Описание слайда:
Классификация по области применения Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат. Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов). Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.

Слайд 6
Описание слайда:
Также алгоритмы классифицируются по: потребности в дополнительной памяти или её отсутствии; потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствии таковой .

Слайд 7
Описание слайда:
Алгоритмы устойчивой сортировки Сортировка обменная (пузырьком) (англ. Bubble sort ) — сложность алгоритма: O(n2); для каждой пары индексов производится обмен, если элементы расположены не по порядку. Сортировка перемешиванием (Шейкерная, Cocktail sort, bidirectional bubble sort) — Сложность алгоритма: O(n2) Гномья сортировка — имеет общее с сортировкой пузырьком и сортировкой вставками. Сложность алгоритма — O(n2). Сортировка вставками (Insertion sort) — Сложность алгоритма: O(n2); определяем где текущий элемент должен находиться в упорядоченном списке и вставляем его туда Блочная сортировка (Корзинная сортировка, Bucket sort) — Сложность алгоритма: O(n); требуется O(k) дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций "переставить" и "сравнить". Сортировка подсчётом (Counting sort) — Сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти (рассмотрено 3 варианта) Сортировка слиянием (Merge sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; выстраиваем первую и вторую половину списка отдельно, а затем — сливаем упорядоченные списки Сортировка с помощью двоичного дерева (англ. Tree sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти

Слайд 8
Описание слайда:
Алгоритмы неустойчивой сортировки Сортировка выбором (Selection sort) — Сложность алгоритма: O(n2); поиск наименьшего или наибольшего элемента и помещения его в начало или конец упорядоченного списка Сортировка Шелла (Shell sort) — Сложность алгоритма: O(n log2 n); попытка улучшить сортировку вставками Сортировка расчёской (Comb sort) — Сложность алгоритма: O(n log n) Пирамидальная сортировка (Сортировка кучи, Heapsort) — Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка Плавная сортировка (Smoothsort) — Сложность алгоритма: O(n log n) Быстрая сортировка (Quicksort) — Сложность алгоритма: O(n log n) — среднее время, O(n2) — худший случай; Поразрядная сортировка (Цифровая сортировка) — Сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти.

Слайд 9
Описание слайда:
Прочие алгоритмы сортировки Сортировка перестановкой — O(n·n!) — худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива. Глупая сортировка (Stupid sort) — O(n3); рекурсивная версия требует дополнительно O(n2) памяти Блинная сортировка (Pancake sorting) — O(n), требуется специализированное аппаратное обеспечение Лексикографическая или поразрядная сортировка (Radix sort) Сортировка подсчётом (Counting sort) Топологическая сортировка Внешняя сортировка

Слайд 10
Описание слайда:
Сортировка обменом (пузырьковая сортировка) Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

Слайд 11
Описание слайда:
Пример

Слайд 12
Описание слайда:
Пример

Слайд 13
Описание слайда:

Слайд 14
Описание слайда:
Оптимизация алгоритма Запоминаем, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу. Запоминаем индекс последнего обмена k. Действительно: все пары соседих элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i. Меняем направление следующих один за другим проходов. Получившийся алгоритм иногда называют "шейкер-сортировкой".

Слайд 15
Описание слайда:
Сортировка выбором Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. Суть алгоритма: Построить готовую упорядоченную последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м. На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i].

Слайд 16
Описание слайда:
Пример

Слайд 17
Описание слайда:
Сортировка вставками Идея алгоритма: Предположим последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться все новые элементы. Суть алгоритма: На i-м шаге последовательность разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n]. На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется.

Слайд 18
Описание слайда:
Пример

Слайд 19
Описание слайда:

Слайд 20
Описание слайда:
Сортировка Шелла Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, идея которого состоит в сравнении элементов, стоящих не только рядом, но и на расстоянии друг от друга. Иными словами — сортировка вставками с предварительными «грубыми» проходами. При сортировке Шелла сначала сравниваются и сортируются между собой ключи, отстоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть, обычной сортировкой вставками).

Слайд 21
Описание слайда:

Слайд 22
Описание слайда:

Слайд 23
Описание слайда:
Быстрая сортировка Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков. Краткое описание алгоритма выбрать элемент, называемый опорным. сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие. повторить рекурсивно для «меньших» и «больших».

Слайд 24
Описание слайда:

Слайд 25
Описание слайда:
Быстрая сортировка

Слайд 26
Описание слайда:

Слайд 27
Описание слайда:

Слайд 28
Описание слайда:

Слайд 29
Описание слайда:
Сортировка подсчетом Этот алгоритм подходит для сортировки целых чисел из не очень большого диапазона (сравнимого с размером массива). Идея алгоритма: для каждого элемента найти, сколько элементов, меньших определенного числа, и поместить это число на соответствующие место. За линейный проход по массиву для каждого из возможных значений подсчитываем, сколько элементов имеют такое значение. Потом добавляем к каждому из найденных чисел суму всех предыдущих. Получая, таким образом, сколько есть элементов, значения которых не больше данного значения. Далее, опять-таки за линейный проход, формируем из исходного массива новый отсортированный.

Слайд 30
Описание слайда:

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

Слайд 32
Описание слайда:

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

Слайд 34
Описание слайда:
Линейный поиск Данный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева направо, т.е. от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.

Слайд 35
Описание слайда:
Двоичный поиск Двоичный поиск (также известен, как метод деления пополам и метод половинного деления) — алгоритм нахождения заданного значения монотонной (невозрастающей или неубывающей) функции. Поиск основывается на теореме о промежуточных значениях. Используется в информатике, вычислительной математике и математическом программировании.

Слайд 36
Описание слайда:
Двоичный поиск в упорядоченном массиве

Слайд 37
Описание слайда:
Библиотека STL

Слайд 38
Описание слайда:
Алгоритмы STL STL - алгоритмы представляют набор готовых функций, которые могут быть применены к STL коллекциям и могут быть подразделены на три основных группы

Слайд 39
Описание слайда:
Функции для сортировки членов коллекции sort, stable_sort, partial_sort, partial_sort_copy, nth_element, binary_search, lower_bound, upper_bound, equal_range, merge, inplace_merge, includes, set_union, set_intersection, set_difference, set_symmetric_difference, make_heap, push_heap, pop_heap, sort_heap, min, max, min_element, max_element, lexographical_compare, next_permutation, prev_permutation


Скачать презентацию на тему Теория алгоритмов. Алгоритмы сортировки массивов. (Лекция 2) можно ниже:

Похожие презентации