Отсортируйте массив из n элементов, чтобы первые k-элементы были самыми низкими в порядке возрастания (алгоритм на месте)

Question

Это домашний вопрос, на котором я застрял.

Мне нужно отсортировать массив из n элементов, чтобы первые k-элементы были самыми низкими и находились в порядке возрастания. Для k <= n/log(n) алгоритм должен быть O(n).

Мои решения: простое решение, о котором я подумал, - это сложить (O (n)) массив. Затем удалите k-элементы и измените начальный индекс кучи / массива с 0 на 1 - 2 - 3 (и так далее до k). Это будет O(n+k*lg(n)+k*n) = O(kn+k*lg(n)). Для данного условия k это будет O(n^2/log(n) + n).

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

Вы не должны давать мне ответ, просто подсказка будет полезна.

Answer 1

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

Предположим, вы делаете следующее: создаете кучу на месте в вашем массиве, затем снимаете с очереди минимальное количество k элементов, оставляя оставшиеся n - k элементов там, где они находятся в массиве. Если вы подумаете о том, где будут располагаться элементы, у вас должно быть k наименьших элементов в массиве, хранящихся в конце массива в порядке возрастания, а n - k оставшихся элементов будут впереди, в порядке кучи. Если у вас возникли проблемы с отображением этого, подумайте о том, как работает heapsort - после k dequeues самые большие k элементов располагаются в порядке убывания сзади, а остальные элементы располагаются в куче спереди. Здесь мы обменяли минимальную кучу на максимальную кучу, отсюда и странный порядок. В результате, если вы затем перевернете массив в конце, вы должны иметь k наименьших элементов в порядке возрастания спереди, а затем n - k оставшихся элементов.

Это позволит правильно найти k наименьших элементов, а время выполнения определяется следующим образом:

• Стоимость кучи: O(n)
• Стоимость k очереди: O(k log n)
• Стоимость обращения массива: O(n)
• Общая стоимость: O(n + k log n)

Теперь предположим, что k ≤ n / log n. Тогда время выполнения

O(n + k log n) = O(n + (n / log n) log n) = O(n)

Итак, вы сделали! Алгоритм работает просто отлично. Кроме того, для этого требуется O(1) вспомогательное пространство (куча может быть встроена на месте, и можно обратить массив в пространство O(1)).

Вы можете сделать лучше, хотя. @timrau предложил в комментариях использовать быстрый выбор (или, в более общем случае, любой алгоритм выбора с линейным временем). Эти алгоритмы переставляют массивы, чтобы расположить самые младшие k элементов в некотором порядке в первых k слотах массива, а остальные n - k элементов в последних n - k слотах в некотором порядке. Это занимает время O (n) независимо от k (изящно!). Предположим, вы делаете это, а затем просто сортируете первые k элементов. Это занимает время O(n + k log k), которое асимптотически лучше, чем алгоритм на основе кучи времени O (n + k log n).

Из известных алгоритмов линейного выбора как быстрый выбор, так и алгоритм медианы медианы могут быть реализованы на месте, если вы будете осторожны, поэтому общее пространство, необходимое для этого подхода, составляет O(1).

Answer 2

Мне приходит в голову, что вы можете сделать это на месте с немного измененным алгоритмом выбора кучи, который является O(n log k). Хотя асимптотически "хуже", чем сложность Quickselect O(n), выбор кучи может превзойти Quickselect, когда k очень мало по сравнению с n. Посмотрите, Когда теория встречает практику для деталей. Но если вы выбираете, скажем, 1000 лучших элементов из списка из миллиона, выбор кучи почти наверняка будет быстрее.

В любом случае, чтобы сделать это на месте, вы строите max-heap (используя стандартную функцию BuildHeap) размера k в начале массива из первых k элементов массива. Это занимает O (K). Затем вы обрабатываете остальные элементы в массиве следующим образом:

for (i = k; i < length; ++i)
{
    if (array[i] < array[0])  // If item is smaller than largest item on heap
    {
        // put large item at the current position
        temp = array[i];
        array[i] = array[0];

        // put new item at the top of heap and sift it down
        array[0] = temp;
        SiftDown(0);
    }
}

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

Когда все готово, самые маленькие k элементов находятся в начале массива.

Затем вы должны отсортировать их, что O(k log k).

Таким образом, полная процедура O(k + n log k + k log k). Опять же, когда k намного меньше n, это значительно быстрее, чем Quickselect.