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

Шейкерная сортировка

Простой алгоритм сортировки, являющийся разновидностью алгоритма пузырьковой сортировки.

Алгоритм:
1. Проход вправо:
- Сравниваем соседние элементы с крайнего левого элемента.
- Если текущий элемент больше следующего элемента, меняем их местами.
- Продолжайте этот процесс, перемещаясь слева направо, пока не дойдете до конца списка. После этого прохода самый большой элемент «всплывает» в конец списка.

2. Проход влево:
- Теперь выполните проход справа налево, сравнивая и меняя местами соседние элементы.
- Если текущий элемент меньше предыдущего, поменяйте их местами.
- Продолжайте этот процесс, перемещаясь справа налево, но остановитесь перед последним отсортированным элементом. После этого прохода наименьший элемент «всплывает» в начало списка.

Сложность:
В лучшем: O(n)
В худшем: O(n^2)

www.tgoop.com/the_algorithms/4564

7.9K viewsOct 3, 2023 at 08:59

Шейкерная сортировка

Простой алгоритм сортировки, являющийся разновидностью алгоритма пузырьковой сортировки.

Алгоритм:
1. Проход вправо:
- Сравниваем соседние элементы с крайнего левого элемента.
- Если текущий элемент больше следующего элемента, меняем их местами.
- Продолжайте этот процесс, перемещаясь слева направо, пока не дойдете до конца списка. После этого прохода самый большой элемент «всплывает» в конец списка.

2. Проход влево:
- Теперь выполните проход справа налево, сравнивая и меняя местами соседние элементы.
- Если текущий элемент меньше предыдущего, поменяйте их местами.
- Продолжайте этот процесс, перемещаясь справа налево, но остановитесь перед последним отсортированным элементом. После этого прохода наименьший элемент «всплывает» в начало списка.

Сложность:
В лучшем: O(n)
В худшем: O(n^2)

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