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

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

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

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

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

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

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

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) дополнительной памяти

наименьшего или наибольшего элемента и помещения его в начало или конец упорядоченного списка
Сортировка Шелла (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) дополнительной памяти.

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

вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

i++) {
for (int j = 0; j < n-i; j++) {
if (data[j] > data [j+1]) {
int tmp = data[j];
data[j] = data[j+1];
data[j+1] = tmp;
}
}
}

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

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

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

< n; i++) {
int c = data[i];
for (j = i-1; j >= 0 && data[j] > c; j--) {
data[j+1] = data[j];
}
data[j+1] = c;
}

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

= n; // Шаг поисков и вставки
int i, j;
do {
// Вычисляем новый шаг
step = step / 3 + 1;
// Производим сортировку простыми вставками с заданным шагом
for (i = step; i < n; i++) {
int c = data[i];
for (j = i-step; j >= 0 && data[j] > c; j -= step) {
data[j+step] = data[j];
}
data[j+step] = c;
}
} while (step != 1);

Количество перестановок элементов (по результатам экспериментов со случайным массивом)

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

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

nb, // длина массива b[]
nc;
int[] c = new int[nc = na + nb];
int ia = 0,
ib = 0,
ic = 0;
while (ia < na && ib < nb) {
if (a[ia] < b[ib])
c[ic++] = a[ia++];
else
c[ic++] = b[ib++];
}
while (ia < na) c[ic++] = a[ia++];
while (ib < nb) c[ic++] = b[ib++];

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

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

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

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

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

Алгоритмы

Адаптеры

Функциональные
объекты

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

Поиска

Математические

Сортировки

Работы
С последовательностями

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