Алгоритмы сортировки (медленная, сгруппированная и упорядоченная)
Все видео алгоритмов сортировки упорядочены, чтобы показать различные асимптотики. Скорость алгоритмов замедлена настолько, что можно увидеть, как они обмениваются элементами. Когда алгоритмы циклов повторяют сортировку на других областях, скорость видео ускоряется, чтобы не было слишком скучно.
Алгоритмы сортировки вставками Insertion Sort
Визуализация алгоритма сортировки вставками.
Сортирует случайный набор целых чисел [1,100], используя сортировку вставкой справа налево.
Анимация замедляется, чтобы вы могли увидеть, как работает алгоритм.
Быстрая сортировка (указатели LR) Quick Sort (LR pointers)
Визуализация алгоритма быстрой сортировки.
Сортирует случайную выборку целых чисел [1,100] с помощью оригинального варианта быстрой сортировки, при этом два указателя (синие) перемещаются слева и справа. Средний элемент выбирается в качестве основного и помечается зеленым цветом.
Быстрая сортировка (указатели LL) Quick Sort (LL pointers)
Визуализация алгоритма быстрой сортировки.
Сортирует случайный набор целых чисел [1,100], используя вариант быстрой сортировки из 3-го издания учебника CLRS, с двумя указателями (синие), оба движутся слева. Первый элемент в каждом диапазоне рекурсии выбирается в качестве поворотного и помечается зеленым цветом (он немедленно перемещается назад).
Быстрая сортировка (троичное деление) Quick Sort
Визуализация алгоритма троичной быстрой сортировки.
Сортирует последовательность целых чисел [1,100] с помощью троично-разделенной быстрой сортировки со схемой разбиения «равно-меньше-больше-равно». Две пары указателей перемещаются слева и справа. После соединения равные элементы меняются местами в середине. Указатель отмечен зеленым цветом, равные элементы — желтым. Поскольку для данной визуализации нужны равные ключи, распределение элементов массива перекошено в [1,100] с помощью квинтовой функции x^5.
Алгоритмы сортировки Сортировка слиянием Merge Sort
Визуализация алгоритма cортировка слиянием.
Сортировка случайной выборки целых чисел [1,100] с помощью сортировки слиянием. Левая и правая граница каждого диапазона отмечены зеленым цветом, середина — синим. Эта сортировка слиянием не работает на месте, при слиянии отсортированных диапазонов она записывает в теневой массив, который копируется обратно после слияния.
Сортировка кучей Heap Sort
Визуализация алгоритма сортировка кучей.
Сортировка случайного массива целых чисел [1,100] с помощью алгоритма max-heap sort. Сначала строится куча в массиве путем просеивания меньшего элемента. Уровни кучи окрашиваются в светлые тона.
Сортировка пузырьком Bubble Sort
Визуализация алгоритма пузырьковой сортировки.
Сортировка случайного набора целых чисел [1,100] с помощью сортировки пузырьком.
Сортировка перемешиванием Cocktail Shaker Sort
Визуализация алгоритма сортировка перемешиванием.
Сортировка случайного множества целых чисел [1,100] с помощью сортировки перемешиванием.
Гномья сортировка Gnome Sort
Визуализация алгоритма гномья сортировка.
Сортировка случайного множества целых чисел [1,100] с помощью gnome sort.
Сортировка Шелла Shell’s Sort
Визуализация алгоритма сортировки Шелла.
Сортировка случайного множества целых чисел [1,100] с помощью сортировки Шелла с массивом промежутков Седжвика.
Сортировка выбором Selection Sort
Визуализация алгоритма сортировки по выбором.
Сортирует случайную выборку целых чисел [1,100], используя сортировку выбором слева направо.
Поразрядная сортировка Radix Sort (LSD)
Визуализация алгоритма поразрядная сортировка.
Сортирует случайную выборку целых чисел [1,100] с помощью поразрядной сортировки по наименьшему значащему разряду с 2-битными радиксами (4 ведра). Алгоритм сортирует не по месту: он копирует элементы в теневой массив во время счетной развертки.
Поразрядная сортировка Radix Sort (MSD)
Визуализация алгоритма поразрядная сортировка MSD Radix Sort.
Сортирует случайную выборку целых чисел [1,100], используя поразрядную сортировку по старшему разряду с 2-битными радиксами (4 ведра). Алгоритм сортирует на месте, проходя циклы с использованием транспозиций.
Сортировка Introsort (std::sort from STL)
Визуализация сортировки Introsort (std::sort) из gcc libstdc++.
Сортирует случайный набор целых чисел [1,100], используя вариант introsort в реализации STL в gcc-4.5. Используется фактическая реализация STL, которая, вероятно, является самой используемой реализацией сортировки в мире.
Сортировка слиянием Adaptive Merge Sort (std::stable_sort)
Визуализация сортировки слияния (std::stable_sort) в gcc libstdc++.
Сортирует случайную выборку целых чисел [1,100], используя адаптивный вариант mergesort в STL-реализации gcc-4.5. Используется фактическая реализация STL, которая, вероятно, является самой используемой реализацией стабильной сортировки в мире.
Гибридный алгоритм сортировки Tim Sort
Визуализация алгоритма TimSort.
Сортирует случайную выборку целых чисел [1,100] с помощью TimSort (стандартный алгоритм сортировки в Python, Java SE 7 и на Android). Объяснение см. на http://en.wikipedia.org/wiki/Timsort. Использовалась реализация на C++.
После медленной сортировки на [1,100] алгоритм снова выполняется быстрее на [1,1260].
Алгоритмы сортировки расчёской Comb Sort
Визуализация алгоритма Comb Sort.
Сортирует случайный набор целых чисел [1,100] с помощью алгоритма Comb Sort https://en.wikipedia.org/wiki/Comb_sort.
Алгоритмы сортировки чёт-нечет Odd-Even Sort
Визуализация алгоритма четно-нечетной сортировки.
Сортировка случайного набора целых чисел [1,100] с помощью четно-нечетной сортировки.
Битонная сортировка Батчера Batcher’s Bitonic Sort
Визуализация алгоритма сортировки Батчера.
Сортирует случайную перестановку целых чисел [1,128] и [1,1260] с помощью битонической сортировки, которая представляет собой параллельную сортировочную сеть, где каждая перестановка слева направо может быть выполнена полностью параллельно https://en.wikipedia.org/wiki/Bitonic_sorter.
Сортировка чётно-нечётнное Батчера Batcher’s Odd-Even Mergesort
Визуализация алгоритма четно-нечетное Бэтчера.
Сортирует случайную перестановку целых чисел [1,128] и [1,1260] с помощью сети mergesort, которая является параллельной сортировочной сетью, где каждая перестановка слева направо может быть выполнена полностью параллельно https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort.
Плавная сортировка Smooth Sort
Визуализация алгоритма плавной сортировки.
Сортирует случайный набор целых чисел [1,100] с помощью плавной сортировки. Используется реализация с сайта https://en.wikipedia.org/wiki/Smoothsort.
Болотная сортировка Bogo Sort
Визуализация алгоритма Bogo Sort.
Bogosort — неэффективный алгоритм сортировки, используемый только в образовательных целях и противопоставляемый другим, более реалистичным алгоритмам. Попытка сортировки случайной перестановки целых чисел [1,100] с помощью bogo sort: короткие звуки — это неудачные проверки, отсортирован ли массив, после чего весь массив переставляется на место и проверяется снова.
Алгоритмы сортировки клоуна Бозо Bozo Sort
Визуализация алгоритма Bozo Sort.
Попытка случайной сортировки целых чисел [1,100] с помощью bozo sort: повторяющиеся звуки — это безуспешные проверки, отсортирован ли массив, после чего случайная пара меняется местами. Когда звук меняется, один из первых элементов был поменян местами.
Медленная сортировка Slow Sort
Визуализация алгоритма медленной сортировки.
Сортирует случайный набор целых чисел [1,50] с помощью медленной сортировки. Используется реализация с сайта https://en.wikipedia.org/wiki/Slowsort. Медленная сортировка очень очень медленная, но не настолько медленная, как Bogo Sort!
Алгоритмы сортировки по частям Stooge Sort
Визуализация алгоритма Stooge Sort.
Сортирует случайный набор целых чисел [1,64] с помощью Stooge sort. Используется реализация из https://en.wikipedia.org/wiki/Stooge_sort.
Цикличная сортировка Cycle Sort
Визуализация алгоритма «Cycle Sort».
Сортировка случайной перестановки целых чисел [1,100] с помощью алгоритма Cycle Sort — https://en.wikipedia.org/wiki/Cycle_sort.
Алгоритм представляет собой алгоритм сортировки на основе транспонирования на месте, который всегда требует минимального количества записей в массив.
Он достигает этого путем вычисления ранга каждого элемента и перестановки его в нужную позицию.
Возможно вам будет интересно:
# Алгоритмы сортировки
