Sắp xếp mảng chỉ chứa 0, 1, 2 bằng thuật toán DNF trong C++

Cho mảng chỉ chứa các giá trị 0, 1, 2. Sắp xếp mảng sao cho tất cả 0 ở đầu, rồi 1, rồi 2 ở cuối. Phải sắp xếp tại chỗ (in-place). Ví dụ:

Đầu vào 1:

arr[] = {2, 0, 0, 1, 2, 1}

Đầu ra:

0 0 1 1 2 2

Đầu vào 2:

arr[] = {0, 1, 1, 2, 1, 1, 0}

Đầu ra:

0 0 1 1 1 1 2

Phương pháp: Thuật toán Dutch National Flag (DNF)

Sử dụng 3 con trỏ: low (đầu), mid (duyệt), high (cuối).

• Khởi tạo low = 0, mid = 0, high = n-1.
• Khi mid <= high:
  • Nếu a[mid] == 0: hoán đổi a[low] và a[mid], tăng low và mid.
  • Nếu a[mid] == 1: chỉ tăng mid.
  • Nếu a[mid] == 2: hoán đổi a[mid] và a[high], giảm high (không tăng mid vì phần tử mới tại mid chưa kiểm tra).

Thuật toán chạy trong O(n) thời gian, O(1) không gian.

Ví dụ mã nguồn

#include <iostream>
using namespace std;

void dnfSort(int a[], int n) {
    int low = 0, mid = 0, high = n - 1;
    while (mid <= high) {
        if (a[mid] == 0) {
            swap(a[low], a[mid]);
            low++; mid++;
        } else if (a[mid] == 1) {
            mid++;
        } else { // a[mid] == 2
            swap(a[mid], a[high]);
            high--;
        }
    }
}

int main() {
    int a[] = {1, 0, 0, 2, 1, 1, 0, 0, 1};
    int n = sizeof(a) / sizeof(int);
    dnfSort(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    return 0;
}

Kết quả

0 0 0 0 1 1 1 1 2