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

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

Вам задан массив, который почти сортирован, поскольку каждый из элементов 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)? Можно ли это улучшить?
  • Можете ли вы сделать это без (частично) повторной сортировки одних и тех же элементов?

Ответы

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

Ответ 4

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

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

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

Ответ 5

Уже указывалось, что одно из асимптотически оптимальных решений использует кучу минут, и я просто хотел предоставить код в 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();
  }
}