Цель заброшена
Автор не отписывался в цели 9 лет 2 месяца 2 дня
Общая
Реализовать все сортировки с выводом действия через консоль с цветным выделением.
- Сортировка выбором (англ. Selection sort) — поиск наименьшего или наибольшего элемента и помещение его в начало или конец упорядоченного списка. Сложность алгоритма: .
- Сортировка пузырьком (англ. Bubble sort) — для каждой пары индексов производится обмен, если элементы расположены не по порядку. Сложность алгоритма: .
- Сортировка перемешиванием (англ. Cocktail sort). Сложность алгоритма: .
- Гномья сортировка — схожа с сортировкой пузырьком и сортировкой вставками. Сложность алгоритма — .
- Сортировка вставками (Insertion sort) — Определяем, где текущий элемент должен находиться в упорядоченном списке, и вставляем его туда. Сложность алгоритма: .
- Сортировка слиянием (Merge sort) — выстраиваем первую и вторую половину списка отдельно, а затем объединяем упорядоченные списки. Сложность алгоритма: . Требуется дополнительной памяти.
- Сортировка с помощью двоичного дерева (англ. Tree sort). Сложность алгоритма: . Требуется дополнительной памяти.
- Сортировка Timsort (англ. Timsort) — комбинированный алгоритм (используется сортировка вставками исортировка слиянием). Сложность алгоритма: . Требуется дополнительной памяти. Разработан для использования в языке Python[5].
- Сортировка подсчётом (Counting sort). Сложность алгоритма: . Требуется дополнительной памяти.
- Блочная сортировка (Корзинная сортировка, Bucket sort) — требуется дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций «переставить» и «сравнить». Сложность алгоритма: .
- Сортировка Шелла (Shell sort). сложность алгоритма: ; улучшение сортировки вставками.
- Сортировка расчёской (Comb sort) — сложность алгоритма:
- Пирамидальная сортировка (сортировка кучи, Heapsort) — сложность алгоритма: ; превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
- Плавная сортировка (Smoothsort) — сложность алгоритма:
- Быстрая сортировка (Quicksort), в варианте с минимальными затратами памяти — сложность алгоритма: — среднее время, — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине. При использовании дополнительной памяти, можно сделать сортировку устойчивой.
- Интроспективная сортировка (Introsort) — сложность алгоритма: , сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает .
- Терпеливая сортировка (Patience sorting) — сложность алгоритма: — наихудший случай, требует дополнительно памяти, также находит самую длинную увеличивающуюся подпоследовательность
- Stooge sort — рекурсивный алгоритм сортировки с временной сложностью .
- Поразрядная сортировка (она же цифровая сортировка) — сложность алгоритма: ; требуется дополнительной памяти.
- Bogosort — в среднем. Произвольно перемешать массив, проверить порядок.
- Сортировка перестановкой — — худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива.
- Глупая сортировка (Stupid sort) — ; рекурсивная версия требует дополнительно памяти
- Bead Sort — или , требуется специализированное аппаратное обеспечение
- Блинная сортировка (Pancake sorting) — , требуется специализированное аппаратное обеспечение
- Блочная сортировка (Корзинная сортировка, Bucket sort)
- Лексикографическая или поразрядная сортировка (Radix sort)
- Сортировка подсчётом (Counting sort)
Критерий завершения
Сделать все
-
Сортировка выбором
-
Сортировка пузырьком
-
Сортировка перемешиванием
-
Гномья сортировка
-
Сортировка вставками
-
Сортировка слиянием
-
Сортировка с помощью двоичного дерева
-
Сортировка подсчётом
-
Блочная сортировка
-
Сортировка Шелла
-
Сортировка расчёской
-
Пирамидальная сортировка
-
Плавная сортировка
-
Быстрая сортировка
-
Интроспективная сортировка
-
Терпеливая сортировка
-
Stooge sort
-
Поразрядная сортировка
-
Bogosort
-
Сортировка перестановкой
-
Глупая сортировка
-
Bead Sort
-
Блинная сортировка
- 4200
- 20 сентября 2015, 16:21
Не пропустите новые записи!
Подпишитесь на цель и следите за ее достижением