Domanda intervista: programma C per ordinare un array binario in O (n)

Question

Ho creato il seguente programma per farlo, ma non sembra funzionare e va in loop infinito. Il suo funzionamento è simile a 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

vedo almeno due problemi nel programma:

Problema 1:

last = arr + N; 

non è corretto. Dovrebbe essere:

last = arr + N - 1; 

perché

(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:
Prossimo Inserisci il tuo ciclo while:

while(front <= last) 

è corretto e deve essere:

while(front < last) 

Nel tuo caso quando il fronte e l'ultimo diventano uguali, il tuo ciclo continua ma né davanti né l'ultimo vengono modificati a questo punto, con conseguente ciclo infinito.

Quando il fronte e l'ultimo diventano uguali, non ha senso continuare, il tuo array sarebbe stato ordinato da allora.

Answer 2

Stai diventando troppo duro con te stesso! Puoi farlo in O (n) conoscendo solo la dimensione dell'array n e la somma degli elementi S. Dato che un array binario ha solo due possibilità per ciascun elemento, sapere quanti ce ne sono di un elemento e la dimensione totale è abbastanza buono.

Una volta accertato, è sufficiente emettere un array contenente gli zeri S - n e n, in questo ordine. Fatto!

Un approccio alternativo che non richiede riassumendo in su prima e lavora sul posto è la seguente: Posizionare un "write" puntatore w in corrispondenza dell'indice 0 e un "letto" puntatore r a indice n-1. Iterare all'indietro con il puntatore di lettura e ogni volta che si incontra uno 0, scrivere uno "0" a w e incrementarlo. Quando si raggiunge l'inizio con r, riempire il resto dell'array con "1" utilizzando w.

Answer 3

vuoi dire la matrice ha solo 0 s e 1 s?

Somma tutti gli elementi N, quindi sovrascrivere la matrice :)

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

il codice non va in un ciclo infinito sul mio 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 

Tuttavia il risultato è sbagliato. Vedo 8 volte 1, ma dovrebbe essere 9 volte uno.

Come alcune persone hanno sottolineato, riassumendo è un approccio molto più semplice:

#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

Se si mira a O (n) dimenticare tutti quicksorts (Θ (nlogn)), bubblesorts ecc Nessun algoritmo di ordinamento classico raggiunge O (n) per set di dati standard, è necessario sfruttare la natura binaria del set.

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

L'idea di base del vostro algoritmo funziona bene e l'attuazione può essere semplificata:

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

Nota che (begin < end) è una condizione più forte per la cessazione del ciclo e in ogni iterazione del una sola azione (spostando un puntatore o scambiando valori) viene preso, semplificando il codice e rendendo più facile capire che il ciclo terminerà realmente.

Answer 7

a quanto pare l'altra domanda era chiusa ... il tuo algoritmo funziona perfettamente. quello che ho postato in risposta ad maddy in un apparente dup di questa reindirizzato qui da una persona che ha chiuso lo

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

spostato alcune linee insieme per farlo entrare nella pagina .... praticamente la stessa

Answer 8

Ripubblicare qui, poiché la domanda in cui ho risposto è stata chiusa (duplicato di questo).

Mi dispiace rispondere a questo utilizzando Python, ma è un esercizio che volevo fare. Il codice è pensato per essere dettagliato, per generare i passaggi dell'algoritmo. Naturalmente, la traduzione in C non è difficile, a patto che tu stia attento a spostare il puntatore. Saluti! Uscita

# 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 

Esempio:

[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, ma è possibile utilizzare il tempo lineare algoritmo di costruzione suffisso Array di Pang Ko:

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

Che sarebbe soffiare mente dell'intervistatore: 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--; 
    } 
} 

.210

Answer 11

ecco una semplice risposta :)

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 soluzione generale (se non è solo 0 e 1) si chiama "Ricerca per Conteggio". Può sempre essere utilizzato se si sa che i dati si trovano in un determinato intervallo. Per esempio. vuoi ordinare un gruppo di persone per la loro data di nascita, escluso l'anno. Basta creare un array di 367 giorni (anno bisestile) e ogni slot in quell'array è un elenco (collegato) in grado di contenere i dati. Ora si passano i dati, si calcola il "giorno dell'anno" dalla data di compleanno dei peerson e li si aggiunge all'elenco appropriato.

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

mantenere un perno per l'ultimo indice zeroth e mantenere scambiare tutti i numeri da sinistra a destra fino a raggiungere la fine della matrice

Answer 14

Questo può essere fatto con un semplice 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

Questo dovrebbe funzionare correttamente. Solo un singolo ciclo farà il lavoro.

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

Qui è l'implementazione C che darà la soluzione in 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; 
     } 
    } 
}