Сортировка массива в O (n log (log n))

Question

Я пытаюсь решить следующее задание: мне дан массив из n элементов.Известно, что не все ключи массива различны, но дано, что у нас есть k различных элементов (конечно, k <= n).назначение состоит в том, чтобы выполнить сортировку массива <strong>stable в худшем случае O (n log (log n)), а k = O (log n).Мне разрешено использовать O (n) дополнительной памяти.

Мое текущее решение описано ниже:

---

Создать хеш-таблицу с цепочкой размера k, которая выполняет следующие действия: ifхеш-функция пытается вставить элемент в место, в котором уже есть значение - она ​​проверяет, равны ли они, - если они есть, то добавляет его в список, если нет, то начинает перемещаться в массиве, пока не найдет место, котороеимеет то же значение или пустой пробел (который всегда идет первым).

Таким образом, списки в каждом месте содержат только элементы с одинаковыми ключами.вставка в хеш-таблицу происходит от начала до конца в исходном массиве, поэтому каждый список сортируется стабильно.Затем сортируйте массив в хеш-таблице с помощью mergeSort (для списков мы рассматриваем первый элемент как один и перемещаем его).

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

Вот в чем я не уверен:

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

Потому что, если это так, кажется, что время выполнения алгоритма равно O (n + k log k) = O (n + log n * log (log n)).что определенно лучше, чем O (n log k), что и требовалось.

Answer 1

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

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

• начальный индекс для элемента i = начальный индекс для элемента i-1 + счет для элемента i-1.

Этот шаг требует сортировки k элементов в хеш-таблице, что составляет O (k log k) = O (log n log log n) операций, намного меньше, чем O (n) для шагов 1 и 3.

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

Если значения сравнения для элементов являются последовательными целыми числами (или целыми числами в некоторых маленькихдиапазон), то вы можете использовать массив вместо хеш-таблицы для подсчета.

Это называется сортировка подсчета .