Алгоритмы сортировки 26 видов

2345
Алгоритмы сортировки
Алгоритмы сортировки

Table of Contents

Алгоритмы сортировки (медленная, сгруппированная и упорядоченная)

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

 

Алгоритмы сортировки вставками 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] с помощью сортировки слиянием. Левая и правая граница каждого диапазона отмечены зеленым цветом, середина — синим. Эта сортировка слиянием не работает на месте, при слиянии отсортированных диапазонов она записывает в теневой массив, который копируется обратно после слияния.

 

Визуализация алгоритма сортировка кучей.
Сортировка случайного массива целых чисел [1,100] с помощью алгоритма max-heap sort. Сначала строится куча в массиве путем просеивания меньшего элемента. Уровни кучи окрашиваются в светлые тона.

Сортировка пузырьком Bubble Sort

Алгоритмы сортировки пузырьком Bubble Sort
Алгоритмы сортировки пузырьком Bubble Sort

Визуализация алгоритма пузырьковой сортировки.
Сортировка случайного набора целых чисел [1,100] с помощью сортировки пузырьком.

Визуализация алгоритма сортировка перемешиванием.
Сортировка случайного множества целых чисел [1,100] с помощью сортировки перемешиванием.

Визуализация алгоритма гномья сортировка.
Сортировка случайного множества целых чисел [1,100] с помощью gnome sort.

Визуализация алгоритма сортировки Шелла.
Сортировка случайного множества целых чисел [1,100] с помощью сортировки Шелла с массивом промежутков Седжвика.

Визуализация алгоритма сортировки по выбором.
Сортирует случайную выборку целых чисел [1,100], используя сортировку выбором слева направо.

Поразрядная сортировка Radix Sort (LSD)

Визуализация алгоритма поразрядная сортировка.
Сортирует случайную выборку целых чисел [1,100] с помощью поразрядной сортировки по наименьшему значащему разряду с 2-битными радиксами (4 ведра). Алгоритм сортирует не по месту: он копирует элементы в теневой массив во время счетной развертки.

Поразрядная сортировка Radix Sort (MSD)

Визуализация алгоритма поразрядная сортировка MSD Radix Sort.
Сортирует случайную выборку целых чисел [1,100], используя поразрядную сортировку по старшему разряду с 2-битными радиксами (4 ведра). Алгоритм сортирует на месте, проходя циклы с использованием транспозиций.

Визуализация сортировки Introsort (std::sort) из gcc libstdc++.
Сортирует случайный набор целых чисел [1,100], используя вариант introsort в реализации STL в gcc-4.5. Используется фактическая реализация STL, которая, вероятно, является самой используемой реализацией сортировки в мире.

Визуализация сортировки слияния (std::stable_sort) в gcc libstdc++.
Сортирует случайную выборку целых чисел [1,100], используя адаптивный вариант mergesort в STL-реализации gcc-4.5. Используется фактическая реализация STL, которая, вероятно, является самой используемой реализацией стабильной сортировки в мире.

Визуализация алгоритма TimSort.
Сортирует случайную выборку целых чисел [1,100] с помощью TimSort (стандартный алгоритм сортировки в Python, Java SE 7 и на Android). Объяснение см. на http://en.wikipedia.org/wiki/Timsort. Использовалась реализация на C++.
После медленной сортировки на [1,100] алгоритм снова выполняется быстрее на [1,1260].

Визуализация алгоритма Comb Sort.
Сортирует случайный набор целых чисел [1,100] с помощью алгоритма Comb Sort https://en.wikipedia.org/wiki/Comb_sort.

Визуализация алгоритма четно-нечетной сортировки.
Сортировка случайного набора целых чисел [1,100] с помощью четно-нечетной сортировки.

Визуализация алгоритма сортировки Батчера.
Сортирует случайную перестановку целых чисел [1,128] и [1,1260] с помощью битонической сортировки, которая представляет собой параллельную сортировочную сеть, где каждая перестановка слева направо может быть выполнена полностью параллельно https://en.wikipedia.org/wiki/Bitonic_sorter.

Визуализация алгоритма четно-нечетное Бэтчера.
Сортирует случайную перестановку целых чисел [1,128] и [1,1260] с помощью сети mergesort, которая является параллельной сортировочной сетью, где каждая перестановка слева направо может быть выполнена полностью параллельно https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort.

Визуализация алгоритма плавной сортировки.
Сортирует случайный набор целых чисел [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.
Сортирует случайный набор целых чисел [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.
Алгоритм представляет собой алгоритм сортировки на основе транспонирования на месте, который всегда требует минимального количества записей в массив.
Он достигает этого путем вычисления ранга каждого элемента и перестановки его в нужную позицию.

 

Возможно вам будет интересно:

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

# Алгоритмы сортировки