ordenar una matriz por posición relativa

Question

Dar una matriz que tiene enteros negativos y positivos, implementar un algoritmo que cuesta O (n) tiempo y O (1) espacios para hacer todos los enteros negativos delante de todos los enteros positivos, y mantener la posición relativa. por ejemplo: {1,7, -5,9, -12,15} -----> {-5, -12,1,7,9,15}

¿Tiene alguna idea?

Answer 1

Está solicitando una función de partición estable en el lugar.

El documento Stable Minimum Space Partitioning in Linear Time (1992) afirma tener tal algoritmo, pero algunos other SO questions han planteado dudas sobre su viabilidad.

Answer 2

mi idea para un algoritmo:

tiene un punto de giro similar a la selección general en la partición basada. http://en.wikipedia.org/wiki/Selection_algorithm

giran alrededor del pivote intercambio de valores hasta que todos los números negativos están en una partición de la matriz (con todos los números positivos después de ella .. o tal vez lo rodea)

Sin embargo, este intercambio se han afectado ligeramente el ordenamiento . Explicaré cómo corregir el orden de los números negativos (y usted hará lo mismo para corregir el orden de los números positivos).

Cada vez que intercambia dos números ... cambie el signo del número.

esto significa que si a través de la partición de números negativos, todos los que son positivos son números negativos que se intercambiaron. Eso significa que todos los números negativos entre un número positivo y el siguiente número positivo deben estar antes del primer número positivo. ir a través de e intercambiarlos todos (no debería haber demasiados en una fila lo que debería obtener O (N))

negs = -4,-5,-6 
pos = 1,2,3 
ans = -4,-5,-6,1,2,3 

1,2,-4,-5,3,-6 

i->-4 j->-5 
-4 and -5 are both negative.. decrease i by one 

1,2,-4,-5,3,-6 
i->2 j->-5 
swap. 

1,5,-4,-2,3,-6 
i->1 j->3 
1 and 3 are both positive, increase j by one (take turns at changing i,j) 

1,5,-4,-2,3,-6 
i->1 j->-6 
swap. 

6,5,-4,-2,3,-1 

#now we have negs at start, pos at end of array. 
#now do corrections using signs as notification of what was swapped 
#we had a counter that told us there were 3 negs.and 3 pos. 
#fix first 3 negs.. 6,5,-4 should go to -4,-5,-6 
(can tell order by. non swapped negs always come before swapped negs..in the order they are in.. negs are in reverse order) 
i'll leave you to implement algorithm for it. 

Answer 3

Este código está la mayor parte del camino .. Yo sólo no han hecho lo parte donde invierte los valores intercambiados entre x, j y entre j, y. (Puedes retroceder en su lugar ... aún no lo hice).

De todos modos .. no tengo tiempo para completarlo me temo, pero es de esperar que pueda:

def brute_force(nums): 
    neg = [i for i in nums if i<0] 
    pos = [i for i in nums if i>=0] 
    return neg+pos 

def in_place(nums,i,j,depth): 
    x,y = i,j 
    print 'running on ',nums[i:j+1] 
    if j-i==1: 
     a,b = nums[i],nums[j] 
     if a>=0 and b<0: 
      nums[i],nums[j] = b,a 
     return None 
    #print i,j 
    while i<j: 
     a,b = nums[i],nums[j] 
     if (a<0 and b>=0): 
      i+=1 
      j-=1 
     elif (a>=0 and b<0): 
      nums[i],nums[j]=-b,-a 
      i+=1 
      j-=1 
     elif a<0: 
      i+=1 
     else: 
      j-=1 
    print "changed1 to ", nums 
    print nums[x:j+1],nums[j+1:y+1] 
    start = (i for i in reversed(nums[x:j+1]) if i>=0) 
    for i in range(x,j): 
     if nums[i]>=0: 
      nums[i]=next(start) 
    print "changed2 to ", nums 
    end = (i for i in reversed(nums[j+1:y+1]) if i<0) 
    for i in range(j+1,y+1): 
     if nums[i]<0: 
      nums[i]=next(end) 
    print "changed3 to ", nums 
    if depth == 0: 
     in_place(nums,0,j,depth+1) 
     in_place(nums,j+1,len(nums)-1,depth+1) 







nums = [1,2,-4,-5,3,-6] 

print brute_force(nums) 
in_place(nums,0,len(nums)-1,0) 
print nums 
print "going z" 
#z = [-2,3,-1] 
#in_place(z,0,2,0) 
#print z 

Además ejemplo:

_list = [1,-4,2,-5,3,-6] 

def in_place(nums,i,j,depth): 
    x,y = i,j 
    print 'running on ',nums[i:j+1] 
    if j-i==1: 
     a,b = nums[i],nums[j] 
     if a>=0 and b<0: 
      nums[i],nums[j] = b,a 
     return None 
    #print i,j 
    while i<j: 
     a,b = nums[i],nums[j] 
     if (a<0 and b>=0): 
      i+=1 
      j-=1 
     elif (a>=0 and b<0): 
      nums[i],nums[j]=-b,-a 
      i+=1 
      j-=1 
     elif a<0: 
      i+=1 
     else: 
      j-=1 
    print "changed1 to ", nums 

in_place(_list,0,len(_list)-1,0) 

>>> 
running on [1, -4, 2, -5, 3, -6] 
changed1 to [6, -4, 5, -2, 3, -1] 

Answer 4

Esto puede hacerse mediante la alteración fusionar la función en el algoritmo de clasificación de combinación.

Entrada: int [] A, bajo int, int mediados, int alta

Loop in-varianza antes del inicio: A [baja] a A [MID] tiene números -ve + ve siguientes por números y tiene números que originalmente estaban presentes en A [bajo] a A [medio].
Por encima de condición se cumple para un [MID + 1] para A [Alto]

pasos Fusión:

1. omitir todos los elementos entre bajo a medio que son -ve, guardar el punto de partida de + Los números ve dicen en la variable j.
2. copia elementos que son + restante ve antes de mediados de matriz temporal
3. copia todos los elementos -ve en gama media + 1 a alta a partir de una [j] mientras incrementando j
4. copiar los elementos almacenados en matriz temporal a a continuando desde j

5. + ve elementos en el segundo medio de a ya están en su lugar, así que no hay necesidad de hacer nada

   public static void rearrange(int[] a){ 
       merge_arrange(a, 0, a.length-1); 
   } 
   
   public static void merge_arrange(int[] a, int low, int high){ 
       if(low < high){ 
        int mid = (low+high)/2; 
        merge_arrange(a, low, mid); 
        merge_arrange(a, mid+1, high); 
   
        merge(a, low, mid, high); 
       } 
   } 
   
   public static void merge(int[] a, int low, int mid, int high){ 
       ArrayList<Integer> temp = new ArrayList<Integer>(); 
   
       int i; 
       for(i=low;i<=mid && a[i]<0;i++); 
   
       int j=i; 
       while(i<=mid){ 
        temp.add(a[i++]); 
       } 
   
       int k; 
       for(k=mid+1;k<=high && a[k]<0;k++){ 
        a[j] = a[k]; 
        j++; 
       } 
   
       for(int num:temp){ 
        a[j] = num; 
        j++; 
       } 
   }