Di chuyển 0 về đầu, 1 về cuối mảng C++

Cho mảng chứa 0, 1 và các số khác. Sắp xếp sao cho: tất cả 0 ở đầu, các số khác ở giữa, tất cả 1 ở cuối.

Ví dụ

Input: [4, 5, 1, 1, 0, 0, 2, 0, 3, 1, 0, 1]
Output: [0, 0, 0, 0, 4, 5, 2, 3, 1, 1, 1, 1]

Thuật toán (2 passes)

1. Pass 1: Đưa tất cả phần tử ≠ 1 lên đầu mảng (giữ thứ tự), đếm số lượng → index idx. Điền 1 vào phần còn lại.
2. Pass 2: Từ cuối mảng, đưa các phần tử ≠ 0 về cuối (ngược lại), rồi điền 0 vào đầu.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

void rearrange0And1(int arr[], int n) {
    int idx = 0;
    // Pass 1: move non-1 to front
    for (int i = 0; i < n; i++)
        if (arr[i] != 1) arr[idx++] = arr[i];
    while (idx < n) arr[idx++] = 1;

    // Pass 2: move non-0 to end (from right)
    idx = n - 1;
    for (int i = n - 1; i >= 0; i--) {
        if (arr[i] == 1) continue;
        if (arr[i] != 0) arr[idx--] = arr[i];
    }
    while (idx >= 0) arr[idx--] = 0;
}

int main() {
    int arr[] = {4,5,1,1,0,0,2,0,3,1,0,1};
    int n = 12;
    rearrange0And1(arr, n);
    for (int x : arr) cout << x << ' ';
    return 0;
}

Kết quả

0 0 0 0 4 5 2 3 1 1 1 1