Умопомрачительное видео сортировки одномерного массива.
Нашла несколько видео, в которых показана сортировка одномерного массива разными методами: quick-sort, shell-sort, merge-sort, insert-sort, bubble-sort.
Расскажу кратко о каждой сортировке:
Quick-sort или Быстрая сортировка
Краткое описание алгоритма:
- выбрать элемент, называемый опорным.
- сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.
- повторить рекурсивно для «меньших» и «больших».
Танец метода:
Shell-sort Сортировка Шелла
Краткое описание алгоритма:
- Задается расстояние d определенным способом.
- При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии d.
- Повторение пункта 1 для некоторых меньших значений d.
- Завершается сортировка Шелла упорядочиванием элементов при d = 1.
Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места.
Танец метода:
Merge-sort или Сортировка слиянием
Так же данный алгоритм называют алгоритмом «разделяй и властвуй».
Краткое описание алгоритма:
- Сортируемый массив разбивается на две части примерно одинакового размера;
- Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
- Два упорядоченных массива половинного размера соединяются в один.
Танец метода:
Insert-sort или Сортировка вставками
Краткое описание алгоритма:
На каждом шаге алгоритма выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан.
Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора.
Обычно, элементы вставляются по порядку их появления во входном массиве.
Танец метода:
Bubble-sort или Сортировка пузырьком
Краткое описание алгоритма:
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Танец метода:
Все выше описанные методы сортировки изображены в виде танца. Я считаю, что данное сочетание научных знаний и искусства очень уместными и хорошо сочетаемыми. Удивительно, конечно, что при помощи танца можно любому объяснить, метод сортировки. Однако можно подумать над тем, какими ещё нестандартными методами можно донести сложную и не очень информацию до человека. Давно известно, что такой подход совмещения помогает быстрее запомнить и разобраться в подаваемом материале. В итоге получаем интересную и познаваемую науку, вдохновляющую и возбуждающую творческую мысль.