Как можно модифицировать алгоритм(например выбором) сортировки , так чтобы наилучшее время работы стало $%O(n\log n)$%?

задан 17 Июн 23:31

1

@lawyer: об алгоритмах сортировки написаны горы литературы. Можно посмотреть хоть популярные статьи, хоть монографию Кнута (том "Получисленные алгоритмы"). По-моему, O(n log n) можно получить за счёт рекурсивного алгоритма: делим массив на две части, каждую сортируем, потом два упорядоченных массива сливаем в один. Но все эти вещи хорошо известны.

(17 Июн 23:56) falcao

@falcao: понял я поищу, но вопрос был про лучшее время работы(тоесть когда массив уже отсортирован) такого алгоритма я пока не видел

(19 Июн 1:09) lawyer

@lawyer: если массив уже отсортирован, то в чём состоит задача?

(19 Июн 1:48) falcao

@falcao, когда вы скармливаете массив алгоритму, он не знает, отсортирован уже массив или нет. И иногда бывает такое, что если подать ему на вход уже отсортированный массив, то время работы будет наихудшим. В частности, такое происходит с самым эффективным на данный момент алгоритмом -- быстрой сортировки Хоара. Его асимптотическая верхняя граница -- O(n^2) (как раз за n^2 он будет работать, если подать ему уже отсортированный массив), тем не менее в общем случае его сложность тяготеет к O(nlog(n)), и он оказывается воистину самым эффективным.

(19 Июн 2:15) haosfortum

@haosfortum: в случае, если массив может по тем или иным причинам оказаться уже отсортированным, можно добавить предварительную проверку на это свойство, что требует линейного времени работы.

(19 Июн 10:11) falcao

@falcao, наверное, можно, но это довольно бессмысленно, так как шанс такого -- 1 к n!. К тому же массив может быть "почти отсортирован", т.е., скажем, для сортировки не хватает одной транспозиции. И тогда все равно некоторые алгоритмы будут долго работать.

(19 Июн 12:50) haosfortum

@lawyer, я не уверен, что понимаю, о чем ваш вопрос. Я сомневаюсь, что есть универсальный способ модификации любого алгоритма сортировки до сложности O(nlog(n)), у каждого алгоритма своя специфика и свои модификации. Скажем, отчасти пирамидальную сортировку можно назвать модификацией алгоритма сортировки выбором за квазилинейное время. Тут все зависит от того, что конкретно вы хотите.

(19 Июн 12:57) haosfortum

@haosfortum: я к тому, что если требуется какую-то мелкую трудность устранить, то для этого всегда есть подходящие средства. Другое дело, что они в каждом случае свои, и нет универсально годящегося. Так или иначе, задача здесь не поставлена как следует, и те трудности, которые надо преодолевать, обрисованы лишь в общих чертах.

(19 Июн 13:16) falcao
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×4,223
×293

задан
17 Июн 23:31

показан
110 раз

обновлен
19 Июн 13:16

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru