какой алгоритм может сделать стабильное двоичное разбиение на месте только с O (N) ходами?

Question

Я пытаюсь понять эту статью: Стабильное минимальное разбиение пространства в линейном времени.

Кажется, что критическая часть утверждения состоит в том, что

Алгоритм B стабильно сортирует битовый массив размером n в O (nlog ₂ n) времени и постоянного дополнительного пространства,но делает только O (n) ходов.

Однако, статья не описывает алгоритм, а только ссылается на другую статью, к которой у меня нет доступа.Я могу найти несколько способов сделать сортировку в пределах временного интервала, но у меня возникают проблемы с поиском того, который гарантирует O (N) перемещений, не требуя также больше, чем постоянное пространство.

Что это за алгоритм B?Другими словами, с учетом

boolean Predicate(Item* a);  //returns result of testing *a for some condition

существует ли функция B(Item* a, size_t N);, которая стабильно сортирует a , используя Predicate в качестве ключа сортировки с меньшим, чем nlog ₂ n вызывает Predicate и выполняет только O (N) записи в a ?

Answer 1

Мне хочется сказать, что это невозможно.Каждый раз, когда вы вычисляете O (n log n) количество информации, но у вас (1) негде ее спрятать (постоянное пространство) и (2) негде сразу ее использовать (O (n) перемещается), происходит что-то странноеon, возможно, подразумевает интенсивное использование стека (которое может не учитываться при анализе пространства, хотя и должно быть).

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

Сортировка по радикалам не вполне сделает это, потому что вам придется вызывать предикат для создания цифр, и если выне запоминайте транзитивность сравнения, тогда вы назовете это O (n ^ 2) раз.(Но я думаю, что для запоминания требуется O (log n) амортизированного пространства на единицу.)

QED - доказательство отсутствия воображения:)

Answer 2

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

int getDest(int i, BitArray p, int nz)
{   bool b=BitArrayGet(p,i);
    int below = BitArrayCount1sBelow(p,i);  //1s below
    return (b)?(nz+below):i-below;
}

int BinaryCycleSort(Item* a, int n, BitArray p)
{
   int i, numZeros = n-BitArrayCount1sBelow(p,n);
   BitArray final = BitArrayNew(n);
   for (i=0;i<numZeros;i++)
      if (!BitArrayGet(final,i))
      {  int dest= GetDest(i,p,numZeros);
         while (dest!=i)                
         {  SwapItem(a+i,a+dest); 
            BitArraySet(final,dest);
            dest = getDest(dest,p,numZeros);
         }
         BitArraySet(final,dest);
      }
   return numZeros;
}

int BinaryPartition(Item* a, int n, Predicate pPred)
{ 
   int i;
   BitArray p = BitArrayNew(n);
   for (i=0;i<n;i++)
      if (pPred(a+i)) BitArraySet(p,i);
   return BinaryCycleSort(a,n,p);
}

с помощью этих помощников:

typedef uint32_t BitStore;
typedef BitStore* BitArray;
BitArray BitArrayNew(int N); //returns array of N bits, all cleared
void BitArraySet(BitArray ba, int i); //sets ba[i] to 1
bool BitArrayGet(BitArray ba, int i); //returns ba[i]
int BitArrayCount1sBelow(BitArray ba, int i) //counts 1s in ba[0..i)

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

Answer 3

Разве не RadixSort ?

O (кН)