Интервью: программа 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

Вы имеете в виду, что массив имеет только 0 s и 1 s?

Суммируйте все N элементов, затем перезапишите массив:)

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 2

Я вижу как минимум две проблемы в программе:

Задача 1:

last = arr + N;

неверно. Должно быть:

last = arr + N - 1;

1012 * потому что *

(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.

задачи2:
Следующий цикл while:

while(front <= last)

неверно и должно быть:

while(front < last)

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

Когда фронт и последний становятся равными, нет смысла продолжать, ваш массив было бы отсортировано к тому времени.

Answer 3

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

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

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

Answer 4

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

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

Альтернативный подход, который не требует предварительного суммирования и работает на месте, заключается в следующем: поместить указатель «запись» w в индекс 0 и указатель «чтение» r в индекс n-1 , Выполните итерацию в обратном направлении с указателем чтения, и каждый раз, когда вы сталкиваетесь с 0, пишите «0» в w и увеличивайте его. Когда вы достигнете начала с r, заполните остальную часть массива "1", используя w.

Answer 5

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

сохраняйте опору для последнего нулевого индекса и меняйте местами все числа слева направо, пока не достигнете конца массива

Answer 6

Общее решение (если оно не только 0 и 1) называется «Сортировка по счету». Его всегда можно использовать, если вы знаете, что данные находятся в определенном диапазоне. Например. Вы хотите отсортировать группу людей по дате их рождения, исключая год. Вы просто создаете массив из 367 (високосного года) дней, и каждый слот в этом массиве представляет собой (связанный) список, который может содержать ваши данные. Теперь вы просматриваете свои данные, вычисляете «день года» по дате рождения peersons и добавляете их в согласованный список.

Answer 7

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 8

Избыток, но вы можете использовать алгоритм построения линейного суффиксного массива Панг Ко:

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

Это взорвет интервьюера: P

Answer 9

Если вы стремитесь к O (n), забудьте обо всех быстрых сортировках (Θ (nlogn)), пузырьковых сортировках и т. Д. Ни один классический алгоритм сортировки не достигает O (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);

Answer 10

Вот реализация C, которая даст решение за время 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;
        }
    }
}