Pregunta de la entrevista: programa C para ordenar una matriz binaria en O (n)

Question

He creado el siguiente programa para hacerlo, pero parece que no funciona y entra en un ciclo infinito. Su funcionamiento es similar al quicksort.

int main() 
{ 
int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1}; 
int N = 18; 
int *front, *last; 

front = arr; 
last = arr + N; 
while(front <= last) 
{ 
    while((front < last) && (*front == 0)) 
    front++; 

    while((front < last) && (*last == 1)) 
    last--; 

    if(front < last) 
    { 
    int temp = *front; 
    *front = *last; 
    *last = temp; 
    front ++; 
    last--; 
    } 
} 
for(int i=0;i<N;i++) 
    printf("%d ",arr[i]); 

return 0; 
} 

Answer 1

veo al menos dos problemas en el programa:

Problema 1:

last = arr + N; 

es incorrecto. Debe ser:

last = arr + N - 1; 

porque

(arr + 0) points to 0th ele 
(arr + 1) points to 1st ele 
... 
(arr + N -1) points to (N-1)th ele..which is the last element. 

Problem2:
Siguiente su bucle while:

while(front <= last) 

es incorrecta y debe ser:

while(front < last) 

En su caso cuando el frente y el último se vuelven iguales, su bucle continúa pero ni el frente ni el último se modifican en este punto, lo que resulta en un bucle infinito.

Cuando el frente y el último se igualan, no tiene sentido continuar, su arreglo habría sido ordenado para entonces.

Answer 2

¡Lo estás haciendo demasiado duro para ti! Puede hacerlo en O (n) conociendo solo el tamaño de la matriz n y la suma de los elementos S. Como una matriz binaria tiene solo dos posibilidades para cada elemento, saber cuántos hay de un elemento y el tamaño total es lo suficientemente bueno.

Una vez que lo sepa, simplemente envíe una matriz que contenga S - n ceros y n, en ese orden. ¡Hecho!

Un enfoque alternativo que no requiere resumir primero y funciona en el lugar es el siguiente: Coloque un puntero de "escritura" w en el índice 0 y un puntero de "lectura" r en el índice n-1. Itere al revés con el puntero de lectura, y cada vez que encuentre un 0, escriba un "0" en w e increméntelo. Cuando llegue al comienzo con r, complete el resto de la matriz con "1" con w.

Answer 3

¿Quieres decir que la matriz solo tiene 0 s y 1 s?

sumar todos los elementos N, entonces sobreescriben la matriz :)

int main() { 
    int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1}; 
    int N = sizeof arr/sizeof *arr; /* 18 */ 
    int sum = 0; 
    int ndx; 
    for (ndx=0; ndx<N; ndx++) sum += arr[ndx]; 
    for (ndx=0; ndx<N-sum; ndx++) arr[ndx] = 0; 
    for (ndx=N-sum; ndx<N; ndx++) arr[ndx] = 1; 
} 

Answer 4

Su código no entra en un bucle sin fin en mi sistema:

# gcc $CFLAGS -o test test.c 
# ./test 
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 

Sin embargo, el resultado es incorrecto. Veo 8 veces 1, pero debe ser 9 veces uno.

Como algunas personas señalaron, resumiendo es un enfoque mucho más simple:

#include <stdio.h> 

int main() 
{ 
    int i; 
    int count; 
    int N = 18; 
    int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1}; 

    /* Sum up all elements */ 
    i = 0; 
    count = 0; 
    while (i < N) count += arr[i++]; 

    /* Overwrite the array */ 
    i = 0; 
    count = N - count; 
    while (i < count) arr[i++] = 0; 
    while (i < N) arr[i++] = 1; 

    /* Print result */ 
    for (i = 0; i < N; i++) printf("%d ",arr[i]); 
} 

Answer 5

Si usted tiene como objetivo O (n) olvidar todos quicksorts (Θ (nlogn)), etc. Sin bubblesorts algoritmo de ordenación clásica obtiene O (n) para conjuntos de datos estándar, debe explotar la naturaleza binaria del conjunto.

int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1}; 
int N = 18; 
int i,s=0; 
for(i=0;i<N;i++) s+=(arr[i]==0); 
for(i=0;i<N;i++) arr[i]=!(i<s); 

Answer 6

La idea básica de su algoritmo funciona bien y la ejecución puede simplificarse:

int a[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1}; 

int *begin = a; 
int *end = begin + 17; 

while (begin < end) { 
    if (*begin == 0) 
     begin++; 
    else if (*end == 1) 
     end--; 
    else { 
     *begin = 0; 
     *end = 1; 
    } 
} 

Tenga en cuenta que (begin < end) es una condición más fuerte para la terminación del bucle y en cada iteración de la una sola acción (moviendo un puntero o intercambiando valores) se toma simplificando el código y facilitando la comprensión de que el ciclo terminará realmente.

Answer 7

aparentemente la otra pregunta se cerró ... su algoritmo funciona perfectamente. lo que he publicado en respuesta a maddy en un aparente dup de este redirigido aquí por una persona que lo cerró

int main() 
{ 
    int v[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1}; int *a, *b, i, n; 
    n = sizeof(v)/sizeof(int); 
    for (a = v, b = v + n - 1; a < b; ++a) { 
    if (*a) { 
     for (; *b; --b) if (a == b) goto end; 
     *a = 0; *b-- = 1; 
    } 
    } 
    end: for (i = 0; i < n; ++i) printf("%d%s", v[i], (i==n-1?"\n":",")); return 0; 
} 

trasladó algunas líneas juntas para que se ajuste en la página .... más o menos la misma

Answer 8

Reposicionando aquí, ya que la pregunta donde respondí se cerró (duplicado de esta).

Lamento haber respondido esto usando Python, pero es un ejercicio que quería hacer. El código está destinado a ser detallado, para dar salida a los pasos del algoritmo. Por supuesto, la traducción a C no es difícil, siempre que tenga cuidado al mover el puntero. ¡Aclamaciones! salida

# Put zeros on the left, ones on the right in one pass             
a = [1,0,1,0,0,1,1,1,0,0,1,0,0,1,0,0,1,1,0,0,1,1,0,0,1,0,1] 
cl = 0 
cr = len(a) - 1 
print a 

while(True): 
    if cl + 1 == cr: 
     print 'last pass; adjacent elements' 
     if a[cl] == 0: 
      print 'a[%d] = 0; leave and exit loop' % (cl) 
      print 'final array:' 
      print a 
      break 
     if a[cl] == 1: 
      print 'a[%d] = 1; try to swap with a[%d]' % (cl, cr) 
      if a[cr] == 1: 
       print 'a[%d] = 1 as well; leave and exit loop' % (cr) 
       print 'final array:' 
       print a 
       break 
      else: 
       print 'a[%d] and a[%d] swapped; leave and exit loop' % (cl, cr) 
       a[cl] = 0 
       a[cr] = 1 
       print 'final array:' 
       print a 
       break 
    if a[cl] == 0: 
     print 'a[%d] = 0; leave and move on to a[%d]' % (cl,cl+1) 
     cl += 1 
     continue 
    else: 
     print 'a[%d] = 1 move to the right' % (cl) 
     while(True): 
      if a[cr] == 1: 
       print 'a[%d] cannot be moved to a[%d], try a[%d]' % (cl, cr, cr-1) 
       cr -= 1 
       continue 
      else: 
       print 'a[%d] swapped with a[%d]' % (cl, cr) 
       a[cr] = 1 
       a[cl] = 0 
       cr -= 1 
       cl += 1 
       print 'next up: a[%d]; right side blocked up to %d' % (cl,cr) 
       break 
    if (cl + 1) == cr: 
     break 

muestra:

[1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1] 
a[0] = 1 move to the right 
a[0] cannot be moved to a[26], try a[25] 
a[0] swapped with a[25] 
next up: a[1]; right side blocked up to 24 
a[1] = 0; leave and move on to a[2] 
a[2] = 1 move to the right 
a[2] cannot be moved to a[24], try a[23] 
a[2] swapped with a[23] 
next up: a[3]; right side blocked up to 22 
a[3] = 0; leave and move on to a[4] 
a[4] = 0; leave and move on to a[5] 
a[5] = 1 move to the right 
a[5] swapped with a[22] 
next up: a[6]; right side blocked up to 21 
a[6] = 1 move to the right 
a[6] cannot be moved to a[21], try a[20] 
a[6] cannot be moved to a[20], try a[19] 
a[6] swapped with a[19] 
next up: a[7]; right side blocked up to 18 
a[7] = 1 move to the right 
a[7] swapped with a[18] 
next up: a[8]; right side blocked up to 17 
a[8] = 0; leave and move on to a[9] 
a[9] = 0; leave and move on to a[10] 
a[10] = 1 move to the right 
a[10] cannot be moved to a[17], try a[16] 
a[10] cannot be moved to a[16], try a[15] 
a[10] swapped with a[15] 
next up: a[11]; right side blocked up to 14 
a[11] = 0; leave and move on to a[12] 
a[12] = 0; leave and move on to a[13] 
last pass; adjacent elements 
a[13] = 1; try to swap with a[14] 
a[13] and a[14] swapped; leave and exit loop 
final array: 
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 

Answer 9

Overkill, pero se puede usar el tiempo lineal algoritmo de construcción sufijo matriz de Pang Ko:

http://sites.google.com/site/kopangcn2/software2

Eso haría volar la mente del entrevistador: P

Answer 10

int[] arr = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 }; 

int left = 0; 
int right = arr.Length-1; 
int first = arr[left]; 
while (left < right) 
{ 
    if (arr[left] == 0 && arr[right] ==1) 
    { 
     left++; 
     right--; 
    } 
    else if (arr[left] == 1 && arr[right] == 1) 
    { 
     right--; 
    } 
    else if (arr[left] == 0 && arr[right] == 0) 
    { 
     left++; 
    } 
    else 
    { 
     arr[left] = 0; 
     arr[right] = 1; 
     left++; 
     right--; 
    } 
} 

Answer 11

aquí una respuesta simple :)

int main() 
{ 
    int a[]={1,0,1,1,1,0,1,0,1},size=9,end_value,index1,index2=-1; 
    end_value=a[size-1]; 
    for(index1=0;index1 < size-1;index1++) 
    { 
     if(a[index1]==end_value) 
     { 
      index2++; 
      a[index2]=!a[index2]; 
      a[index1]=!a[index1]; 
     } 
    } 
    index2++; 
    a[index2]=!a[index2]; 
    a[index1]=!a[index1]; 
} 

Answer 12

La solución general (si es que no sólo 0s y 1s) se llama "Clasificación por Counting". Siempre se puede usar si sabes que los datos están en un cierto rango. P.ej. desea ordenar un grupo de personas por su fecha de nacimiento, excluyendo el año. Usted acaba de hacer una matriz de 367 (año bisiesto), y cada ranura en esa matriz es una lista (vinculada) capaz de contener sus datos. Ahora que barre sus datos, calcule el "día del año" a partir de la fecha de cumpleaños de las peersons y añádalos a la lista correspondiente.

Answer 13

void my_sort(int* arr, int n){ 
    int zero = -1; 

    for(int i = 0; i < n;i++){ 
    if(arr[i] == 0){ 
     zero++; 
     swap(arr[zero],arr[i]); 
    } 
    } 
} 

mantener un pivote para el último índice cero y mantener el intercambio de todos los números de izquierda a derecha hasta llegar a la final de la matriz

Answer 14

Esto se puede hacer con un simple binario counting sort:

#include <stdio.h> 

int main() 
{ 
    int N = 18, zeros=0, i; 
    int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1}, *ptr, *last; 

    ptr = arr; 
    last = arr + N - 1; 
    while (ptr != last) 
    { 
     if (!*ptr) zeros++; 
     ptr++; 
    } 

    for (i = 0; i < zeros; i++) arr[i] = 0; 
    for (; i < N; i++) arr[i] = 1; 

    for (i = 0; i < N; i++) 
     printf("%d ", arr[i]); 
    putchar('\n'); 

    return 0; 
} 

Answer 15

Esto debería funcionar bien. Solo un bucle único hará el trabajo.

int arr[]={0,0,0,1,0,1,0,1,0}; 
int lastz=7,i=0,temp,n; 
n=9; 
while(i<n){ 
     if(arr[i]==0 && i<lastz){ 
      lastz=i; 
     } else if(arr[i]==1 && lastz<i){ 
      temp=arr[lastz]; 
      arr[lastz]=arr[i]; 
      arr[i]=temp; 
      lastz++; 
     } 
     i++; 
} 

Answer 16

Aquí está la Implementación C que dará la solución en el tiempo O (n).

/* 
C program to sort a binary array in one pass 
Input: 0 1 0 1 1 0 
OutPut: 0 0 0 1 1 1 
*/ 

#include<stdio.h> 
void segregate0and1(int*, int); 

int main() 
{ 
    int a[] = {0, 1, 0, 1, 1, 0}; 
    int array_length = sizeof(a)/sizeof(a[0]); 

    segregate0and1(a, array_length); 

    printf("Array after segregation: "); 
    for (int i = 0; i < array_length; i++) 
     printf("%d ", a[i]); 
    printf("\n");  

    return 0; 
} 

void segregate0and1(int a[], int array_length) 
{ 
    int left = 0, right = array_length-1; 

    while (left < right) 
    { 
     /* Increment left index while we see 0 at left */ 
     while (a[left] == 0 && left < right) 
      left++; 

     /* Decrement right index while we see 1 at right */ 
     while (a[right] == 1 && left < right) 
      right--; 

     /* If left is smaller than right then there is a 1 at left 
      and a 0 at right. Exchange a[left] and a[right]*/ 
     if (left < right) 
     { 
      a[left] = 0; 
      a[right] = 1; 
     } 
    } 
}