Наглядная демонстрация алгоритмов сортировки

Методы сортировки изображенные в виде танца - это сочетание научных знаний и искусства, которые очень уместны и хорошо сочетаемы.

Удивительно, конечно, что при помощи танца можно любому объяснить, метод сортировки.

Quick-sort или Быстрая сортировка.

Краткое описание алгоритма:

1. выбрать элемент, называемый опорным.
2. сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.
3. повторить рекурсивно для «меньших» и «больших».

Shell-sort Сортировка Шелла.

Краткое описание алгоритма:

1. Задается расстояние d определенным способом.
2. При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии d.
3. Повторение пункта 1  для некоторых меньших значений d.
4. Завершается сортировка Шелла упорядочиванием элементов при d = 1.

Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места.

Merge-sort или Сортировка слиянием

Так же данный алгоритм называют алгоритмом «разделяй и властвуй».

Краткое описание алгоритма:

1. Сортируемый массив разбивается на две части примерно одинакового размера;
2. Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
3. Два упорядоченных массива половинного размера соединяются в один.

Insert-sort или Сортировка вставками

Краткое описание алгоритма:

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

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

Обычно, элементы вставляются по порядку их появления во входном массиве.

Bubble-sort или Сортировка пузырьком

Краткое описание алгоритма:

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