Интервью: программа C для сортировки двоичного массива в O (n)

Question

Я придумал следующую программу для этого, но она, похоже, не работает и идет в бесконечный цикл. Его работа аналогична быстрой сортировке.

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

Это должно работать нормально. Только один цикл сделает работу.

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 2

Это можно сделать с помощью простого двоичного файла с сортировкой :

#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 3

вот простой ответ:)

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 4

Повторное размещение здесь, поскольку вопрос, на который я ответил, закрыт (дубликат этого).

Извините, что ответил на это с помощью Python, но я хотел бы выполнить это упражнение. Код должен быть подробным, чтобы выводить шаги алгоритма. Конечно, перевод на C не сложен, если вы осторожно перемещаете указатель. Ура! * * 1005

# 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

Пример вывода:

[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 5

очевидно, другой вопрос был закрыт ... ваш алгоритм работает отлично. то, что я написал в ответ на maddy в явном dup этого перенаправленного здесь человеком, который закрыл это

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

переместил несколько строк вместе, чтобы они поместились на странице .... почти так же

Answer 6

Ваш код не заходит в бесконечный цикл в моей системе:

# 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

Однако результат неверен. Я вижу 8 раз 1, но это должно быть 9 раз один.

Как отмечали некоторые люди, подведение итогов - гораздо более простой подход:

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