Есть ли способ пропустить пустые корзины во время сортировки?

Question

Подсчет сортировки - это сортировка ведра. Давайте предположим, что мы используем это так:

• Пусть A будет массив для сортировки
• Пусть k будет максимальным элементом
• Пусть bucket[] будет массивом ведер
• Пусть каждый сегмент представляет собой связанный список (с указателем начала и конца)

Тогда в псевдокоде счетная сортировка выглядит так:

Counting-Sort (A[], bucket[], k)

1.  Init bucket[]
2.  for i -> 1 to n
3.        add A[i] to bucket[A[i].key].end
4.  for i -> 1 to k
5.        concatenate bucket[i].start to bucket[0].end
6.        bucket[0].end=bucket[i].end
7.  copy bucket[0] to A

Сложность времени по строкам:

1) Я знаю, что есть способ (не простой, но способ) инициализировать массив в O (1)

2,3) O (n)

4,5) O (k)

6) O (n)

Это дает нам чистое время выполнения O (k + n), которое для k >> n равно & Omega; (n), что плохо для нас. Но что, если мы можем изменить строки 4,5, чтобы как-то пропустить пустые сегменты? Таким образом, в итоге у нас не будет O (n) метра, чем является k.

Кто-нибудь знает, как это сделать? Или это невозможно?

Answer 1

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

Если есть z блоков, которые фактически используются, это занимает O (n + z log z).Если количество сегментов велико по сравнению с фактически используемым количеством, это может быть намного быстрее.

В более общем случае - если у вас есть способ сортировки z различных сегментов, используемых в O (f (z))время, вы можете выполнить сортировку сегмента за O (n + f (z)).Поддерживайте второй массив блоков, которые вы фактически используете, добавляя сегмент в массив, когда он используется в первый раз.Прежде чем выполнять итерации по сегментам, отсортируйте по времени O (f (z)) индексы используемых блоков, а затем выполните итерацию по всему массиву, чтобы определить, какие сегменты следует посетить.Например, если вы использовали y-быстрые деревья, вы можете отсортировать по O (n + z log log z).

Надеюсь, это поможет!

Answer 2

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

O ( n ) в общем случае невозможно.