Временная сложность для сортировки массива двоичных чисел

Question

Учитывая следующий массив: | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |

мы должны отсортировать выше массив как все 1 на правой стороне и 0 на левой стороне.

Я придумал 2 алгоритма на C++.

первый один:

for(i = 0; i < n; i++) { 
    if(a[i] == 1 && i != n - 1) { 
     for(j = i + 1; j < n; j++) { 
      if(a[j] == 0) { 
       temp = a[j]; 
       a[i] = a[j]; 
       a[j] = temp; 
       break; 
      } 
     } 
    } 
} 

второй один:

int x = 0; 
for(i = 0; i < n; i++) { 
    if(a[i] == 1) { 
     for(j = n-x-1; j >= 0; j--) { 
      if(a[j] == 0) { 
       temp = a[j]; 
       a[i] = a[j]; 
       a[j] = temp; 
       x++; 
       break; 
      } 
     } 
    if(x > n/2) 
    break; 
} 

вы можете сказать мне временную сложность обоих. и который лучше работает , также предложите мне лучший алгоритм с объяснением. Благодарю.

Answer 1

Просто посчитайте количество единиц, затем заполните ваш массив нулями сначала lengthOfArray - sum элементов, а затем с помощью единиц. Сложностью будет O (n).

В ваших обоих случаях у вас есть сложность O (N²)

Answer 2

1-ый отсортирует массив в O (N^2) время, как это прямым следствием пузырьковой сортировки. но второй метод не будет сортировать массив, потому что вы меняете 1 с первым 0 при переходе от конца. Поэтому, если ваш массив похож на 0 0 0 1 1 1, тогда 2-й код поменяет 1 в 3-м индексе на 0 из 2-го индекса и, наконец, выглядит как 0 0 1 1 1 0. И я не знаю, что это за х?

Answer 3

Как @Alexandru сказал, что это хорошо дает O (N), вам просто нужно перебирать дважды

1. Чтобы найти количество 0, 1
2. Для заполнения массива с 1, 0, как говорит граф ,

Если вы ищете другой альтернативный вид, вы можете посмотреть, что это O (N).

for(int i=0, j=n-1;i<j;) 
{ 
if(a[i]==1 && a[j]==0) swap(a[i],a[j]); 
else if(a[i]==1 && a[j]==1) j--; 
else if(a[i]==0 && a[j]==0) i++; 
else if(a[i]==0 && a[j]==1) {j--; i++;} 
}