Сортировка частично отсортированного массива в O (n)

Question

Эй, я просто застрял в этом вопросе.

Мне нужно разработать алгоритм (не нужно кода), который сортирует определенный частично отсортированный массив в полностью отсортированный массив. Массив имеет N действительные числа , и первые N- [N \ sqrt (N)] ([] обозначает floor этого числа) отсортированы, а остальные не. У несортированных чисел в конце нет никаких специальных свойств, на самом деле мне ничего не сказано о них, кроме, очевидно, что они настоящие числа, как и остальные.

Кикером является сложность времени, для алгоритма должно быть O (n).

Моей первой мыслью было попытаться отсортировать только несортированные числа, а затем использовать алгоритм слияния, но я не могу найти какой-либо алгоритм сортировки, который бы работал здесь в O (n). Так что я думаю, что все это неправильно, есть идеи?

Answer 1

Другими словами, это означает, что в конце массива находятся несортированные элементы sqrt (N). Вы можете отсортировать их с помощью алгоритма O (n ^ 2), который даст время O (sqrt (N) ^ 2) = O (N); затем сделайте слияние, которое вы упомянули, которое также будет выполняться в O (N). Поэтому оба шага вместе займут всего O (N).

Answer 2

В общем случае это невозможно при использовании алгоритма сортировки на основе сравнения. Скорее всего, вы что-то упускаете из вопроса.

Представьте себе частично отсортированный массив [1, 2, 3, 4564, 8481, 448788, 145, 86411, 23477]. Он содержит 9 элементов, первые 3 из которых отсортированы (обратите внимание, что floor(N/sqrt(N)) = floor(sqrt(N)) при условии, что вы имели в виду N/sqrt(N) и floor(sqrt(9)) = 3). Проблема в том, что все несортированные элементы находятся в диапазоне, который не содержит отсортированные элементы. Это делает отсортированную часть массива бесполезной для любого алгоритма сортировки, поскольку они все равно останутся там (или будут перемещены до самого конца в случае, когда они больше, чем несортированные элементы).

При таком типе ввода вам все равно нужно независимо отсортировать N - floor(sqrt(N)) элементов. И, насколько я знаю, N - floor(sqrt(N)) ~ N (~ в основном означает «та же сложность, что и»). Таким образом, у вас остается массив из приблизительно N элементов для сортировки, что занимает O(N log N) время в общем случае.

Теперь я указал «использование алгоритма сортировки на основе сравнения», потому что сортировка действительных чисел ( в некотором диапазоне , как и обычные числа с плавающей запятой, хранящиеся в компьютерах) может выполняться в амортизированной форме O(N) время использования сортировки по хешу (аналог сортировки по счету) или, возможно, даже модифицированной сортировки по основанию, если все сделано правильно. Но тот факт, что часть массива уже отсортирована, не помогает.