x, y, z

Алгоритмы сортировки в народных танцах

Комментарии: 0
Трансильванский университет Sapientia представил свой новый обучающий курс по алгоритмам сортировки. Стоит отметить талант создателей и высокую наглядность пособия.

1. Сортировка пузырьком как венгерский народный танец
Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: $O(n^2)$.

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

Исполняется танец народа Чангоши (венг. csángók, также чанго от венг. Csángó)

2. Сортировка слиянием как немецкий народный танец
Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Время работы алгоритма порядка $O(n\log n)$ при отсутствии деградации на неудачных случаях, которая является больным местом быстрой сортировки (тоже алгоритм порядка $O(n\log n)$, но только для среднего случая).

Исполняется трансильвано-саксонский (немецкий) народный танец.

3. Сортировка выбором как цыганский народный танец
Сортировка выбором (Selection sort) — алгоритм сортировки. Может быть как устойчивый, так и неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае $O(n^2)$, предполагая что сравнения делаются за постоянное время.

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

Исполняется танец legényes (в Венгрии) или feciorească (в Румынии)

5. Сортировка Шелла как венгерский народный танец
Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Дональда Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга; иными словами — это сортировка вставками, но с предварительными «грубыми» проходами. Аналогичный метод усовершенствования «пузырьковой» сортировки называется «сортировка расчёской».

Исполняется танец венгерской народности Székelys.

6. Сортировка вставками как румынский народный танец
Сортировка вставками (англ. Insertion sort) — алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов. Вычислительная сложность $O(n^2)$.

7. Сортировка кучей как венгерский народный танец
Сортировка кучей (англ. Heapsort) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за $O(n \log n)$ операций при сортировке $n$ элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, $O(1)$). Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям. Пирамидальная сортировка была предложена Дж. Уильямсом в 1964 году.

Исполняется венгерский народный танец Mezőségi.

Создано в Sapientia University, Tirgu Mures (Marosvásárhely), Romania.
Режиссеры: Kátai Zoltán and Tóth László.
Хореограф: Füzesi Albert.
Комментарии: 0