algorithm - bubble - ¿Qué algoritmo puede realizar una partición binaria in situ estable con solo O(N) movimientos?

sorting algorithms comparison

Question

Estoy tratando de entender este documento: partición de espacio mínimo estable en tiempo lineal.

Parece que una parte crítica de la afirmación es que

El algoritmo B ordena de manera estable una matriz de bits de tamaño n en tiempo O (nlog ₂ n) y espacio extra constante, pero solo realiza movimientos O (n) .

Sin embargo, el documento no describe el algoritmo, solo hace referencia a otro documento al que no tengo acceso. Puedo encontrar varias formas de hacer el orden dentro de los límites de tiempo, pero tengo problemas para encontrar una que garantice que O (N) se mueva sin que también requiera más que espacio constante.

¿Qué es este algoritmo B? En otras palabras, dado

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

¿hay una función B(Item* a, size_t N); que ordena de forma estable un Predicado de uso como la clave de ordenación con menos de nlog ₂ n llamadas a Predicado, y realiza solo las escrituras O (N) en un ?

Answer 1

¿No es RadixSort ?

O (kN)

Answer 2

Esto es lo que tengo hasta ahora. Una versión de clasificación de ciclo que utiliza una matriz de bits para mantener el resultado de las pruebas de partición y calcula los destinos sobre la marcha. Realiza una partición binaria estable con N comparaciones, intercambios <N y exactamente 2N bits de almacenamiento asignado.

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);
}

usando estos ayudantes:

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)

Obviamente esto no es un espacio constante. Pero creo que esto podría ser usado como un bloque de construcción para la meta final. La matriz completa se puede dividir en bloques N / B utilizando un BitArray de tamaño fijo de B bits. ¿Hay alguna manera de reutilizar esos mismos bits mientras se realiza una fusión estable?

Answer 3

Estoy tentado de decir que no es posible. Cada vez que estás calculando O (n log n) cantidad de información, pero no tienes (1) lugar para esconderla (espacio constante), y (2) para usarla de inmediato (O (n) se mueve), hay algo raro en, posiblemente implicando un uso intensivo de la pila (que puede no estar incluido en el análisis del espacio, aunque debería estarlo).

Podría ser posible si almacena información temporal dentro de muchos bits de un solo número entero, o algo parecido a eso. (Entonces O (1) en la práctica, pero O (log n) en teoría.)

La clasificación de radix no lo haría porque tendría que llamar al predicado para crear los dígitos, y si no memoriza la transitividad de la comparación, entonces la llamará O (n ^ 2) veces. (Pero para memorizar se necesita O (log n) espacio amortizado por artículo, creo).

QED - Prueba por falta de imaginación :)