¿Cómo ordenar una matriz de enteros en negativo, cero, parte positiva sin cambiar la posición relativa?

Question

Proporcione un algoritmo O (n) que toma como entrada una matriz S, luego divide S en tres conjuntos: negativos, ceros y positivos. Muestre cómo implementar esto en su lugar, es decir, sin asignar memoria nueva. Y debes mantener la secuencia relativa del número. por ejemplo: {-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 4, 1, 2}

No estoy seguro de si tales una solución sale Las mejores soluciones que puedo pensar son:

Solución 1: Usando una matriz de enteros extra, recorra toda la matriz para obtener negativos, luego 0s, luego positivos.

Solución 2: No mantener la secuencia relativa del número. Después coloca la matriz dos veces:

template <typename Type> 
void Partion(Type *array, int begin, int end, Type v, int &l, int &r) 
{ 
    l = begin; 
    for (int i=begin; i!=end; ++i) 
    { 
     if (array[i] < v) 
      swap(array[i], array[l++]); 
    } 
    r = l; 
    for (int j=l; j!=end; ++j) 
    { 
     if (array[j] == v) 
      swap(array[j], array[r++]); 
    } 
} 

Answer 1

no se puede hacer esto simplemente utilizando cualquier "tipo estable" realizado con un comparador costumbre que sólo comprueba el signo?

Edit:
No, eso es O (n log n).

Una cosa que puede hacer en tiempo lineal es reducir el problema. Dado que los ceros no se pueden pedir (¿cómo se dice uno de otro?), Puede hacer un pase por el que recorre la matriz, omitiendo los ceros y completando con los valores distintos de cero. Luego agrega la cantidad correcta de ceros al final.

j=0; 
for (i=0;i<N;i++) { 
    if (A[i]) { 
    A[j++]=A[i]; 
    } 
} 
while (j<N) { 
    A[j++]=0; 
} 

Ahora se puede ignorar el último tramo y el problema se convierte en la búsqueda de un O (n) algoritmo para una partición estable alrededor de 0. Por desgracia, la función from the c++ stlstable_partition tiene solamente O (n) comparaciones, pero O (n log n) swaps si no hay espacio adicional disponible. Sin embargo, este artículo: "Stable minimum space partitioning in linear time" parece indicar que es posible en O (n). No creo entenderlo lo suficientemente bien como para resumirlo claramente aquí.

Si eso funciona, el paso final es insertar los ceros entre las particiones, que también es O (n), ya que los ceros no tienen orden para mantener.

Answer 2

Esta es una instancia del Dutch national flag problem estudiada por Edsger Dijkstra. Es interesante porque no se conoce estable solución a este problema que se ejecuta en O (n) tiempo y O (1) espacio (o al menos, la última vez que revisé la literatura, no existe una solución conocida al problema).

Answer 3

No estoy seguro de si esto ayuda, pero el requisito de partición estable en tres clases se puede reducir al problema de la partición estable en dos clases: separar lo negativo de lo no negativo, luego lo positivo de lo no positivo . Si el problema de dos clases se puede resolver en O (1) espacio y O (n) tiempo, la solución se puede aplicar dos veces para resolver el problema original.

Answer 4

biblioteca El C++ tiene un algoritmo stable_partition que requiere n comparaciones y O (n de registro n) intercambia cuando se ejecuta en-sitio.

Como @Ted points out, el problema requiere dos aplicaciones de este algoritmo.

Answer 5

Los ceros son indistinguibles, así que supongo que no te importa si se intercambian o simplemente se sobrescriben al final (es decir, simplemente ponemos a cero la parte central después de que hayamos terminado los números positivos y negativos extremos de la matriz).

Si está viendo una situación en la que los números enteros son solo claves para algo más grande, puede que este no sea el caso; es posible que desee que se conserven ceros y particiones estables. Pero si no, aquí hay dos ideas:

En primer lugar, su problema es idéntico al problema de la partición binaria estable.

Un algoritmo para su problema, por supuesto, tiene particiones binarias estables (solo una matriz sin ceros). Por el contrario, si la matriz tiene ceros, puede utilizar una partición binaria para hacer el trabajo sucio: escanee la matriz, intercambie cada cero que encuentre con el siguiente valor negativo (haciendo un seguimiento de dónde estaba para no hacer n^2 escaneo general), lo que resulta en

[mixed -, +] [posiblemente extra ceros] [mixed 0, +].

Entonces haces dos particiones binarias para obtener

[-] [+] [0] [+]

y cambiar los valores de + encima para conseguir el resultado deseado.

AFAIK con particiones binarias puede elegir cualquiera de dos estable, en el lugar, y O (n). Por lo tanto, parece que no hay suerte, pero aparentemente se conoce un algoritmo O (n * log n) in situ como un algoritmo O (n) que utiliza el espacio de raspado de log (n).

En segundo lugar, si puede garantizar que el número de ceros será al menos f (n), los ceros pueden compensar la falta de espacio de cero; es simple obtener una partición en el lugar estable en el tiempo O (n^2/f (n)). En particular, si los ceros serán al menos una fracción constante de la matriz, se obtiene O (n) tiempo de ejecución con sólo correr estos dos pasos hasta que haya terminado:

1. derecho de exploración a través de la matriz, el canje de cada uno cero te encuentras con el siguiente valor negativo
2. de lectura izquierdo a través de la matriz, el canje de cada uno cero te encuentras con el siguiente valor positivo

Si ceros son tan abundantes como cualquiera de los otros tipos, esto es hecho después de hacer 1 luego 2 luego 1 otra vez.