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

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

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

Если вы нацелены на O (N), забудьте все Quicksorts (θ (NLOGN)), BUBLYORTS и т. Д. Нет. Классический алгоритм сортировки не достигает (n) для стандартных наборов данных, вы должны использовать двоичную природу набора.

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

Вы делаете это слишком сильно на себе! Вы можете сделать это в O (n), зная только размер массива N и сумма элементов S . Поскольку двоичный массив имеет только две возможности для каждого элемента, зная, сколько существует одного элемента, и общий размер достаточно хорош.

Как только вы знаете, что просто выведите массив, содержащий S - N Zeroes и n , в этом порядке. Выполнено!

Альтернативный подход, который не требует суммирования его в первую очередь, и работает на месте: разместить указатель «Написать» W на указателю index 0 и «чтение» R при индексе N-1. Итайте обратно с указателем чтения, и каждый раз, когда вы столкнулись с 0, напишите «0» в w и увеличивайте его. Когда вы достигаете начала с R , заполните оставшуюся часть массива с помощью «1», используя w .

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

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

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

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

Мне жаль ответить на это, используя Python, но это упражнение, которое я хотел сделать. Код предназначен для условного, выводить этапы алгоритма. Конечно, перевод C не сложно, если вы осторожны, двигая указатель. Ваше здоровье!

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

Основная идея вашего алгоритма работает хорошо, и реализация может Быть упрощенным:

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

Обратите внимание, что (начало - это более сильное условие завершения цикла и в каждой итерации только одного действия (перемещение указателей или значений замены), упрощая Код и облегчает понимание того, что цикл действительно прекратится.