Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=418322&view=findpost&p=3831381 Mon, 25 May 2020 10:16:40 +0000 Как оцениваются комбинированные алгоритмы сортировки? https://forum.sources.ru/index.php?showtopic=418322&view=findpost&p=3831381 Либо это выбор одного из существующих алгоритмов, в зависимости от размера данных, как говорил MBo
Либо это что-то объединенное, "закрученное", как пишет amk.
Ну, а так, можно построить график зависимости от тестов. Визуально определить чем его описать. :lol:]]> Black_Dragon Алгоритмы https://forum.sources.ru/index.php?showtopic=418322&view=findpost&p=3829308 Sun, 26 Apr 2020 16:08:56 +0000 Как оцениваются комбинированные алгоритмы сортировки? https://forum.sources.ru/index.php?showtopic=418322&view=findpost&p=3829308
Для начала ищутся строго убывающие последовательности. Эти последовательности сортируются просто обратной перестановкой.
Потом производится разбивка на возрастающие серии, составляется оптимальный порядок объединения. Первыми при этом объединяются короткие пары.
Объединение производится методом слияния (слияние может производиться как слева направо, так и справа налево, в зависимости от того какая из сливаемых последовательность короче).
В некоторых случаях быстрее произвести слияние методом вставок (когда одна из последовательностей имеет длину один или два элемента).

Это для обычной, возрастающей сортировки.

Добавлено
Производится это параллельно по мере обнаружения описанных подцепочек]]> amk Алгоритмы https://forum.sources.ru/index.php?showtopic=418322&view=findpost&p=3829224 Sat, 25 Apr 2020 06:24:19 +0000 Как оцениваются комбинированные алгоритмы сортировки? https://forum.sources.ru/index.php?showtopic=418322&view=findpost&p=3829224
Таким образом общее время немного уменьшается, сложность O(n*log(n)) сохраняется, потому что на вставки тратится в данном случае n/100 * 100^2 = 100*n - т.е. линейное время от общего количества элементов.]]> MBo Алгоритмы https://forum.sources.ru/index.php?showtopic=418322&view=findpost&p=3829128 Fri, 24 Apr 2020 15:55:29 +0000 Как оцениваются комбинированные алгоритмы сортировки? https://forum.sources.ru/index.php?showtopic=418322&view=findpost&p=3829128
Собственно - сабж. Давайте на примере Timsort. Вот цитата из вики:

Цитата
Сортировка Timsort (англ. Timsort) — комбинированный алгоритм (используется сортировка вставками и сортировка слиянием). Сложность алгоритма: O(n*log(n)). Требуется O(n) дополнительной памяти. Разработан для использования в языке Python[14].

Собственно, вопрос: сабж!

В данном случае имеем два алгоритма, которые "сочетаем":

1) Сортировка вставками - вычислительная сложность O(n²)
2) Сортировка слиянием - вычислительная сложность O(n*log(n))

Откуда - результирующий O(n*log(n))?]]> JoeUser Алгоритмы