Сортировка чисел сразу против каждого генерируется

Question

Существуют ли какие-либо алгоритмы, которые выигрывают в сложности по времени, помещая каждый элемент в список в отсортированном порядке, поскольку они генерируются по сравнению с генерацией всего списка и просто с использованием быстрой сортировки на полностью несортированном готовом продукте?

I ' Я думаю, нет, так как если бы это было так, то вы могли бы просто перебрать несортированный список, используя этот алгоритм, чтобы разбить быструю сортировку, но мне было интересно, если я был неправ.

Answer 1

За запросы ОП, переместив мой комментарий к ответу. В случае поиска предположение о том, что предварительно отсортированы, ничего не дает (в отличие от задачи поиска). Наиболее эффективный способ найти правильное место для элемента в отсортированном списке - это двоичный поиск, который является O (log n), вы делаете это для n элементов. Вы все еще получаете O (nlgn). У нас есть очень веские доказательства того, что мы НЕ МОЖЕМ делать лучше, чем O (nlgn), для определенной сортировки на основе сравнения. Обратите внимание, что есть алгоритмы, которые, как мы знаем, работают в O (n) на среднем с наихудшим случаем, все еще равным O (nlgn), например, Smooth Sort. Однако есть разница между предварительно отсортированными и поступающими в случайном порядке элементами и вставкой отсортированного подсписка

. Вы можете прочитать об этом чуть подробнее:

Generi c и практичный алгоритм сортировки быстрее, чем O (n log n)?

https://cs.stackexchange.com/questions/80458/can-we-create-faster-sort-algorithm-than-on-log-n

Конечно, вы можете сделать случайный алгоритм, где вы случайным образом сортируете & надеюсь на лучшее. У нас действительно есть методы, которые мы можем использовать для манипулирования вероятностями, так что вероятность получения нужного нам элемента очень близка к 1, а вероятность выбора других элементов очень близка к 0. Вот как мы получаем O ( √N) поиск в списке несортированный в квантовом поиске (есть недавние свидетельства того, что это может быть достигнуто на обычных компьютерах, но еще не было успешно реализовано)

если мы однажды найти более эффективный алгоритм сортировки, это будет тот, который волшебным образом делает это без сравнения элементов. Этот инвариант настолько силен, что даже с квантовой сортировкой мы не знаем, как сделать лучше, чем O (nlgn) на данный момент. Есть исключения из этого в ограниченной в пространстве сортировке

Answer 2

Если вы не непреклонны в использовании списка, то дерево бинарного поиска имеет сложность вставки O(log(n)) и будет в порядке к концу вставок. Однако это приведет к дополнительным расходам и, следовательно, будет использовать этот подход только в том случае, если вам абсолютно необходимо знать порядок сортировки элементов после каждой вставки.

Скажите, что вам нужно находить индекс вставленного элемента после каждой вставки. Обратите внимание, что вставка в отсортированный список по желаемому индексу займет O(n), так как вам придется сдвигать большие элементы вправо, чтобы освободить место.

Answer 3

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