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

Tim Sort

Это высокоэффективный и стабильный алгоритм сортировки,, который сочетает в себе элементы сортировки слиянием и сортировки вставками.

Алгоритм:
1. Разделение входного массива на более мелкие сегменты, называемые «runs». Минимальный размер run (minrun) определяется на основе n, исходя из следующих принципов:
- Не должно быть слишком большим, тк в дальнейшем применена сортировка вставками
- Не должно быть слишком маленьким, так как чем меньше run, тем больше итераций слияния придётся выполнить.
- Оптимальная величина n/minrun - степень двойки
2. Сортировка runs с помощью сортировки вставками.
3. Объединение соседних runs с помощью сортировки слияния

Сложность алгоритма:
В лучшем случаи: O(n)
В cреднем: O(n logn)
В худшем: O(n logn)

www.tgoop.com/the_algorithms/4562

8.4K viewsSep 30, 2023 at 09:03

Tim Sort

Это высокоэффективный и стабильный алгоритм сортировки,, который сочетает в себе элементы сортировки слиянием и сортировки вставками.

Алгоритм:
1. Разделение входного массива на более мелкие сегменты, называемые «runs». Минимальный размер run (minrun) определяется на основе n, исходя из следующих принципов:
- Не должно быть слишком большим, тк в дальнейшем применена сортировка вставками
- Не должно быть слишком маленьким, так как чем меньше run, тем больше итераций слияния придётся выполнить.
- Оптимальная величина n/minrun - степень двойки
2. Сортировка runs с помощью сортировки вставками.
3. Объединение соседних runs с помощью сортировки слияния

Сложность алгоритма:
В лучшем случаи: O(n)
В cреднем: O(n logn)
В худшем: O(n logn)

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