Сортировка почти отсортированного массива (элементы не более чем на k)

Question

Мне недавно задали этот вопрос:

Вам дан почти отсортированный массив, в котором каждый из элементов N может быть смещен не более чем на k позиций из правильного отсортированного порядка. Найдите эффективный по пространству и времени алгоритм сортировки массива.

У меня есть решение O(N log k) следующим образом.

Обозначим arr[0..n), чтобы обозначить элементы массива от индекса 0 (включительно) до N (исключая).

• Сортировка arr[0..2k)
  • Теперь мы знаем, что arr[0..k) находятся в своих окончательно отсортированных позициях ...
  • ... но arr[k..2k) все еще может быть не на месте k!
• Сортировка arr[k..3k)
  • Теперь мы знаем, что arr[k..2k) находятся в своих окончательно отсортированных позициях ...
  • ... но arr[2k..3k) все еще может быть не на месте k
• Сортировка arr[2k..4k)
• ....
• Пока вы не сортируете arr[ik..N), тогда все готово!
  • Этот последний шаг может быть дешевле, чем другие шаги, если у вас осталось менее 2k элементов

На каждом шаге вы сортируете не более 2k элементов в O(k log k), помещая не менее k элементов в их окончательные отсортированные позиции в конце каждого шага. Есть O(N/k) шагов, поэтому общая сложность составляет O(N log k).

Мои вопросы:

• Является ли O(N log k) оптимальным? Можно ли это улучшить?
• Можете ли вы сделать это без (частичной) повторной сортировки тех же элементов?

Answer 1

Как показал Боб Седжвик в своей диссертационной работе (и последующих), сортировка вставок абсолютно уничтожает"почти отсортированный массив". В этом случае ваши асимптотики выглядят хорошо, но если k <12, я уверен, что сортировка вставок выигрывает каждый раз. Я не знаю, есть ли хорошее объяснение для <em>, почему сортировка вставками так хорошо справляется, но найти место было бы в одном из учебников Седжвика под названием Алгоритмы (он сделал много изданий для разных языков).

• Я понятия не имею, является ли O (N log k) оптимальным, но более важно, что мне все равно - если k мало, то постоянные факторы имеют значение, а если k велико , вы также можете просто отсортировать массив.

• Сортировка вставками поможет решить эту проблему без повторной сортировки тех же элементов.

Нотация Big-O очень хорошо подходит для класса алгоритма, но в реальном мире константы имеют значение. Это слишком легко упустить из виду. (И я говорю это как профессор, который преподавал нотацию Big-O!)

Answer 2

Если используется только модель сравнения, O (n log k) является оптимальным. Рассмотрим случай, когда k = n.

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

Используйте min-heap из 2k элементов. Сначала вставьте 2k элементов, затем удалите min, вставьте следующий элемент и т. Д.

Это гарантирует, что O (n log k) времени и O (k) пространства и куч обычно имеют достаточно маленькие скрытые константы.

Answer 3

Уже отмечалось, что одно из асимптотически оптимальных решений использует кучу минимальных значений, и я просто хотел предоставить код на Java:

public void sortNearlySorted(int[] nums, int k) {
  PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  for (int i = 0; i < k; i++) {
    minHeap.add(nums[i]);
  }

  for (int i = 0; i < nums.length; i++) {
    if (i + k < nums.length) {
      minHeap.add(nums[i + k]);
    }
    nums[i] = minHeap.remove();
  }
}

Answer 4

Ваше решение будет хорошим, если k достаточно велико. Нет лучшего решения с точки зрения сложности времени; каждый элемент может быть неуместен на k мест, что означает, что вам нужно выучить log2 k битов информации, чтобы правильно разместить его, что означает, что вам нужно как минимум log2 k сравнений - так что это сложность не менее O(N log k).

Однако, как уже отмечали другие, если k мало, постоянные члены убьют вас. Используйте что-то очень быстрое для каждой операции, например сортировку вставкой, в этом случае.

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

Answer 5

Поскольку k, по-видимому, должно быть довольно маленьким, сортировка вставкой, вероятно, является наиболее очевидным и общепринятым алгоритмом.

При вставке сортировки по случайным элементам вам нужно сканировать N элементов, и вы должны перемещать каждое из них в среднем по N / 2 позициям, что дает ~ N * N / 2 всего операций. Константа "/ 2" игнорируется в характеристике big-O (или аналогичной), что приводит к сложности O (N ² ).

В случае, если вы предлагаете, ожидаемое число операций составляет ~ N * K / 2 - но поскольку k является константой, весь член k/2 игнорируется в характеристике big-O, поэтому общая сложность O (N).