Алгоритм сортировки массива для первого элемента, затем для первых 2 элементов, затем для первых 3 элементов и т. Д.

Question

У меня есть список несортированных чисел, и я хочу алгоритм, чтобы я мог получить отсортированный список первых элементов R, но так как этот R может отличаться для разных тестовых случаев, я не хочу сортировать массив каждый раз для первого Rэлементы.Есть ли способ, которым я могу сделать это.Один из возможных способов - сохранить векторный массив таким образом, чтобы сначала были отсортированы 1 номер, затем отсортированы первые 2 номера, затем отсортированы первые 3 номера и т. Д., Но это займет 1log1 + 2log2 + 3log3 + .... + nlogn время, равное N ^2logN сложность.Возможен ли более быстрый путь к этому?

Answer 1

Мы могли бы занять O(n log n) пробел, чтобы сохранить частичные результаты сортировки слиянием.Тогда верхняя граница для возврата первых отсортированных R элементов будет похожа на объединение log n отсортированных списков.Я нашел одну ссылку для объединения k отсортированных списков общей длины n в O(n * log k), что сделало бы наши O(n * log log n), но, надеюсь, многие из запросов будут еще более эффективными.

13,15,12,4,18,1,23,17,6,2 ->

| 1   2   4   6   12   13   15   17   18   23 |
| 4   12   13   15   18 | 1   2   6   17  23  | 
| 13  15  | 4   12   18 | 1   23 | 2   6  17  |
| 13 | 15 | 12 | 4 | 18 | 1 | 23 | 17 | 6 | 2 |

Answer 2

Вы можете попробовать быструю сортировку, но не делать это полностью.Я слышал, что Haskell делает это аналогичным образом.

Это почти обычная быстрая сортировка, но вы откладываете работу, которую можно отложить.

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

Время для первого элемента будет O(n) (и вряд ли вы получите что-то лучше), все время будет O(n * log n).

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

Исправление:если вам нужно каждый раз выводить весь подмассив, это будет O(n^2), только если вы выводите по номеру за раз - это будет O(n * log n).

Answer 3

Кажется, что старый добрый сортировщик вставки будет лучше, чем O (N ^ 2 lg N) в этом случае, потому что вам не нужно сортировать элементы с нуля для каждого R.Представьте, что у вас есть копия отсортированных первых n элементов массива для n в 1..R-1.Просто вставьте R -й элемент в копию отсортированного массива R-1 первых элементов (это O (R)), и вы получите отсортированный массив R первых элементов.

Это O (N ^ 2), если вы хотите получить результат для каждого R в 1..N, но на практике это будет меньше, чем O (N ^ 2), потому что вы можете создавать отсортированные массивы по требованию, начиная споследний отсортированный массив с меньшим количеством элементов, чем R.