## List Of Sorting Algoritms

1. [Как работают сортировки?](https://www.youtube.com/watch?v=PF7AqefS4MU&ab_channel=AlekOS)

Самое очевидное и простое решение какой-либо задачи называется «наивный алгоритм» — это устоявшийся термин.

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

1. [Bubble sort](https://habr.com/ru/articles/204600/)

Или сортировка простыми обменами. Бессмертная классика жанра. Принцип действий прост: обходим массив от начала до конца, попутно меняя местами неотсортированные соседние элементы. В результате первого прохода на последнее место «всплывёт» максимальный элемент. Теперь снова обходим неотсортированную часть массива (от первого элемента до предпоследнего) и меняем по пути неотсортированных соседей. Второй по величине элемент окажется на предпоследнем месте. Продолжая в том же духе, будем обходить всё уменьшающуюся неотсортированную часть массива, запихивая найденные максимумы в конец.

![Bubble sort](https://habrastorage.org/getpro/habr/post_images/187/5a3/929/1875a3929dd14c8ea5ff4ccc3d0db9bd.gif)

Если не только в конец задвигать максимумы, а ещё и в начало перебрасывать минимумы то у нас получается…

## Шейкерная сортировка / Shaker sort

1. [Shaker sort](https://habr.com/ru/articles/204600/)

Она же сортировка перемешиванием, она же коктейльная сортировка. Начинается процесс как в «пузырьке»: выдавливаем максимум на самые задворки. После этого разворачиваемся на 1800 и идём в обратную сторону, при этом уже перекатывая в начало не максимум, а минимум. Отсортировав в массиве первый и последний элементы, снова делаем кульбит. Обойдя туда-обратно несколько раз, в итоге заканчиваем процесс, оказавшись в середине списка.

![Shaker sort](https://habrastorage.org/getpro/habr/post_images/2a9/ad7/855/2a9ad78556f13396ebc68cb4ac21e91c.gif)

Шейкерная сортировка работает немного быстрее чем пузырьковая, поскольку по массиву в нужных направлениях попеременно мигрируют и максимумы и минимумы. Улучшения, как говорится, налицо.

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

## Сортировка расческой / Comb sort

1. [Comb sort](https://habr.com/ru/articles/204600/)

В «пузырьке», «шейкере» и «чёт-нечете» при переборе массива сравниваются соседние элементы. Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального. Таким образом мы как бы причёсываем массив, постепенно разглаживая на всё более аккуратные пряди.

![Comb sort](https://habrastorage.org/getpro/habr/post_images/15b/1bb/37e/15b1bb37e7d06fc9d2ccd8adb34b8980.gif)

Модификация сортировки пузырьком. Для того, чтобы избавиться от «черепах», будем переставлять элементы, стоящие на расстоянии. Зафиксируем его и будем идти слева направо, сравнивая элементы, стоящие на этом расстоянии, переставляя их, если необходимо. Очевидно, это позволит «черепахам» быстро добраться в начало массива. Оптимально изначально взять расстояние равным длине массива, а далее делить его на некоторый коэффициент, равный примерно 1.247. Когда расстояние станет равно единице, выполняется сортировка пузырьком. 

В лучшем случае асимптотика равна O(nlogn), в худшем – O(n2). Какая асимптотика в среднем мне не очень понятно, на практике похоже на O(nlogn).

## Сортировка выбором / Selection sort

Просто и незатейливо — проходим по массиву в поисках максимального элемента. Найденный максимум меняем местами с последним элементом. Неотсортированная часть массива уменьшилась на один элемент (не включает последний элемент, куда мы переставили найденный максимум). К этой неотсортированной части применяем те же действия — находим максимум и ставим его на последнее место в неотсортированной части массива. И так продолжаем до тех пор, пока неотсортированная часть массива не уменьшится до одного элемента.

![Selection sort](https://habrastorage.org/webt/yt/cs/fz/ytcsfzyhzn9xy8opfyodmgz-a4u.gif)

Сортировка простым выбором представляет из себя грубый двойной перебор. Можно ли её улучшить? Разберём несколько модификаций.

## Двухсторонняя сортировка выбором / Double selection sort

![Double selection sort](https://habrastorage.org/webt/jj/xn/kq/jjxnkqnbcbgwtqhxq9_p99kwmdi.gif)

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

## Быстрая сортировка, сортировка Хоара / Quick sort

Быстрый метод сортировки функционирует по принципу "разделяй и властвуй".

![Quick sort](https://thecode.media/wp-content/uploads/2022/04/sorting_quicksort_anim.gif)

> Синяя линия — это значение опорного элемента, а серый блок показывает, какую часть массива сортирует алгоритм

Так как на третьем шаге мы разбиваем массив на два и для каждой части делаем то же самое, и так снова и снова, то это значит, что в нём используется [рекурсия](../../2.2%20Languages/2.2.2%20Paradigm/2.2.2.1%20Declarative/2.2.2.1.1%20FunctionalProgramming(FP).md).

---

[2.1.4 Leetcode Theme Folder](../2.1.4%20Leetcode/) | [Back To iTWiki Contents](https://github.com/eldaroid/iTWiki) | [2.2 Languages Theme Folder](../../2.2%20Languages/)